Source-linked AI summary
Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal
Daniel Lokshtanov, Dániel Marx, Saket Saurabh
TL;DR
The paper asks whether exponential-time algorithms for graph problems on bounded-treewidth graphs can be improved. It proves conditional lower bounds via reductions to SAT, showing that the best known treewidth-dependent bases are essentially optimal unless SETH fails.
Problem
The paper studies whether known algorithms for graph problems on bounded-treewidth graphs can be improved beyond their exponential dependence on treewidth.
Method
The authors prove running-time lower bounds by relating faster algorithms for the graph problems to faster algorithms for SAT, thereby circumventing an obstruction to SETH-based lower bounds.
Results
Under SETH, the best known algorithms are essentially optimal for Independent Set, Dominating Set, Max Cut, Odd Cycle Transversal, q-Coloring, and Partition Into Triangles.
Takeaways & Limitations
Improving the considered bounded-treewidth algorithms would yield a faster SAT algorithm and therefore violate SETH.
Takeaways & Limitations
The lower bounds depend on the Strong Exponential Time Hypothesis, which the paper notes may not be accepted by everyone.
Abstract
from arXiv · showhide
We obtain a number of lower bounds on the running time of algorithms solving problems on graphs of bounded treewidth. We prove the results under the Strong Exponential Time Hypothesis of Impagliazzo and Paturi. In particular, assuming that SAT cannot be solved in (2-ε)^{n}m^{O(1)} time, we show that for any e > 0; {\sc Independent Set} cannot be solved in (2-e)^{tw(G)}|V(G)|^{O(1)} time, {\sc Dominating Set} cannot be solved in (3-e)^{tw(G)}|V(G)|^{O(1)} time, {\sc Max Cut} cannot be solved in (2-e)^{tw(G)}|V(G)|^{O(1)} time, {\sc Odd Cycle Transversal} cannot be solved in (3-e)^{tw(G)}|V(G)|^{O(1)} time, For any $q \geq 3$, $q$-{\sc Coloring} cannot be solved in (q-e)^{tw(G)}|V(G)|^{O(1)} time, {\sc Partition Into Triangles} cannot be solved in (2-e)^{tw(G)}|V(G)|^{O(1)} time. Our lower bounds match the running times for the best known algorithms for the problems, up to the e in the base.
1 Introduction
The paper argues that several bounded-treewidth graph algorithms are essentially optimal under SETH, because improving their exponential bases would yield a faster SAT algorithm. Its reductions carefully control treewidth, and the results also extend to bounded pathwidth.
- Lower bounds: (2−ε)^tw(G) algorithms for INDEPENDENT SET and MAX CUT would imply an O∗((2−δ)^n) SAT algorithm.The reduction framework relates improvements in these graph problems directly to violating SETH.
- Lower bounds: (3−ε)^tw(G) algorithms for DOMINATING SET and ODD CYCLE TRANSVERSAL would imply an O∗((2−δ)^n) SAT algorithm.The same implication applies to both problems, with base 3 as the threshold.
- Lower bounds: For q ≥ 3, a (q−ε)^tw(G) algorithm for q-COLORING would imply an O∗((2−δ)^n) SAT algorithm.The result preserves the number of colors q in the exponential base.
- Lower bounds: (2−ε)^tw(G) algorithms for PARTITION INTO TRIANGLES would imply an O∗((2−δ)^n) SAT algorithm.This matches the best known running-time base reported for the problem.
- Reduction strategy: The reductions use polynomial-time many-one transformations and tightly bound output treewidth through pathwidth, with each variable increasing treewidth by less than one.The construction aims to maximize combinatorial possibilities per unit increase in treewidth.
- Complexity assumption: SETH asserts that SAT lacks a (2−δ)^n algorithm, while the paper explains that sparsification is unnecessary for these bounded-treewidth lower bounds.The paper connects specific graph problems to the basic question of whether SAT admits faster exponential-time algorithms.
2 Preliminaries
This section introduces graph substructures, neighborhoods, tree decompositions, treewidth, pathwidth, mixed search games, and SAT assignments used throughout the paper.
- Graph definitions: An induced subgraph G[V′] contains exactly the edges of G whose endpoints both lie in V′.It is formed by restricting the vertex set and retaining all internal edges.
- Graph definitions: The closed neighborhood N[D] contains every vertex in D together with all vertices adjacent to vertices in D.For a single vertex u, N[u] = N(u) ∪ {u}.
- Treewidth and pathwidth: A tree decomposition assigns vertex subsets to a tree so every graph edge appears in a bag and bags containing each vertex form a connected subtree.Its width is the largest bag size minus one; treewidth is the minimum such width.
- Treewidth and pathwidth: Pathwidth is the restricted form of treewidth in which the decomposition tree is required to be a path.The paper denotes pathwidth by pw(G).
- Mixed search games: In a mixed search game, searchers clear contaminated edges by simultaneous endpoint placement or by sliding along edges, while contamination can return through unguarded paths.This game is introduced as a graph-search formulation used in the paper’s preliminaries.
- SAT notation: A SAT instance is a conjunction of clauses over Boolean variables, and an assignment satisfies it when every clause has a literal assigned 1.Assignments are elements of {0,1}^n.
3 Independent Set
The Independent Set reduction encodes variable assignments with paths and clause satisfaction with clause gadgets, while keeping pathwidth at most n + 4. Its correctness yields a SAT-based lower bound ruling out any O*((2 − ε)^tw(G)) algorithm under the stated assumption.
- Lower bound: If Independent Set were solvable in O*((2 − ε)^tw(G)) time, SAT would be solvable in O*((2 − δ)^n) time for some δ > 0.The construction, correctness lemmas, and width bound together establish the contradiction-based lower bound.
- Construction: A clause gadget with c literals has maximum independent-set size c + 2, and every literal can be selected in such a set while excluding the others.Because c is even, every independent set of size c + 2 contains at least one literal vertex.
- Construction: The reduction builds n variable paths of length 2m and attaches a clause gadget to each clause occurrence.Each path represents one variable, and edges connect path positions to literal vertices according to positive or negative occurrences.
- Correctness: A satisfying assignment produces an independent set of size (mn + Σ_i≤m |Ci| + 2)(n + 1).The construction selects alternating vertices on each variable path and a compatible maximum independent set in every clause gadget.
- Correctness: An independent set of that size forces a consistent alternating choice on the variable paths, which can be decoded into a satisfying assignment.The proof uses the connected copies of each path and the pigeon-hole principle to find one copy encoding all variables consistently.
- Width bound: The constructed graph has pathwidth at most n + 4.A mixed search strategy uses n path searchers plus three temporary gadget searchers, followed by Proposition 1.
4 Dominating Set
The Dominating Set reduction groups variables into small blocks represented by group gadgets arranged in long paths, with clause vertices enforcing satisfied assignments. The construction supports decoding in both directions and gives a SAT-based lower bound at base 3.
- Lower bound: If Dominating Set were solvable in O*((3 − ε)^pw(G)) time, SAT would be solvable in O*((2 − δ)^n) time for some δ > 0.The proof chooses p based on ε and combines the construction's width bound with the two correctness lemmas.
- Construction: Variables are grouped into blocks of size at most β = floor(log 3^p), giving t = ceil(n/β) groups.The integer p depends only on ε, and the number of available gadget subsets is sufficient to encode every group assignment.
- Construction: Each group gadget contains p paths and assignment-selector vertices xS and x′S, with guards and a clique controlling domination.A selector S picks exactly one vertex from each path and corresponds to an assignment of the group variables.
- Construction: Copies of each group gadget are arranged path-like, while clause vertices connect to selectors representing group assignments that satisfy the clause.Each clause receives 2pt + 1 private vertices distributed across the gadget copies.
- Correctness: A satisfying assignment yields a dominating set of size (p + 1)tm(2pt + 1) + 1.The set contains h and, in every group gadget, the selector for the restricted assignment together with its associated x′S vertex.
- Correctness: Any dominating set of that size contains exactly p + 1 vertices per group gadget and can be decoded into assignments for all variable groups.A pigeon-hole argument identifies a block of gadget copies with unchanged path selections across every group.
- Correctness: The decoded assignments satisfy every clause because the corresponding selector is connected to the clause vertex in the construction.The proof reads one stable gadget block and uses its selector choices as the assignments restricted to each group.
5 Max Cut
The Max Cut reduction transforms SAT formulas into weighted and then unweighted graph instances while controlling pathwidth. This yields a SAT-based lower bound matching the known (2−ε)^pw(G) dependence.
- Lower bound: If MAX CUT is solvable in O∗((2−ε)^pw(G)) time, then SAT is solvable in O∗((2−δ)^n) time for some δ>0.The theorem applies to unweighted MAX CUT parameterized by pathwidth.
- Construction: The reduction first constructs a weighted MAX CUT instance with one variable vertex and one clause gadget for each clause.Each clause gadget contains a path with 4|Cj| vertices, edge weights 3n, and links to a distinguished vertex x0.
- Correctness: A satisfying assignment produces a cut of weight at least t by placing variable vertices according to truth values and selecting one true literal per clause path.The selected literal determines where two consecutive path vertices lie on the same side, while the remaining path vertices alternate sides.
- Correctness: Conversely, any cut meeting the threshold forces every clause gadget to encode a satisfied clause, yielding a satisfying SAT assignment.The gadget’s weight structure limits how many incident edges can fail to cross, so reaching the threshold identifies a literal whose assignment satisfies the clause.
- Unweighted conversion: Weighted edges are eliminated by replacing each edge of weight we with we length-three paths, shifting the target cut size to 2W+t.The replacement preserves the threshold equivalence between weighted and unweighted instances.
- Pathwidth: The resulting graph has pathwidth at most n+5, established through a mixed-search strategy using n+5 searchers.The strategy places searchers on variable vertices and x0, then processes clause gadgets sequentially.
6 Graph Coloring
The coloring reduction encodes grouped SAT assignments as colorings of vertex sets and uses clause paths with connectors to enforce consistency. It proves lower bounds for q-COLORING under both feedback vertex set and pathwidth parameterizations.
- Lower bound: If q-COLORING is solvable in O∗((q−ε)^fvs(G)) or O∗((3−ε)^pw(G)) time, then SAT is solvable in O∗((2−δ)^n) time.The theorem covers q-COLORING through a list-coloring construction and a reduction back to ordinary coloring.
- Variable encoding: The construction groups SAT variables into sets Fi and represents each group Fi by a set Vi of p vertices whose coloring encodes a group assignment.There are q^p possible colorings of Vi, enough to assign distinct colorings to the group assignments.
- Clause gadgets: Each clause gadget contains a path with one vertex for every group assignment satisfying the clause, and red marks the selected satisfying assignment.The path endpoints receive fixed white or black lists, forcing at least one red vertex; its position identifies how the clause is satisfied.
- Connectors: A connector links a clause-path vertex to a variable group and enforces that the path vertex can be red only when the corresponding group coloring is present.The connector supports arbitrary white or black colors at the path vertex, while red requires the matching coloring on Vi.
- Correctness: The construction is correct in both directions: satisfiable formulas yield proper list-colorings, and every proper list-coloring yields a satisfying assignment.These directions are stated in Lemmas 12 and 13.
- Parameter control: The union of the group vertex sets forms a feedback vertex set, while the constructed graph has pathwidth at most pt+4.This parameter control transfers the assumed coloring running times into a faster-than-2^n SAT algorithm.
7 Odd Cycle Transversal
The paper reduces SAT to Odd Cycle Transversal while tightly controlling pathwidth, showing that any improvement below base 3 in the pathwidth exponent would yield a faster-than-2^n SAT algorithm.
- An odd cycle transversal is a vertex set whose deletion leaves a bipartite graph; the problem asks whether one of size k exists.
- Lower bound: The construction proves that an O*((3 − ε)^pw(G)) Odd Cycle Transversal algorithm would solve SAT in O*((2 − δ)^n) time for some δ > 0.The same lower bound applies to treewidth because tw(G) ≤ pw(G).
- Construction: The reduction groups variables into blocks and represents each group assignment by a selected good subset of a path gadget.Each group has at most ⌊log 3^p⌋ variables, while good subsets provide at least 3^p ≥ 2^h possibilities.
- Construction: The arrow gadget makes selecting its source enable selecting its target without additional budget, while preserving bipartite structure after deletion.Its passive transversal is {a1, a3}; when the source is deleted, {a2, v} is a smallest transversal.
- Correctness: The constructed graph uses paths, odd cycles, and clause gadgets so feasible transversals encode group assignments satisfying every clause.The satisfiable direction constructs a transversal of budget α, and the converse recovers a satisfying assignment from any transversal of that size.
8 Partition Into Triangles
The Partition Into Triangles lower bound is obtained by first encoding SAT with triangle packing and then forcing a full partition, while keeping pathwidth near the number of variables.
- A triangle packing is a collection of pairwise vertex-disjoint vertex sets, each inducing a triangle; Partition Into Triangles requires covering the graph with such triangles.
- Lower bound: Therefore, an O*((2 − ε)^pw(G)) algorithm for Partition Into Triangles would yield an O*((2 − δ)^n) SAT algorithm for some δ > 0.Lemmata 18–21 establish the packing equivalence, reverse implication, partition transformation, and pathwidth bound.
- Construction: The SAT reduction creates one path per variable and clause gadgets whose selectable triangles encode truth assignments and satisfied literals.The variable paths have 2m(n + 1) + 1 vertices, and each clause receives n + 1 gadgets.
- Triangle Packing: A satisfying assignment yields a triangle packing of size mn(n + 1) + m(n + 1).True and false variable values select alternating triangles, while satisfied clause literals supply the remaining clause-gadget triangles.
- Triangle Packing: Conversely, a packing of that size forces a consistent assignment satisfying every clause.The packing structure selects alternating variable triangles, and each clause gadget must connect to a literal compatible with that assignment.
- Partition Into Triangles: Adding four-vertex cliques converts the packing instance into G′, with G having a packing of size t if and only if G′ has a triangle partition.The transformation preserves the intended packing through completion triangles and has pathwidth at most n + 10.
9 Conclusion
The paper concludes that the best known exponential bases for several bounded-treewidth graph problems are optimal under SETH. It also identifies planar graphs and alternative parameters as open directions.
- For several basic graph problems, the best known algorithms have optimal exponential dependence on treewidth under the paper’s assumption.The conclusion explicitly characterizes the exponential base as best possible.
- The recent use of fast subset sum convolutions for Dominating Set and Partition Into Triangles made possible algorithmic improvements that the lower bounds now constrain.
- The results connect specific bounded-treewidth graph problems to the possibility of faster SAT algorithms under SETH.The authors state that improving the considered algorithms would disprove SETH.
- Open questions include tight lower bounds for planar graphs and problems parameterized by measures other than treewidth.