Source-linked AI summary
Representative sets and irrelevant vertices: New tools for kernelization
Stefan Kratsch, Magnus Wahlström
TL;DR
The paper addresses missing polynomial kernels for Almost 2-SAT and several graph cut problems. It applies representative-set lemmas from matroid theory to kernelization and irrelevant-vertex arguments, obtaining randomized polynomial kernels and polynomial-size cut-covering sets. The results include O(k6) variables for Almost 2-SAT, O(ks+1) vertices for s-Multiway Cut, and explicit bounds for covering families of minimum cuts.
Problem
Polynomial kernels were previously unknown for Almost 2-SAT and several graph cut problems, including Multiway Cut and Multicut variants.
Method
The paper applies representative-set lemmas from matroid theory to simplify cut problems and identify irrelevant vertices that can be made undeletable.
Results
The paper obtains randomized polynomial kernels for Almost 2-SAT and several graph cut problems, plus polynomial-size sets covering families of minimum cuts.
Takeaways & Limitations
Representative sets provide a general kernelization tool that yields kernels for Almost 2-SAT, constant-terminal cut problems, and related cut-covering results.
Takeaways & Limitations
Polynomial kernels remain open for general Multiway Cut, several Multicut variants, Group Feedback Set with arbitrary groups, and Directed Feedback Vertex Set.
Abstract
from arXiv · showhide
The existence of a polynomial kernel for Odd Cycle Transversal was a notorious open problem in parameterized complexity. Recently, this was settled by the present authors (Kratsch and Wahlström, SODA 2012), with a randomized polynomial kernel for the problem, using matroid theory to encode flow questions over a set of terminals in size polynomial in the number of terminals. In the current work we further establish the usefulness of matroid theory to kernelization by showing applications of a result on representative sets due to Lovász (Combinatorial Surveys 1977) and Marx (TCS 2009). We show how representative sets can be used to give a polynomial kernel for the elusive Almost 2-SAT problem. We further apply the representative sets tool to the problem of finding irrelevant vertices in graph cut problems, i.e., vertices which can be made undeletable without affecting the status of the problem. This gives the first significant progress towards a polynomial kernel for the Multiway Cut problem; in particular, we get a kernel of O(k^{s+1}) vertices for Multiway Cut instances with at most s terminals. Both these kernelization results have significant spin-off effects, producing the first polynomial kernels for a range of related problems. More generally, the irrelevant vertex results have implications for covering min-cuts in graphs. For a directed graph G=(V,E) and sets S, T \subseteq V, let r be the size of a minimum (S,T)-vertex cut (which may intersect S and T). We can find a set Z \subseteq V of size O(|S|*|T|*r) which contains a minimum (A,B)-vertex cut for every A \subseteq S, B \subseteq T. Similarly, for an undirected graph G=(V,E), a set of terminals X \subseteq V, and a constant s, we can find a set Z\subseteq V of size O(|X|^{s+1}) which contains a minimum multiway cut for any partition of X into at most s pairwise disjoint subsets.
1 Introduction
The paper applies representative sets from matroid theory to polynomial kernelization, addressing open kernelization problems in Almost 2-SAT and graph cuts. It obtains randomized polynomial kernels and cut-covering sets with polynomial size bounds.
- Motivation: Polynomial kernels were previously unknown for Almost 2-SAT and several related problems, including Vertex Cover Above LP.Almost 2-SAT also captures Odd Cycle Transversal and has implications for several other parameterized problems.
- Representative-set approach: The paper uses representative sets to simplify Digraph Pair Cut, a constrained cut problem designed to capture the iterative-compression form of Almost 2-SAT.The simplification reduces the problem to one involving a polynomial number of terminals.
- Kernelization results: Almost 2-SAT admits a randomized kernel with O(k6) variables and failure probability O(2−n).The corresponding compression has size ˜O(k6), one-sided error, and false positives only.
- Kernelization results: O(ks+1) vertices suffice for s-Multiway Cut, alongside kernels for Multiway Cut with deletable terminals, s-Multicut, and Group Feedback Vertex Set.All these kernelizations are randomized with failure probability exponentially small in n.
- Cut-covering consequences: The paper also develops irrelevant-vertex results for covering minimum cuts and multiway cuts through terminal sets.Theorems 3 and 4 provide polynomial-size sets containing minimum cuts for broad families of terminal choices or partitions.
2 Preliminaries
The preliminaries define parameterized kernelization, describe the randomized guarantees used throughout, and introduce linear matroids and gammoids as the paper’s representation framework.
- Parameterized complexity and kernelization: A kernelization maps an instance with parameter k to an equivalent instance whose size and parameter are bounded by a computable function h(k).The kernel is polynomial when h is polynomially bounded.
- Randomization: All kernelization results are randomized, with either one-sided false positives or failure probability exponentially small in the input size.The paper notes that these randomized kernels remain compatible with existing kernel lower-bound frameworks.
- Matroids: A matroid consists of a ground set and independent sets satisfying nonemptiness, heredity, and augmentation axioms.Rank is the maximum size of an independent subset, and a basis is a maximal independent set.
- Matroids: Linear matroids are represented by matrices whose columns form the ground set and whose linearly independent subsets are the matroid’s independent sets.The paper uses only matroids representable over a field.
- Gammoids: In a gammoid, subsets linked to source vertices by vertex-disjoint paths form the independent sets of a matroid.Such a representation can be found in randomized polynomial time with one-sided error.
- Graph constructions: Sink-only copies retain only incoming edges and are used to require multiple paths to reach selected vertices.Adding such a copy does not affect independent sets that omit the copy.
3 Tools from matroid theory
The paper connects closest cuts to gammoid independence and uses representative sets to preserve relevant cut behavior while discarding redundant choices.
- Representative sets: A representative subcollection preserves the existence of independent extensions after adding any disjoint set of up to r elements.This property allows a smaller family of sets to retain the extension behavior of the original family.
- Representative sets: The paper uses representative sets in the rank-adjusted form obtained from the matroid rank and the set size.The cited lemma builds on work by Lovász and Marx.
- Representative-set lemma: For a linear matroid of rank r+s, the lemma removes a set while retaining an r-representative family and finds it in polynomial time from a representation.The reduction applies when the family contains sufficiently many independent sets of size s.
- Closest cuts: A closest set is the unique minimum cut closest to the source, and every set induces such a closest cut through a polynomial-time operation.Closestness is defined using uniqueness of the relevant source-to-set minimum cut.
- Closest cuts and gammoids: Gammoid independence characterizes reachability after deleting a closest cut: a vertex is reachable exactly when the corresponding augmented set is independent.The construction uses sink-only copies and a maximal independent subset of the cut.
- Irrelevant vertices: A non-closest cut can be replaced by an equally small cut that omits a vertex whose sink-only augmentation is dependent.This replacement is the basis for identifying irrelevant vertices.
4 Representative sets: A polynomial kernel for Almost 2-SAT
Representative sets and gammoid representations reduce Digraph Pair Cut to polynomial size, yielding randomized kernels for Almost 2-SAT and related problems.
- Problem: Digraph Pair Cut asks whether deleting at most k vertices prevents every input pair from remaining reachable from source s.It generalizes Vertex Cover: an n-point star centered at s yields one Vertex Cover edge per pair.
- Representative sets: The representative-pair lemma reduces any instance to O(k^2) pairs while preserving reachability under every closest cut of size at most k.The reduction succeeds in randomized polynomial time with exponentially small failure probability.
- Gammoid encoding: Gammoid representations encode the relevant graph-cut reachability questions after representative pairs have been selected.For closest cuts, reachability corresponds to extending an independent set in a gammoid; two disjoint copies handle vertex pairs.
- Generalization: q-tuples generalize the construction, with representative sets of size O(k^q) for separating at least one member of every tuple.The O(k^q) bound is stated to be tight for q-tuples.
- Kernel consequences: A randomized compression of Digraph Pair Cut has size ˜O(k^3(k + log 1/ε)) and success probability at least 1 − ε.In the remaining cases, the compressed output encodes a positive instance; standard reductions then give a polynomial coRP-kernel for Almost 2-SAT.
5 Finding irrelevant vertices: Polynomial kernels for cut problems
Representative sets identify vertices that can be retained or made undeletable without changing relevant cut solutions, producing randomized kernels for bounded-terminal cut problems and broader cut-covering results.
- Irrelevant vertices: An irrelevant vertex is one that some optimal solution avoids, although different irrelevant vertices may each be needed by other optimal solutions.This distinction motivates iterative deletion rather than assuming all irrelevant vertices can be removed simultaneously.
- Further consequences: The framework also yields direct polynomial kernels for s-Multicut, bounded-group Feedback Vertex Set, Almost 2-SAT, and signed-cycle problems.The reported bounds include O(k^6) for Almost 2-SAT and O(k^4.5) for signed Odd Cycle Transversal.
- Deletable terminals: Multiway Cut with deletable terminals has a randomized kernel of O(k^3) vertices, with exponentially small error limited to false negatives.Representative vertices together with the terminals contain an optimal solution, allowing all other vertices to become undeletable.
- Bounded terminals: For s-Multiway Cut, representative sets identify irrelevant vertices iteratively, yielding a randomized kernel of O(k^{s+1}) vertices.The approach removes one irrelevant vertex per iteration rather than directly guaranteeing a representative set containing an optimal solution.
- Cut covering: The cut-covering results find O(|S|·|T|·r) vertices containing a minimum (A,B)-cut for every A ⊆ S and B ⊆ T.A related directed result finds O(|X|^3) vertices covering minimum cuts between terminal subsets after deleting any terminal subset R.
- Limitations: The cut-covering upper bound is only known to be necessary up to Ω(|S|·|T|), since the authors do not know whether the additional factor r is necessary.This is an explicit tightness limitation for the directed covering result.
6 Implications for Almost 2-SAT and related problems
The paper reduces Almost 2-SAT to Digraph Pair Cut and derives randomized polynomial kernels, while also transferring the resulting framework to related vertex-cover problems.
- Almost 2-SAT: Almost 2-SAT Compression reduces in polynomial time to Digraph Pair Cut with parameter k′ = |X| + k.The reduction represents variables and clauses using directed edges and terminal pairs, with solution sizes corresponding in both directions.
- Almost 2-SAT: Almost 2-SAT has a randomized polynomial-time compression of size ˜O(k6), implying a polynomial coRP-kernelization.The kernel is bootstrapped from an initial deletion set of size polynomial in k.
- Related problems: The kernelization framework yields randomized polynomial kernels for Vertex Cover Above Matching, König Deletion Set variants, and RHorn-Backdoor Deletion Set.These consequences follow through polynomial parameter transformations, including the equivalence between Vertex Cover Above Matching and Almost 2-SAT.
- Related problems: Vertex Cover Above LP and Vertex Cover Above Maximum Matching are equivalent under polynomial parameter transformations.The reduction from the LP parameterization to the matching parameterization complements the trivial reverse direction.
7 Implications for multi-terminal cut problems
Representative sets support kernels for bounded-terminal cut problems and fixed-group feedback vertex set by identifying vertices that can be made undeletable without changing optimal solutions.
- Bounded terminal pairs multicut: The s-Multicut construction has exponentially small error probability in n, with errors limited to false negatives.The same one-sided limitation applies to the representative-set alternatives described for the construction.
- Group feedback vertex set: The paper connects Group Feedback Vertex Set to nonnull-cycle deletion and notes that Odd Cycle Transversal is the special case with group Z2.It also gives a direct reduction from Multiway Cut to Group Feedback Vertex Set using terminal labels and heavy terminal copies.
- Group feedback vertex set: The group-feedback construction first obtains a solution of size O(s2k2) or proves that the instance is negative.It normalizes labels outside the approximate solution and then invokes multiway-cut structure.
- Group feedback vertex set: For a fixed group Γ with s elements, Group Feedback Vertex Set(k) has a randomized polynomial kernel with O(k2s+2) vertices.The approach reduces selected group-label assignments to Multiway Cut instances with s terminals and uses irrelevant vertices.
8 Omitted proofs
The omitted proofs establish the representative-set machinery behind the paper’s kernel bounds, including Digraph Pair Cut, bounded-terminal Multiway Cut, and min-cut covering results.
- Digraph Pair Cut: Digraph Pair Cut can be solved in time O∗(2k) and compressed to size ˜O(k3(k + log 1/ǫ)) with success probability at least 1−ǫ.The algorithm branches on reachable pairs while representative pairs preserve reachability under closest-to-source cuts.
- Digraph Pair Cut: A representative-pair construction reduces Digraph Pair Cut to O(k2) pairs, yielding a kernel of O(k4) vertices.The construction uses two gammoid copies and a representative subset of the resulting pair family.
- Multiway Cut: s-Multiway Cut(k) has a randomized kernel of O(ks+1) vertices, with exponentially small error probability and false negatives only.The reduction identifies potentially highly reachable vertices and safely makes other vertices undeletable.
- Covering min-cuts: A directed graph admits a set of O(|S|·|T|·r) vertices containing a minimum (A,B)-vertex cut for every A ⊆ S and B ⊆ T.Vertices outside the covering set and terminals may then be made undeletable without changing minimum cut sizes.
- Covering multiway cuts: An undirected graph with terminal set X admits a set of O(|X|s+1) vertices containing a minimum multiway cut for every partition into at most s parts.This is the covering statement used to derive the bounded-terminal multiway-cut kernel.
9 Conclusion
The paper develops matroid-based techniques that yield randomized polynomial kernels and small cut-covering sets across several parameterized problems. These results advance kernelization while leaving broader kernelization questions open.
- Conclusion: Representative-set techniques from matroid theory yield polynomial kernels for Almost 2-SAT, s-terminal Multiway Cut, and Multicut with s terminal pairs.The kernels apply for constant s and can be made reduction-rule based.
- Conclusion: The techniques find small sets containing minimum cuts for every pair of terminal subsets and minimum multiway cuts for bounded-size terminal partitions.These cut-covering sets have size polynomial in the number of terminals.
- Conclusion: The kernels are randomized but remain compatible with established lower-bound frameworks for polynomial kernelization.The authors identify concrete polynomial upper and lower bounds as a relevant direction for future work.
- Conclusion: Polynomial kernels remain open for general Multiway Cut, Multicut, Group Feedback Arc Set, Group Feedback Vertex Set, and Directed Feedback Vertex Set variants.The open cases include edge- and vertex-deletion variants and arbitrary groups where specified.