We identify a sufficient condition, treewidth-pliability , that gives a polynomial-time algorithm for an arbitrarily good approximation of the optimal value in a large class of Max-2-CSPs parameterised by the class of allowed constraint graphs (with arbitrary constraints on an unbounded alphabet). Our result applies more generally to the maximum homomorphism problem between two rational-valued structures. The condition unifies the two main approaches for designing a polynomial-time approximation scheme. One is Baker’s layering technique, which applies to sparse graphs such as planar or excluded-minor graphs. The other is based on Szemerédi’s regularity lemma and applies to dense graphs. We extend the applicability of both techniques to new classes of Max-CSPs. However, we prove that the condition cannot be used to find solutions (as opposed to approximating the optimal value) in general. Treewidth-pliability turns out to be a robust notion that can be defined in several equivalent ways, including characterisations via size, treedepth, or the Hadwiger number. We show connections to the notions of fractional-treewidth-fragility from structural graph theory, hyperfiniteness from the area of property testing, and regularity partitions from the theory of dense graph limits. These may be of independent interest. In particular, we show that a monotone class of graphs is hyperfinite if and only if it is fractionally-treewidth-fragile and has bounded degree.

Abstract. The approximate graph coloring problem, whose complexity is unresolved in most cases, concerns finding a [Formula: see text]-coloring of a graph that is promised to be [Formula: see text]-colorable, where [Formula: see text]. This problem naturally generalizes to promise graph homomorphism problems and further to promise constraint satisfaction problems. The complexity of these problems has recently been studied through an algebraic approach. In this paper, we introduce two new techniques to analyze the complexity of promise CSPs: one is based on topology and the other on adjunction. We apply these techniques, together with the previously introduced algebraic approach, to obtain new unconditional NP-hardness results for a significant class of approximate graph coloring and promise graph homomorphism problems.

We study polynomial-time approximation schemes (PTASes) for constraint satisfaction problems (CSPs) such as Maximum Independent Set or Minimum Vertex Cover on sparse graph classes. Baker’s approach gives a PTAS on planar graphs, excluded-minor classes, and beyond. For Max-CSPs, and even more generally, maximisation finite-valued CSPs (where constraints are arbitrary non-negative functions), Romero, Wrochna, and Živný [SODA’21] showed that the Sherali-Adams LP relaxation gives a simple PTAS for all fractionally-treewidth-fragile classes, which is the most general “sparsity” condition for which a PTAS is known. We extend these results to general-valued CSPs, which include “crisp” (or “strict”) constraints that have to be satisfied by every feasible assignment. The only condition on the crisp constraints is that their domain contains an element that is at least as feasible as all the others (but possibly less valuable). For minimisation general-valued CSPs with crisp constraints, we present a PTAS for all Baker graph classes—a definition by Dvořák [SODA’20] that encompasses all classes where Baker’s technique is known to work, except for fractionally-treewidth-fragile classes. While this is standard for problems satisfying a certain monotonicity condition on crisp constraints, we show this can be relaxed to diagonalisability —a property of relational structures connected to logics, statistical physics, and random CSPs.

