The @math -colouring reconfiguration problem asks whether, for a given graph @math , two proper @math -colourings @math and @math of @math , and a positive integer @math , there exists a sequence of at most @math proper @math -colourings of @math which starts with @math and ends with @math and where successive colourings in the sequence differ on exactly one vertex of @math . We give a complete picture of the parameterized complexity of the @math -colouring reconfiguration problem for each fixed @math when parameterized by @math . First we show that the @math -colouring reconfiguration problem is polynomial-time solvable for @math , settling an open problem of Cereceda, van den Heuvel and Johnson. Then, for all @math , we show that the @math -colouring reconfiguration problem, when parameterized by @math , is fixed-parameter tractable (addressing a question of Mouawad, Nishimura, Raman, Simjour and Suzuki) but that it has no polynomial kernel unless the polynomial hierarchy collapses.
The algorithmic question of whether @math is connected for a given @math is addressed in @cite_3 @cite_9 , where it is shown that the problem is coNP-complete for @math and bipartite @math , but polynomial-time solvable for planar bipartite @math .
@cite_9 @cite_3
2807350215 2952621790 2091602684 2103875227
We show that any language in nondeterministic time @math , where the number of iterated exponentials is an arbitrary function @math , can be decided by a multiprover interactive proof system with a classical polynomial-time verifier and a constant number of quantum entangled provers, with completeness @math and soundness @math , where the number of iterated exponentials is @math and @math is a universal constant. The result was previously known for @math and @math ; we obtain it for any time-constructible function @math . The result is based on a compression technique for interactive proof systems with entangled provers that significantly simplifies and strengthens a protocol compression result of Ji (STOC'17). As a separate consequence of this technique we obtain a different proof of Slofstra's recent result (unpublished) on the uncomputability of the entangled value of multiprover games. Finally, we show that even minor improvements to our compression result would yield remarkable consequences in computational complexity theory and the foundations of quantum mechanics: first, it would imply that the class MIP* contains all computable languages; second, it would provide a negative resolution to a multipartite version of Tsirelson's problem on the relation between the commuting operator and tensor product models for quantum correlations. Let @math be a nontrivial @math -ary predicate. Consider a random instance of the constraint satisfaction problem @math on @math variables with @math constraints, each being @math applied to @math randomly chosen literals. Provided the constraint density satisfies @math , such an instance is unsatisfiable with high probability. The problem is to efficiently find a proof of unsatisfiability. We show that whenever the predicate @math supports a @math - probability distribution on its satisfying assignments, the sum of squares (SOS) algorithm of degree @math (which runs in time @math ) refute a random instance of @math . In particular, the polynomial-time SOS algorithm requires @math constraints to refute random instances of CSP @math when @math supports a @math -wise uniform distribution on its satisfying assignments. Together with recent work of [LRS15], our result also implies that polynomial-size semidefinite programming relaxation for refutation requires at least @math constraints. Our results (which also extend with no change to CSPs over larger alphabets) subsume all previously known lower bounds for semialgebraic refutation of random CSPs. For every constraint predicate @math , they give a three-way hardness tradeoff between the density of constraints, the SOS degree (hence running time), and the strength of the refutation. By recent algorithmic results of [AOW15] and [RRS16], this full three-way tradeoff is , up to lower-order factors. Assuming that NP @math @math BPTIME( @math ), we show that graph min-bisection, dense @math -subgraph, and bipartite clique have no polynomial time approximation scheme (PTAS). We give a reduction from the minimum distance of code (MDC) problem. Starting with an instance of MDC, we build a quasi-random probabilistically checkable proof (PCP) that suffices to prove the desired inapproximability results. In a quasi-random PCP, the query pattern of the verifier looks random in a certain precise sense. Among the several new techniques we introduce, the most interesting one gives a way of certifying that a given polynomial belongs to a given linear subspace of polynomials. As is important for our purpose, the certificate itself happens to be another polynomial, and it can be checked probabilistically by reading a constant number of its values. For a 3-colourable graph G, the 3-colour graph of G, denoted C3(G), is the graph with node set the proper vertex 3-colourings of G, and two nodes adjacent whenever the corresponding colourings differ on precisely one vertex of G. We consider the following question : given G, how easily can we decide whether or not C3(G) is connected?We show that the 3-colour graph of a 3-chromatic graph is never connected, and characterise the bipartite graphs for which C3(G) is connected. We also show that the problem of deciding the connectedness of the 3-colour graph of a bipartite graph is coNP-complete, but that restricted to planar bipartite graphs, the question is answerable in polynomial time.