PaperlayerView exact revision on arXiv

Source-linked AI summary

Solving connectivity problems parameterized by treewidth in single exponential time

Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan van Rooij, Jakub Onufry Wojtaszczyk

arXiv:1103.0534v1cs.DS

TL;DR

Connectivity constraints made treewidth-based graph algorithms substantially slower than local problems. The paper introduces randomized Cut&Count algorithms that recover single-exponential dependence for most connectivity-type problems, while identifying maximization problems where such improvement is unlikely.

  • Problem

    Global constraints such as connectivity led to algorithms running in tw(G)^O(tw(G))|V|^O(1), weakening their usefulness in broader graph-algorithmic applications.

  • Method

    Cut&Count uses randomization to handle connectivity-type problems, producing randomized algorithms with runtime c^tw(G)|V|^O(1) and allowing false negatives with probability at most 1/2 when a solution exists.

  • Results

    Cut&Count yields single-exponential algorithms for most connectivity-type problems, while several component-maximization problems remain unlikely to admit c^tw(G)|V|^O(1) algorithms under standard exponential-time assumptions.

  • Takeaways & Limitations

    The results establish a marked complexity difference between minimizing and maximizing the number of connected components, and show that some connectivity costs are intrinsic rather than artifacts of the technique.

  • Takeaways & Limitations

    The technique fails for CYCLE PACKING and MAX CYCLE COVER, while optimal-constant analyses depend on the particular problem rather than a general theorem.

Abstract

from arXiv · show

