New Developments in the field Computational Complexity part2(Computer Science)
- Quantum Feasibility Labeling for NP-complete Vertex Coloring Problem(arXiv)
Author : Junpeng Zhan
Abstract : Many important science and engineering problems can be converted into NP-complete problems which are of significant importance in computer science and mathematics. Currently, neither existing classical nor quantum algorithms can solve these problems in polynomial time. To overcome this difficulty, this paper proposes a quantum feasibility labeling (QFL) algorithm to label all possible solutions to the vertex coloring problem, which is a well-known NP-complete problem. The variational quantum search (VQS) algorithm proposed in my previous work has been demonstrated, up to 26 qubits, to achieve an exponential speedup in finding good element(s) from an unstructured database. Using the labels and the associated possible solutions as input, the VQS can find all feasible solutions to the vertex coloring problem. The number of qubits and the circuit depth required by the QFL each is a polynomial function of the number of vertices, the number of edges, and the number of colors of a vertex coloring problem. The QFL together with the VQS could be the first algorithm to solve an NP-complete problem in polynomial time, provided that the VQS is proved to be efficient for any number of qubits.
2.Parameterised and Fine-grained Subgraph Counting, modulo 2 (arXiv)
Author : Leslie Ann Goldberg, Marc Roth
Abstract : Given a class of graphs H, the problem ⊕Sub(H) is defined as follows. The input is a graph H ∈ H together with an arbitrary graph G. The problem is to compute, modulo 2, the number of subgraphs of G that are isomorphic to H. The goal of this research is to determine for which classes H the problem ⊕Sub(H) is fixed-parameter tractable (FPT), i.e., solvable in time f(|H|) · |G|O(1).
Curticapean, Dell, and Husfeldt (ESA 2021) conjectured that ⊕Sub(H) is FPT if and only if the class of allowed patterns H is matching splittable, which means that for some fixed B, every H ∈ H can be turned into a matching (a graph in which every vertex has degree at most 1) by removing at most B vertices.
Assuming the randomised Exponential Time Hypothesis, we prove their conjecture for (I) all hereditary pattern classes H, and (II) all tree pattern classes, i.e., all classes H such that every H ∈ H is a tree.
We also establish almost tight fine-grained upper and lower bounds for the case of hereditary patterns (I).