We study polynomial-time approximation schemes (PTASes) for constraint satisfaction problems (CSPs) such as Maximum Independent Set or Minimum Vertex Cover on sparse graph classes.Baker's approach gives a PTAS on planar graphs, excluded-minor classes, and beyond. For Max-CSPs, and even more generally, maximisation finite-valued CSPs (where constraints are arbitrary non-negative functions), Romero, Wrochna, and Živný [SODA'21] showed that the Sherali-Adams LP relaxation gives a simple PTAS for all fractionally-treewidth-fragile classes, which is the most general "sparsity" condition for which a PTAS is known. We extend these results to general-valued CSPs, which include "crisp" (or "strict") constraints that have to be satisfied by every feasible assignment. The only condition on the crisp constraints is that their domain contains an element which is at least as feasible as all the others (but possibly less valuable).For minimisation general-valued CSPs with crisp constraints, we present a PTAS for all Baker graph classes - a definition by Dvořák [SODA'20] which encompasses all classes where Baker's technique is known to work, except for fractionally-treewidth-fragile classes. While this is standard for problems satisfying a certain monotonicity condition on crisp constraints, we show this can be relaxed to diagonalisability - a property of relational structures connected to logics, statistical physics, and random CSPs.

We identify a sufficient condition, treewidth-pliability, that gives a polynomial-time approximation scheme (PTAS) for a large class of Max-2-CSPs parametrised by the class of allowed constraint graphs (with arbitrary constraints on an unbounded alphabet). Our result applies more generally to the maximum homomorphism problem between two rational-valued structures. The condition unifies the two main approaches for designing PTASes. One is Baker's layering technique, which applies to sparse graphs such as planar or excluded-minor graphs. The other is based on Szemerédi's regularity lemma and applies to dense graphs. We extend the applicability of both techniques to new classes of Max-CSPs. Treewidth-pliability turns out to be a robust notion that can be defined in several equivalent ways, including characterisations via size, treedepth, or the Hadwiger number. We show connections to the notions of fractional-treewidth-fragility from structural graph theory, hyperfiniteness from the area of property testing, and regularity partitions from the theory of dense graph limits. These may be of independent interest. In particular we show that a monotone class of graphs is hyperfinite if and only if it is fractionally-treewidth-fragile and has bounded degree. The full version [59] containing detailed proofs is available at https://arxiv.org/abs/1911.03204.

Suppose ${\mathcal{F}}$ is a finite family of graphs. We consider the following meta-problem, called $\mathcal{F}$-Immersion Deletion: given a graph $G$ and integer $k$, decide whether the deletion of at most $k$ edges of $G$ can result in a graph that does not contain any graph from $\mathcal{F}$ as an immersion. This problem is a close relative of the $\mathcal{F}$-Minor Deletion problem studied by Fomin et al. [ Proceedings of FOCS, IEEE, 2012, pp. 470--479], where one deletes vertices in order to remove all minor models of graphs from $\mathcal{F}$. We prove that whenever all graphs from $\mathcal{F}$ are connected and at least one graph of $\mathcal{F}$ is planar and subcubic, then the $\mathcal{F}$-Immersion Deletion problem admits a constant-factor approximation algorithm running in time $\mathcal{O}(m^3 \cdot n^3 \cdot \log m)$, a linear kernel that can be computed in time $\mathcal{O}(m^4 \cdot n^3 \cdot \log m)$, and a $\mathcal{O}(2^{\mathcal{O}(k)} + m^4 \cdot n^3 \cdot \log m)$-time fixed-parameter algorithm, where $n,m$ count the vertices and edges of the input graph. These results mirror the findings of Fomin et al., who obtained a similar set of algorithmic results for $\mathcal{F}$-Minor Deletion, under the assumption that at least one graph from $\mathcal{F}$ is planar. An important difference is that we are able to obtain a linear kernel for $\mathcal{F}$-Immersion Deletion, while the exponent of the kernel of Fomin et al. for $\mathcal{F}$-Minor Deletion depends heavily on the family $\mathcal{F}$. In fact, this dependence is unavoidable under plausible complexity assumptions, as proven by Giannopoulou et al. [ ACM Trans. Algorithms, 13 (2017), p. 35]. This reveals that the kernelization complexity of $\mathcal{F}$-Immersion Deletion is quite different from that of $\mathcal{F}$-Minor Deletion.

While 3-SAT is NP-hard, 2-SAT is solvable in polynomial time. Austrin, Guruswami, and Håstad [FOCS'14/SICOMP'17] proved a result known as "(2+ε)-SAT is NP-hard". They showed that the problem of distinguishing k-CNF formulas that are g-satisfiable (i.e. some assignment satisfies at least g literals in every clause) from those that are not even 1-satisfiable is NP-hard if g/k < 1/2 and is in P otherwise. We study a generalisation of SAT on arbitrary finite domains, with clauses that are disjunctions of unary constraints, and establish analogous behaviour. Thus we give a dichotomy for a natural fragment of promise constraint satisfaction problems (PCSPs) on arbitrary finite domains.

An algorithm for finding treedepth decompositions

We present new results on approximate colourings of graphs and, more generally, approximate H-colourings and promise constraint satisfaction problems. First, we show NP-hardness of colouring k-colourable graphs with colours for every k ≥ 4. This improves the result of Bulín, Krokhin, and Opršal [STOC'19], who gave NP-hardness of colouring k-colourable graphs with 2k – 1 colours for k ≥ 3, and the result of Huang [APPROX-RANDOM'13], who gave NP-hardness of colouring k-colourable graphs with colours for sufficiently large k. Thus, for k ≥ 4, we improve from known linear/sub-exponential gaps to exponential gaps. Second, we show that the topology of the box complex of H alone determines whether H-colouring of G-colourable graphs is NP-hard for all (non-bipartite, H-colourable) G. This formalises the topological intuition behind the result of Krokhin and Opršal [FOCS’19] that 3-colouring of G-colourable graphs is NP-hard for all (3-colourable, non-bipartite) G. We use this technique to establish NP-hardness of H-colouring of G-colourable graphs for H that include but go beyond K3, including square-free graphs and circular cliques (leaving K4 and larger cliques open). Underlying all of our proofs is a very general observation that adjoint functors give reductions between promise constraint satisfaction problems. The full version [55] containing detailed proofs is available at https://arxiv.org/abs/1907.00872.

In the field of constraint satisfaction problems (CSPs), promise CSPs are an exciting new direction of study. In a promise CSP, each constraint comes in two forms: “strict” and “weak,” and in the associated decision problem one must distinguish between being able to satisfy all the strict constraints versus not being able to satisfy all the weak constraints. The most commonly cited example of a promise CSP is the approximate graph coloring problem-which has recently seen exciting progress [Bulín, Krokhin, and Oprs̆al, Proceedings of the Symposium on Theory of Computing, 2019, pp. 602--613 and Wrochna and Živný, Proceedings of the Symposium on Discrete Algorithms, 2020, pp. 1426--1435] benefiting from a systematic algebraic approach to promise CSPs based on “polymorphisms,” operations that map tuples in the strict form of each constraint to tuples in the corresponding weak form. In this work, we present a simple algorithm which in polynomial time solves the decision problem for all promise CSPs that admit infinitely many symmetric polymorphisms, which are invariant under arbitrary coordinate permutations. This generalizes previous work of the first two authors [Brakensiek and Guruswami, Proceedings of the Symposium on Discrete Algorithms, 2019, pp. 436--455]. We also extend this algorithm to a more general class of block-symmetric polymorphisms. As a corollary, this single algorithm solves all polynomial-time tractable Boolean CSPs simultaneously. These results give a new perspective on Schaefer's classic dichotomy theorem and shed further light on how symmetries of polymorphisms enable algorithms. Finally, we show that block symmetric polymorphisms are not only sufficient but also necessary for this algorithm to work, thus establishing its precise power.

For a fixed graph H, we consider the H-Recoloring problem: given a graph G and two H-colorings of G, i.e., homomorphisms from G to H, can one be transformed into the other by changing one color at a time, maintaining an H-coloring throughout. This is the same as finding a path in the Hom(G,H) complex. For H=K_k this is the problem of finding paths between k-colorings, which was recently shown to be in P for kłeq 3 and PSPACE-complete otherwise. We generalize the positive side of this dichotomy by providing an algorithm that solves the problem in polynomial time for any H with no C_4 subgraph. This gives a large class of constraints for which finding solutions to the Constraint Satisfaction Problem is NP-complete but finding paths in the solution space is in P. The algorithm uses a characterization of possible reconfiguration sequences (paths in Hom(G,H)), whose main part is a purely topological condition described in terms of the fundamental groupoid of H seen as a topological space.

Cutwidth is one of the classic layout parameters for graphs. It measures how well one can order the vertices of a graph in a linear manner, so that the maximum number of edges between any prefix and its complement suffix is minimized. As graphs of cutwidth at most k are closed under taking immersions, the results of Robertson and Seymour imply that there is a finite list of minimal immersion obstructions for admitting a cut layout of width at most k. We prove that every minimal immersion obstruction for cutwidth at most k has size at most $$2^{{O}(k^3\log k)}$$ . As an interesting algorithmic byproduct, we design a new fixed-parameter algorithm for computing the cutwidth of a graph that runs in time $$2^{{O}(k^2\log k)}\cdot n$$ , where k is the optimum width and n is the number of vertices. While being slower by a $$\log k$$ -factor in the exponent than the fastest known algorithm, given by Thilikos et al. (J Algorithms 56(1):1–24, 2005; J Algorithms 56(1):25–49, 2005), our algorithm has the advantage of being simpler and self-contained; arguably, it explains better the combinatorics of optimum-width layouts.

The notion of Turing kernelization investigates whether a polynomial-time algorithm can solve an NP-hard problem, when it is aided by an oracle that can be queried for the answers to bounded-size subproblems. One of the main open problems in this direction is whether $$k$$ -Path admits a polynomial Turing kernel: can a polynomial-time algorithm determine whether an undirected graph has a simple path of length k, using an oracle that answers queries of size $$k^{\mathscr {O} (1)}$$ ? We show this can be done when the input graph avoids a fixed graph H as a topological minor, thereby significantly generalizing an earlier result for bounded-degree and $$K_{3,t}$$ -minor-free graphs. Moreover, we show that $$k$$ -Path even admits a polynomial Turing kernel when the input graph is not H-topological-minor-free itself, but contains a known vertex modulator of size bounded polynomially in the parameter, whose deletion makes it so. To obtain our results, we build on the graph minors decomposition to show that any H-topological-minor-free graph that does not contain a k-path, has a separation that can safely be reduced after communication with the oracle.

In the Edge Bipartization problem one is given an undirected graph G and an integer k, and the question is whether k edges can be deleted from G so that it becomes bipartite. Guo et al. (J Comput Syst Sci 72(8):1386–1396, 2006) proposed an algorithm solving this problem in time $$\mathcal {O}(2^k\cdot {m}^2)$$ ; today, this algorithm is a textbook example of an application of the iterative compression technique. Despite extensive progress in the understanding of the parameterized complexity of graph separation problems in the recent years, no significant improvement upon this result has been yet reported. We present an algorithm for Edge Bipartization that works in time $$\mathcal {O}(1.977^k\cdot {nm})$$ , which is the first algorithm with the running time dependence on the parameter better than $$2^k$$ . To this end, we combine the general iterative compression strategy of Guo et al. (2006), the technique proposed by Wahlström (in: Proceedings of SODA’14, SIAM, 2014) of using a polynomial-time solvable relaxation in the form of a Valued Constraint Satisfaction Problem to guide a bounded-depth branching algorithm, and an involved Measure&Conquer analysis of the recursion tree.

A graph $K$ is multiplicative if a homomorphism from any product $G \times H$ to $K$ implies a homomorphism from $G$ or from $H$. Hedetniemi's conjecture stated that all cliques are multiplicative. In an attempt to explore the boundaries of current methods, we investigate strongly multiplicative graphs, which we define as graphs $K$ such that for any connected graphs $G,H$ with odd cycles $C,C'$, a homomorphism from $(G \times C') \cup (C \times H) \subseteq G \times H$ to $K$ implies a homomorphism from $G$ or $H$. Strong multiplicativity of $K$ also implies the following property, which may be of independent interest: If $G$ is nonbipartite, $H$ is a connected graph with a vertex $h$, and there is a homomorphism $\phi\!: G \times H \rightarrow K$ such that $ \phi(-,h)$ is constant, then $H$ admits a homomorphism to $K$. All graphs currently known to be multiplicative are strongly multiplicative. We revisit the proofs in a different view based on covering graphs and replace fragments with more combinatorial arguments. This allows us to find new (strongly) multiplicative graphs: all graphs in which every edge is in at most one square, and the third power of any graph of girth $>$ 12. Though more graphs are amenable to our methods, they still make no progress for the case of cliques. Instead we hope to understand their limits, perhaps hinting at ways to further extend them.

We investigate the complexity of several fundamental polynomial-time solvable problems on graphs and on matrices, when the given instance has low treewidth; in the case of matrices, we consider the treewidth of the graph formed by non-zero entries. In each of the considered cases, the best known algorithms working on general graphs run in polynomial time; however, the exponent of the polynomial is large. Therefore, our main goal is to construct algorithms with running time of the form poly( k )⋅ n or poly( k )⋅ n log n , where k is the width of the tree decomposition given on the input. Such procedures would outperform the best known algorithms for the considered problems already for moderate values of the treewidth, like O ( n 1/ c ) for a constant c . Our results include the following: — an algorithm for computing the determinant and the rank of an n × n matrix using O ( k 3 ⋅ n ) time and arithmetic operations; —an algorithm for solving a system of linear equations using O ( k 3 ⋅ n ) time and arithmetic operations; —an O ( k 3 ⋅ n log n )-time randomized algorithm for finding the cardinality of a maximum matching in a graph; —an O ( k 4 ⋅ n log 2 n )-time randomized algorithm for constructing a maximum matching in a graph; —an O ( k 2 ⋅ n log n )-time algorithm for finding a maximum vertex flow in a directed graph. Moreover, we give an approximation algorithm for treewidth with time complexity suited to the running times as above. Namely, the algorithm, when given a graph G and integer k , runs in time O ( k 7 ⋅ n log n ) and either correctly reports that the treewidth of G is larger than k , or constructs a tree decomposition of G of width O ( k 2 ). The above results stand in contrast with the recent work of Abboud et al. (SODA 2016), which shows that the existence of algorithms with similar running times is unlikely for the problems of finding the diameter and the radius of a graph of low treewidth.

The notion of Turing kernelization investigates whether a polynomial-time algorithm can solve an NP-hard problem, when it is aided by an oracle that can be queried for the answers to bounded-size subproblems. One of the main open problems in this direction is whether k-PATH admits a polynomial Turing kernel: can a polynomial-time algorithm determine whether an undirected graph has a simple path of length k, using an oracle that answers queries of size k^{O(1)}? We show this can be done when the input graph avoids a fixed graph H as a topological minor, thereby significantly generalizing an earlier result for bounded-degree and K_{3,t}-minor-free graphs. Moreover, we show that k-PATH even admits a polynomial Turing kernel when the input graph is not H-topological-minor-free itself, but contains a known vertex modulator of size bounded polynomially in the parameter, whose deletion makes it so. To obtain our results, we build on the graph minors decomposition to show that any H-topological-minor-free graph that does not contain a k-path has a separation that can safely be reduced after communication with the oracle.

We investigate the complexity of several fundamental polynomial-time solvable problems on graphs and on matrices, when the given instance has low treewidth; in the case of matrices, we consider the treewidth of the graph formed by non-zero entries. In each of the considered cases, the best known algorithms working on general graphs run in polynomial, but far from linear, time. Thus, our goal is to construct algorithms with running time of the form poly(k) · n or poly(k) · n log n, where k is the width of the tree decomposition given on the input. Such procedures would outperform the best known algorithms for the considered problems already for moderate values of the treewidth, like O(n1/c) for some small constant c. Our results include: an algorithm for computing the determinant and the rank of an n × n matrix using O(k3 · n) time and arithmetic operations;an algorithm for solving a system of linear equations using O(k3 · n) time and arithmetic operations;an O(k3 · n log n)-time randomized algorithm for finding the cardinality of a maximum matching in a graph;an O(k4 · nlog2 n)-time randomized algorithm for constructing a maximum matching in a graph;an O(k2 · n log n)-time algorithm for finding a maximum vertex flow in a directed graph. Moreover, we provide an approximation algorithm for treewidth with time complexity suited to the running times as above. Namely, the algorithm, when given a graph G and integer k, runs in time O(k2 · n log n) and either correctly reports that the treewidth of G is larger than k, or constructs a tree decomposition of G of width O(k2). The above results stand in contrast with the recent work of Abboud et al. [SODA 2016], which shows that the existence of algorithms with similar running times is unlikely for the problems of finding the diameter and the radius of a graph of low treewidth.

A graph is called {claw,diamond}-free if it contains neither a claw (a K 1,3) nor a diamond (a K 4 with an edge removed) as an induced subgraph. Equivalently, {claw,diamond}-free graphs are characterized as line graphs of triangle-free graphs, or as linear dominoes (graphs in which every vertex is in at most two maximal cliques and every edge is in exactly one maximal clique). We consider the parameterized complexity of the {claw,diamond}-free Edge Deletion problem, where given a graph G and a parameter k, the question is whether one can remove at most k edges from G to obtain a {claw,diamond}-free graph. Our main result is that this problem admits a polynomial kernel. We complement this result by proving that, even on instances with maximum degree 6, the problem is NP-complete and cannot be solved in time $2^{o(k)}\cdot |V(G)|^{\mathcal {O}(1)}$ unless the Exponential Time Hypothesis fails.

In the EDGE BIPARTIZATION problem one is given an undirected graph G and an integer k, and the question is whether k edges can be deleted from G so that it becomes bipartite. In 2006, Guo et al. [J. Comput. Syst. Sci., 72(8):1386-1396, 2006] proposed an algorithm solving this problem in time O(2^k m^2); today, this algorithm is a textbook example of an application of the iterative compression technique. Despite extensive progress in the understanding of the parameterized complexity of graph separation problems in the recent years, no significant improvement upon this result has been yet reported. We present an algorithm for Edge Bipartization that works in time O(1.977^k nm), which is the first algorithm with the running time dependence on the parameter better than 2^k. To this end, we combine the general iterative compression strategy of Guo et al. [J. Comput. Syst. Sci., 72(8):1386-1396, 2006], the technique proposed by Wahlström [SODA'14] of using a polynomial-time solvable relaxation in the form of a Valued Constraint Satisfaction Problem to guide a bounded-depth branching algorithm, and an involved Measure&Conquer analysis of the recursion tree.