For the vast majority of local graph problems standard dynamic programming techniques give c^tw V^O(1) algorithms, where tw is the treewidth of the input graph. On the other hand, for problems with a global requirement (usually connectivity) the best-known algorithms were naive dynamic programming schemes running in tw^O(tw) V^O(1) time. We breach this gap by introducing a technique we dubbed Cut&Count that allows to produce c^tw V^O(1) Monte Carlo algorithms for most connectivity-type problems, including Hamiltonian Path, Feedback Vertex Set and Connected Dominating Set, consequently answering the question raised by Lokshtanov, Marx and Saurabh [SODA'11] in a surprising way. We also show that (under reasonable complexity assumptions) the gap cannot be breached for some problems for which Cut&Count does not work, like CYCLE PACKING. The constant c we obtain is in all cases small (at most 4 for undirected problems and at most 6 for directed ones), and in several cases we are able to show that improving those constants would cause the Strong Exponential Time Hypothesis to fail. Our results have numerous consequences in various fields, like FPT algorithms, exact and approximate algorithms on planar and H-minor-free graphs and algorithms on graphs of bounded degree. In all these fields we are able to improve the best-known results for some problems.

1 Introduction and notation

Cut&Count uses randomization to reduce many connectivity-type problems from treewidth-dependent dynamic programs to c^tw n^O(1) algorithms. The paper gives small bases, matching lower bounds for several problems, and consequences for bounded-degree, planar, and H-minor-free graphs.

  • Our results: Cut&Count gives randomized c^tw|V|^O(1) algorithms for most connectivity-type problems, including Hamiltonian Path, Feedback Vertex Set, and Connected Dominating Set.The technique is described as answering the question of whether earlier 2^O(tw log tw) algorithms were optimal.
  • Our results: 4^t|V|^O(1) algorithms cover Connected Dominating Set, Connected Feedback Vertex Set, Connected Odd Cycle Transversal, and several undirected problems.The listed undirected problems include Min Cycle Cover, Longest Path, Longest Cycle, Exact k-Leaf Spanning Tree, Maximum Full Degree Spanning Tree, and Graph Metric Travelling Salesman Problem.
  • Our results: 6^t|V|^O(1) algorithms solve directed Min Cycle Cover, Longest Path, Longest Cycle, and Exact k-Leaf Outbranching.The corresponding undirected Longest Path and Longest Cycle algorithms use 4^t|V|^O(1).
  • Lower bounds: Matching lower bounds show that several bases cannot be improved under the Strong Exponential Time Hypothesis.For Steiner Tree on path decompositions, no (3−ε)^p|V|^O(1) algorithm exists unless SETH is false; analogous lower bounds cover several connected problems.
  • Lower bounds: Cut&Count fails for Cycle Packing and Max Cycle Cover, for which no 2^o(p log p)|V|^O(1) algorithm exists unless the Exponential Time Hypothesis is false.The paper identifies a marked difference between minimizing and maximizing the number of connected components.

2 Preliminaries and notation

The preliminaries define graph, cut, neighborhood, degree, decomposition, and weighting notation, then introduce nice tree decompositions and isolation-based parity counting.

  • Cuts and graph notation: A consistent cut separates vertices so that no edge crosses its two sides; consistently cut subgraphs pair such cuts with selected vertex or edge sets.
  • Tree decompositions: A tree decomposition represents a graph using bags satisfying vertex-containment and path-continuity properties; treewidth is the largest bag size minus one.
  • Nice tree decompositions: Nice tree decompositions use empty root and leaf bags together with introduce-vertex, introduce-edge, forget, and join bags.Every graph edge is introduced exactly once.
  • Bag-associated subgraphs: For each decomposition bag, Vx contains vertices appearing in descendants, while Ex contains edges introduced in descendants.
  • Isolation and parity: Random weights isolate a unique minimum-weight member of a nonempty set family with high probability, enabling parity-based counting modulo two.Polynomial-identity testing over characteristic two is presented as an alternative with similar consequences.

3 Cut&Count: Illustration of the technique

Cut&Count relaxes connectivity, counts consistently cut candidates modulo two, and uses random isolation so connected solutions survive while disconnected candidates cancel.

  • Technique overview: Cut&Count splits into a Cut part that relaxes connectivity and a Count part that computes candidate-cut pairs modulo two.
  • Parity mechanism: Disconnected candidates cancel because they admit an even number of consistent cuts, whereas connected candidates remain in the parity count.
  • Random isolation: Random vertex weights and weight-specific parity counts use the Isolation Lemma to make the relevant solution count odd with high probability.
  • STEINER TREE: For STEINER TREE, candidate sets contain k vertices including all terminals, while solutions additionally require the induced subgraph to be connected.
  • STEINER TREE: 3^tN^2|V|^O(1) time suffices to compute the required parity values for STEINER TREE on a width-t nice decomposition.
  • STEINER TREE: STEINER TREE therefore has a Monte Carlo algorithm running in 3^t|V|^O(1) time, with no false positives and false negatives occurring with probability at most 1/2.
  • DIRECTED MIN CYCLE COVER: The directed cycle-cover application uses analogous parity counting and dynamic programming, yielding a 6^t|V|^O(1) Monte Carlo algorithm with one-sided error.

4 Applications of the technique for other problems

The paper applies Cut&Count to additional connectivity-related problems, using markers, cut states, degree information, and subset-convolution techniques to obtain single-exponential treewidth algorithms.

  • FEEDBACK VERTEX SET: FEEDBACK VERTEX SET encodes forest structure by counting vertices, edges, and marked components, using the characterization that forests have at least n−m components.
  • FEEDBACK VERTEX SET: Its dynamic program tracks selected vertices, introduced edges, markers, weights, and three cut states per bag vertex.
  • CONNECTED VERTEX COVER: CONNECTED VERTEX COVER tracks vertex count, weight, and three membership-side states, checking edge coverage when edges are introduced.
  • CONNECTED DOMINATING SET: CONNECTED DOMINATING SET uses four states per bag vertex and Fast Subset Convolution at join bags to combine domination information.
  • CONNECTED ODD CYCLE TRANSVERSAL: 4^tw(G)|V|^O(1) time results for the undirected CONNECTED ODD CYCLE TRANSVERSAL application by tracking one degree and four states per vertex.
  • Path and cycle problems: LONGEST CYCLE algorithms imply equally fast HAMILTONIAN CYCLE algorithms, and longest-path variants reduce to corresponding longest-cycle variants.
  • Leaf problems: Refined candidate definitions and binomial transforms improve leaf problems to 4^tw(G)|V|^O(1) for EXACT k-LEAF SPANNING TREE and 6^tw(G)|V|^O(1) for EXACT k-LEAF OUTBRANCHING.

5 Lower bounds

The paper establishes lower bounds showing that some connectivity problems remain superexponential in pathwidth, while several Cut&Count bases cannot be improved under SETH.

  • Lower bounds assuming SETH: Assuming SETH, improving the exponential bases for several connected problems, including CONNECTED DOMINATING SET and FEEDBACK VERTEX SET, is impossible.The theorem covers connected vertex cover, connected odd cycle transversal, Steiner tree, and exact k-leaf spanning tree as well.
  • Lower bounds assuming ETH: The lower bounds separate minimizing from maximizing connected components: maximizing components is harder under ETH.The paper contrasts these problems with connectivity minimization results enabled by Cut&Count.
  • Lower bounds assuming ETH: Assuming ETH, CYCLE PACKING, MAX CYCLE COVER, and MAXIMALLY DISCONNECTED DOMINATING SET have no 2^o(p log p)n^O(1)-time algorithms.This holds for directed and undirected versions of the cycle problems, with p the width of a given path decomposition.
  • Lower bounds assuming ETH: The lower-bound proofs reduce from k × k HITTING SET and its permutation variant, then transfer hardness to cycle-packing and related problems.The permutation variant requires one selected element from every row and column.

6 Concluding remarks

The concluding rule of thumb explains when Cut&Count can reduce connectivity optimization to interface counting, while matching lower bounds and open questions delimit its scope.

  • Concluding remarks: Cut&Count computes the minimum number of connected components over subgraphs whose partial behavior is captured by a small bag interface.If θ is the number of possible interfaces, the rule gives a (θ|V|)^O(1)-time algorithm.
  • Concluding remarks: When θ = c^t|V|^O(1), many resulting algorithms run in (c+c′)^t|V|^O(1), where c′ counts states affected by cuts.For many problems, the stated θ^O(1) bound is deliberately loose because better implementations are available.
  • Concluding remarks: Several problems maximizing connected components lack 2^o(p log p)|V|^O(1)-time algorithms unless ETH fails, separating maximization from minimization.The conclusion explicitly identifies this as a marked difference in the treewidth/pathwidth setting.
  • Open questions: The paper leaves open whether Cut&Count can be derandomized and whether its directed-graph constant 6 can be improved.It also asks about derandomizing parameterized algorithms on specially structured tree decompositions.
  • Technical tools: The appendices rely on fast subset convolution and generalized products, including p = 2 and p = 4 computations in p^|B||B|^O(1) ring operations.The applications use the ring Z2, while the appendix discusses calculations over Z and Zq.

A.2 FEEDBACK VERTEX SET

The section applies Cut&Count to Feedback Vertex Set by counting structured, marked forest candidates modulo 2, yielding randomized single-exponential algorithms.

  • Constrained Feedback Vertex Set: 3^t|V|^O(1) time suffices for Constrained Feedback Vertex Set on a tree decomposition of width t.The Monte Carlo algorithm cannot give false positives and may give false negatives with probability at most 1/2.
  • Cut&Count construction: The Cut part represents candidates as marked subgraphs with prescribed size, edge count, marker count, and total weight.Candidates exclude the required set S and are organized by parameters A, B, C, and W.
  • Cut&Count construction: A valid candidate is a forest whose every connected component contains a marker, enabling connectivity-related structure to be recognized through consistent cuts.The forest characterization uses the condition that a graph is a forest exactly when it has at most n−m connected components.
  • Dynamic programming: The dynamic program tracks vertex, edge, marker, and weight accumulators together with bag colourings in a bottom-up traversal.The state records local interfaces while maintaining global counts through the decomposition.
  • Dynamic programming: The recurrence computes parity in 3^t|V|^O(1) time, and nonempty parity identifies a feedback vertex set of the required size.The algorithm counts modulo 2 rather than storing full integer counts.
  • Related applications: The same framework gives 3^t|V|^O(1) algorithms for Constrained Connected Vertex Cover and 4^t|V|^O(1) algorithms for Connected Dominating Set and Connected Odd Cycle Transversal.These algorithms share the one-sided error guarantee: no false positives and false negatives with probability at most 1/2.

A.3.4 CONNECTED FEEDBACK VERTEX SET

The section extends Cut&Count to Connected Feedback Vertex Set and situates it alongside cycle and path problems captured by Partial Cycle Cover.

  • Constrained Connected Feedback Vertex Set: The candidate solution requires a connected set Y containing S whose complement is a forest.This is the constrained connected version addressed by the section.
  • Constrained Connected Feedback Vertex Set: 4^t|V|^O(1) time solves Constrained Connected Feedback Vertex Set on a tree decomposition of width t.The Monte Carlo algorithm has no false positives and false negatives with probability at most 1/2.
  • Cut&Count construction: Cut&Count attaches one consistent cut to G[Y] and another to G[V\Y].The two cuts enforce the connectedness of the chosen solution and its forest complement within the counting framework.
  • Dynamic programming: The dynamic program tracks subgraph size, edge count, marker count, weight, and four-way bag colourings while processing the decomposition bottom-up.State transitions enforce cut consistency and the constraints involving S and a fixed vertex v1.
  • Dynamic programming: The recurrence computes the parity of counted triples in 4^t n^O(1) time.The final table entry gives the parity needed to test whether a valid connected feedback vertex set exists.
  • Partial Cycle Cover: Partial Cycle Cover unifies Longest Cycle, Minimum Cycle Cover, and, through reduction, Longest Path.The undirected version is solved by Cut&Count in 4^t|V|^O(1) time, while the directed version uses 6^t|V|^O(1) time.

A.4.1 The undirected case

For undirected Partial Cycle Cover, Cut&Count counts marked edge sets and consistent cuts, with a compressed dynamic program running in single-exponential treewidth time.

  • Result: 4^t|V|^O(1) time solves undirected Partial Cycle Cover on a tree decomposition of width t.The algorithm is Monte Carlo, with no false positives and false negatives occurring with probability at most 1/2.
  • Cut&Count construction: The counted objects are edge subsets X of size ℓ with k marked edges, prescribed weight, and degree two at every vertex of G[X].These conditions make X a collection of vertex-disjoint cycles covering exactly ℓ vertices.
  • Cut&Count construction: The solution family keeps components that are isolated vertices or contain a marked edge, while the cut family requires a consistent cut with marked-edge endpoints on one side.Markers bound the number of cycle components by k.
  • Dynamic programming: Each bag state records degree information, cut side information for degree-one vertices, and accumulators for marked edges, selected edges, and weight.Sides are omitted for degree-zero and degree-two vertices because no later edge can require that information for degree-two completion.
  • Dynamic programming: Marking edges avoids ambiguity because every edge is introduced exactly once in the tree decomposition.Vertex marking could occur multiple times or require unavailable cut-side information.
  • Dynamic programming: A direct recurrence costs 16^t|V|^O(1), but the Z4 product reduces join-bag processing and yields the 4^t|V|^O(1) bound.The Z4 encoding makes compatible colouring combinations correspond to nonzero terms in the convolution.
  • Result: The final dynamic program computes the parity of the cut family for every weight in 4^t|V|^O(1) time.A nonzero parity for some weight detects the desired partial cycle cover.

A.4.2 The directed case

DIRECTED PARTIAL CYCLE COVER is solved with a Monte-Carlo Cut&Count algorithm using 6^tw(G)|V|^O(1) time. The dynamic program counts solution parities over weighted arc subsets and consistent cuts.

  • Algorithm and guarantee: 6^t|V|^O(1) time solves DIRECTED PARTIAL CYCLE COVER with no false positives and false negatives with probability at most 1/2.The algorithm computes the parity of consistent-cut objects modulo 2.
  • Cut&Count construction: Cut&Count represents candidates as arc subsets X with marked arcs M, tracking |X|, |M|, and their combined weight.The weighted universe is A × {X, M}.
  • Cut&Count construction: A candidate is counted when every vertex in G[X] has indegree and outdegree one, while each nontrivial component contains a marked arc.Consistent cuts additionally require the marked vertices to lie on one designated side.
  • Dynamic programming states: The state of each boundary vertex records its indegree, outdegree, and, for degree-one vertices, its cut side.Degree-zero and degree-two vertices do not retain cut-side information.
  • Dynamic programming states: Join transitions combine child states through a six-state table, and generalized subset convolution reduces direct 36^t processing to 6^t|V|^O(1).The resulting join computation has the stated 6^t|V|^O(1) complexity.

A.5.2 EXACT k-LEAF OUTBRANCHING

EXACT k-LEAF OUTBRANCHING asks for a rooted spanning tree directed away from its root with exactly k leaves. Cut&Count yields a 6^t|V|^O(1)-time Monte-Carlo algorithm by counting weighted arc candidates and consistent cuts modulo 2.

  • Result: 6^t|V|^O(1) time solves EXACT k-LEAF OUTBRANCHING, with no false positives and false negatives occurring with probability at most 1/2.The algorithm is Monte Carlo and receives a width-t tree decomposition.
  • Cut&Count formulation: The cut part uses arc subsets X with prescribed indegrees, exactly k outdegree-zero vertices, and a random weight function.The root has indegree zero and every other vertex has indegree one.
  • Correctness: Weak connectivity together with the indegree constraints makes each valid candidate a spanning tree rooted at v1 with edges directed away from the root.Such candidates have |V| − 1 arcs.
  • Cut&Count formulation: The counted objects pair each candidate with a consistent cut of G(V \ R, X), where R contains the designated outdegree-zero vertices and the root is fixed on one side.This formulation avoids storing cut sides for vertices in R.
  • Dynamic programming: The dynamic program stores boundary cut colors and indegree information while tracking the number of designated vertices and total weight.Fast subset convolution evaluates join transitions within the 6^t|V|^O(1) bound.

A.6 MAXIMUM FULL DEGREE SPANNING TREE

EXACT FULL DEGREE SPANNING TREE asks for a spanning tree containing exactly k vertices whose tree degree equals their graph degree. The Cut&Count algorithm solves it in 4^t|V|^O(1) time.

  • Result: 4^t|V|^O(1) time solves EXACT FULL DEGREE SPANNING TREE with no false positives and false negatives with probability at most 1/2.The algorithm is Monte Carlo and uses a width-t tree decomposition.
  • Cut&Count formulation: The cut part considers edge subsets X of size |V| − 1 and weight W, requiring exactly k vertices to satisfy deg_G(v) = deg_G[X](v).These subsets are the solution candidates.
  • Correctness: Because an edge set of size |V| − 1 is connected exactly when it forms a tree, consistent cuts identify the connected candidates.The counted solution objects are connected candidates of weight W.
  • Dynamic programming: Dynamic-programming states track forgotten full-degree vertices, selected-edge count, selected-edge weight, boundary cut sides, and unselected incident-edge information.The interface records whether a boundary vertex still has an incident edge outside X.

A.7 GRAPH METRIC TRAVELLING SALESMAN PROBLEM

GRAPH METRIC TRAVELLING SALESMAN asks for a closed walk of length at most k visiting every vertex. Cut&Count solves it in 4^t|V|^O(1) time by tracking edge multiplicities, parity, weights, and consistent cuts.

  • Result: 4^t|V|^O(1) time solves GRAPH METRIC TRAVELLING SALESMAN with no false positives and false negatives with probability at most 1/2.The algorithm is Monte Carlo on a width-t tree decomposition.
  • Cut&Count formulation: Solution candidates assign each edge multiplicity 0, 1, or 2, with total size i at most k and randomized weight W.The universe distinguishes using each edge once from using it twice.
  • Cut&Count formulation: Candidates require every vertex to have even degree, while solutions additionally require the used-edge subgraph to be connected.Consistent cuts are formed on the subgraph induced by edges with positive multiplicity.
  • Dynamic programming: The dynamic program tracks walk size, weight, boundary cut sides, and whether each boundary vertex has odd or even degree.Edges can be omitted, used once, or used twice.
  • Dynamic programming: Xor products evaluate join transitions, allowing the parity of consistent-cut objects to be computed for all relevant sizes and weights in 4^t|V|^O(1) time.All arithmetic is performed modulo 2.

B Improvements in FVS, CVC and CFVS parameterized by the solution size

Combining iterative compression with Cut&Count improves parameterized algorithms for FEEDBACK VERTEX SET, CONNECTED VERTEX COVER, and CONNECTED FEEDBACK VERTEX SET. The resulting Monte Carlo algorithms use single-exponential dependence on the solution size and polynomial space.

  • Overview: Iterative compression and Cut&Count improve upper bounds for three vertex-deletion problems whose remaining graphs have constant treewidth.The problems are FEEDBACK VERTEX SET, CONNECTED VERTEX COVER, and CONNECTED FEEDBACK VERTEX SET.
  • FEEDBACK VERTEX SET: 3^k nO(1) time solves FEEDBACK VERTEX SET with polynomial space and false-negative probability at most 1/2.The Monte Carlo algorithm cannot give false positives.
  • Algorithmic framework: Iterative compression constructs solutions consecutively on growing subgraphs, while Cut&Count processes a bounded-treewidth decomposition obtained from the current solution.For FEEDBACK VERTEX SET, adding the current solution to every bag yields width at most k + 2.
  • CONNECTED VERTEX COVER: 2^k nO(1) time solves CONNECTED VERTEX COVER with polynomial space and false-negative probability at most 1/2.The algorithm cannot give false positives; the connectivity requirement reduces the complexity from 3^k nO(1) to 2^k nO(1).
  • Algorithmic framework: Bounding reasonable boundary evaluations exploits a large connected component and at most two additional vertices, yielding 3^3 · 2^(k−1) evaluations for CONNECTED VERTEX COVER.This bound gives the 2^k nO(1) running time using polynomial space.
  • CONNECTED FEEDBACK VERTEX SET: 3^k nO(1) time solves CONNECTED FEEDBACK VERTEX SET with polynomial space and false-negative probability at most 1/2.This improves on the previously best stated 46.2^k nO(1) algorithm.

C Negative results under ETH

The paper establishes ETH-based lower bounds for maximizing connected components, showing that several problems likely require 2^Ω(p log p) nO(1) time when parameterized by pathwidth. The reductions start from hitting-set variants and preserve pathwidth within linear bounds.

  • Lower bounds: The lower-bound section targets problems that maximize rather than minimize the number of connected components.The stated hard problems are CYCLE PACKING, MAX CYCLE COVER, and MAXIMALLY DISCONNECTED DOMINATING SET.
  • Lower bounds: Assuming ETH, CYCLE PACKING, MAX CYCLE COVER, and MAXIMALLY DISCONNECTED DOMINATING SET have no 2^o(p log p) nO(1) algorithms.Here p is the width of a given path decomposition, and MAX CYCLE COVER is covered in both directed and undirected settings.
  • Reduction sources: The reductions originate from k × k HITTING SET and k × k PERMUTATION HITTING SET, for which ETH rules out 2^o(k log k)nO(1) algorithms.The permutation variant requires exactly one selected element from each row and column.
  • Dominating-set reduction: Force gadgets compel every dominating set of size at most ℓ to contain their attached vertex.Omitting the attached vertex forces inclusion of ℓ + 1 new degree-one vertices.
  • Dominating-set reduction: One-in-many gadgets compel every dominating set of size at most ℓ to contain a vertex from their attached set X.If X is avoided, all ℓ + 1 gadget vertices must enter the dominating set.
  • Dominating-set reduction: The constructed graph has pathwidth at most 3k, while a YES hitting-set instance yields a dominating set of size ℓ with exactly r connected components.Conversely, any dominating set of size at most ℓ inducing at least r components implies a YES hitting-set instance.

C.2.1 Proof overview and preliminaries

The proof overview reduces permutation hitting set to cycle-packing instances using gadget constructions that enforce solution constraints while preserving pathwidth up to additive constants. The central r-in-many gadget limits how many attaching-set vertices a cycle family may use.

  • Preliminaries: Multiple edges and loops can be removed from cycle-packing instances while increasing pathwidth by at most 2.Replacing each edge with a path of length three preserves vertex-disjoint cycle families.
  • Proof overview: The undirected cycle-packing reduction constructs a graph with path decomposition width O(k), preserving equivalence with permutation hitting set.A YES initial instance yields ℓ vertex-disjoint cycles, and any such cycle family implies a YES initial instance.
  • r-in-many gadget: The gadget enforces that at most r vertices of X are covered by a gadget-safe cycle family in the original graph.A gadget extension is gadget safe when it contains the maximum number ℓ_G of gadget short cycles.
  • r-in-many gadget: An r-in-many gadget attached to X adds |X| − r vertices joined to every vertex of X by double edges.Each gadget short cycle uses one new vertex and one attaching-point vertex.
  • r-in-many gadget: Any maximum cycle family can be chosen gadget safe, and removing its ℓ_G short cycles leaves a gadget-safe family in the original graph.This permits reasoning about the underlying construction after accounting for the forced gadget cycles.
  • Pathwidth preservation: If each attaching set X_i appears in a decomposition bag, adding r_i-in-many gadgets increases pathwidth by at most 1.The new bags contain the original bag plus one gadget vertex.
  • Construction: The reduction’s constructed graph G contains ℓ vertex-disjoint cycles whenever the initial permutation hitting-set instance is a YES-instance.The construction begins from the permutation hitting-set instance and builds graph H before attaching the gadgets.

C.2.5 From disjoint cycles to hitting set

The reduction analyzes vertex-disjoint cycle families through gadget-safe cycles and an induction that extracts a permutation hitting set. Structural separation properties force each selected cycle to encode a row-column choice intersecting every set S_s.

  • Lemma C.20 shows that at least ℓ vertex-disjoint cycles imply a YES-instance of k × k PERMUTATION HITTING SET.
  • A maximum cycle family can be made gadget safe, leaving a family C of non-short cycles for structural analysis.
  • The subgraph H[L ∪ R ∪ C] is a forest whose components organize the paths and attached leaves used by the reduction.
  • Each cycle in C contains exactly two vertices from Z, and together the cycles cover Z.
  • The separator sets E_s force each selected cycle to cross between Z_s and Z \ Z_s, while all remaining cycles stay on one side.
  • Induction identifies a permutation f such that (i, f(i)) belongs to every S_s, yielding a hitting set with one element per row and column.

D Negative results under SETH

The paper establishes SETH-based lower bounds showing that the single-exponential algorithms' bases are optimal for several connectivity problems. Polynomial-size reductions from SAT preserve sufficiently small pathwidth while encoding satisfiability through solution existence.

  • D.1 CONNECTED VERTEX COVER: Under SETH, CONNECTED VERTEX COVER cannot be solved in (3 −ε)^p|V|^O(1) time given a path decomposition of width p.The lower bound follows from a reduction to STEINER TREE that preserves treewidth and increases pathwidth by at most one.
  • D.1 CONNECTED VERTEX COVER: A satisfying SAT assignment exists if and only if the constructed graph has a connected vertex cover of size at most K.The forward and reverse directions are given by Lemmas D.5 and D.6, while the construction has pathwidth at most ηn′ + O(3^η).
  • D.2 CONNECTED DOMINATING SET: Under SETH, CONNECTED DOMINATING SET cannot be solved in (4 −ε)^p|V|^O(1) time on pathwidth p.The reduction preserves satisfiability in both directions and constructs a path decomposition of width at most n′ + O(1).
  • D.3 CONNECTED FEEDBACK VERTEX SET and CONNECTED ODD CYCLE TRANSVERSAL: Under SETH, CONNECTED FEEDBACK VERTEX SET and CONNECTED ODD CYCLE TRANSVERSAL cannot be solved in (4 −ε)^p|V|^O(1) time on pathwidth p.One SAT reduction supplies the two correctness directions and yields pathwidth at most n′ + O(1).
  • D.4 FEEDBACK VERTEX SET: Under SETH, FEEDBACK VERTEX SET cannot be solved in (3 −ε)^p|V|^O(1) time on pathwidth p.The reduction uses a construction without a connectivity requirement, proves satisfiability equivalence, and achieves pathwidth at most ηn′ + O(η3^η).
Loading 1103.0534v1…