Source-linked AI summary
Faster Parameterized Algorithms using Linear Programming
Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh
TL;DR
The paper studies Vertex Cover parameterized by the gap between an optimal solution size and the LP relaxation value, motivated by improving above-guarantee algorithms. It analyzes LP-value changes in branching and combines the resulting algorithm with reductions to improve bounds for several related problems and kernelization.
Problem
The paper asks whether an approach based on the gap between solution size and LP optimum can yield simpler and faster algorithms for Above Guarantee Vertex Cover.
Method
The paper combines deterministic preprocessing, branching analyzed through changes in the LP value, and parameterized reductions to related problems.
Results
The paper obtains an O^*(2.3146^k) algorithm for Vertex Cover above LP, matching bounds for several related problems, an O^*(1.5214^k) bound for three others, and a kernel with at most 2k - c log k vertices.
Takeaways & Limitations
The new Odd Cycle Transversal algorithm is the first to improve on the dependence of the seminal O^*(3^k) algorithm, while reductions transfer algorithmic and kernelization results across problems.
Takeaways & Limitations
The reduced graph is technically defined using both the input graph and its memory representation because reduction choices depend on the LP solution, although the implemented rules and LP solver are deterministic.
Abstract
from arXiv · showhide
We investigate the parameterized complexity of Vertex Cover parameterized by the difference between the size of the optimal solution and the value of the linear programming (LP) relaxation of the problem. By carefully analyzing the change in the LP value in the branching steps, we argue that combining previously known preprocessing rules with the most straightforward branching algorithm yields an $O^*((2.618)^k)$ algorithm for the problem. Here $k$ is the excess of the vertex cover size over the LP optimum, and we write $O^*(f(k))$ for a time complexity of the form $O(f(k)n^{O(1)})$, where $f (k)$ grows exponentially with $k$. We proceed to show that a more sophisticated branching algorithm achieves a runtime of $O^*(2.3146^k)$. Following this, using known and new reductions, we give $O^*(2.3146^k)$ algorithms for the parameterized versions of Above Guarantee Vertex Cover, Odd Cycle Transversal, Split Vertex Deletion and Almost 2-SAT, and an $O^*(1.5214^k)$ algorithm for Konig Vertex Deletion, Vertex Cover Param by OCT and Vertex Cover Param by KVD. These algorithms significantly improve the best known bounds for these problems. The most notable improvement is the new bound for Odd Cycle Transversal - this is the first algorithm which beats the dependence on $k$ of the seminal $O^*(3^k)$ algorithm of Reed, Smith and Vetta. Finally, using our algorithm, we obtain a kernel for the standard parameterization of Vertex Cover with at most $2k - c \log k$ vertices. Our kernel is simpler than previously known kernels achieving the same size bound.
1 Introduction and Motivation
The paper studies Vertex Cover above LP and develops faster parameterized algorithms, reductions to related problems, and a smaller kernel for standard Vertex Cover.
- Motivation: The standard Vertex Cover parameterization becomes impractical when the requested cover size is large relative to a maximum matching.When k is smaller than the matching size, the answer is immediately NO; otherwise large matchings can make the standard running time unattractive.
- Motivation: Above Guarantee Vertex Cover is central among related parameterized problems because improved algorithms transfer to Almost 2-SAT and Odd Cycle Transversal.The paper describes parameterized reductions connecting agvc with several problems.
- Motivation: Vertex Cover above LP parameterizes the excess of the requested cover size over the LP relaxation optimum.The LP relaxation replaces binary variables with nonnegative variables, and its optimum lower-bounds minimum vertex-cover size.
- Results and Methodology: O^*(2.3146^(k−vc*(G))) is achieved for Vertex Cover above LP through LP-aware branching and preprocessing.A simpler version combines known preprocessing rules with arbitrary-vertex branching, while the faster version adds more involved branching rules.
- Results: O^*(1.5124^k) is obtained for Konig Vertex Deletion, and a kernel with at most 2k − c log k vertices is obtained for standard Vertex Cover.The kernel is described as simpler than a previous kernel with the same size bound.
2 Preliminaries
The preliminaries define the graph-theoretic notation, LP relaxation, half-integral optima, and branching-measure terminology used throughout the paper.
- Notation: For vertex sets, G[S] is the induced subgraph, N_G(u) is the open neighborhood, and N_G(T) excludes T itself.The notation N_i[S] denotes vertices within distance i of S.
- Surplus: The surplus of an independent set X is |N(X)| − |X|, while graph surplus is the minimum surplus over all independent sets.For a collection of independent sets, surplus is the minimum surplus among its members.
- LP relaxation: LPVC(G) relaxes vertex-cover integrality constraints to nonnegative variables, and its optimum value vc*(G) lower-bounds the minimum vertex-cover size.The paper uses half-integral optimal solutions, with variables in {0, 1/2, 1}, obtainable in polynomial time.
- LP notation: The half-integral solution partitions vertices into V_x^0, V_x^{1/2}, and V_x^1 according to their assigned values.The all-1/2 assignment is also used as a reference LP solution.
- Branching analysis: A branching vector records the measure decrease in each recursive branch, such as (p1, p2, ..., pl).This notation supports the running-time analysis of branching algorithms.
3 A Simple Algorithm for Vertex Cover above LP
The simple algorithm exhaustively applies three preprocessing rules and then branches on an arbitrary vertex, yielding a 2.6181^(k−vc*(G)) running-time bound.
- Algorithm: The algorithm has preprocessing and branching phases, applying known reduction rules before recursive branching.After preprocessing is exhausted, it branches on an arbitrary vertex.
- Preprocessing: Preprocessing Rule 1 fixes vertices assigned 0 or 1 by a half-integral LP optimum and decreases the target accordingly.It applies when the all-1/2 solution is not the unique LP optimum.
- Preprocessing: Preprocessing Rule 2 includes N(Z) in the cover when surplus(Z)=1 and N(Z) is not independent, deleting Z∪N(Z) and reducing k by |N(Z)|.Its correctness follows from the minimum-surplus structural lemma.
- Preprocessing: Preprocessing Rule 3 removes Z and identifies N(Z) when surplus(Z)=1 and N(Z) is independent, reducing k by |Z|.The reduced instance preserves equivalence of the vertex-cover decision problem.
- Rule testing: Both surplus-one preprocessing rules can be tested in polynomial time using LP instances with selected variables fixed.Rule 2 fixes an edge's endpoints to 1; Rule 3 fixes a vertex to 0 and checks for an LP increase of 1/2.
- Running time: 2.6181^(k−vc*(G)) is the resulting running time for Vertex Cover above LP, and the same base applies to computing a minimum vertex cover.The recurrence analysis uses the measure μ=k−vc*(G).
4 Improved Algorithm for Vertex Cover above LP
The improved algorithm strengthens the simple approach by using branching rules based on the structure of a selected vertex neighborhood.
- Improved branching: The improved algorithm introduces additional branching steps that exploit the structure of the neighborhood of the branched-on vertex or vertex set.Its stated goal is to obtain branching vectors better than the basic algorithm's.
4.1 Some general claims to measure the drops
The improved analysis quantifies measure drops when branching on independent vertex sets and shows how minimum-surplus sets can be found efficiently.
- General branching claims: Branching on an independent set S considers setting all of S to 1 or all of S to 0, with exhaustiveness guaranteed under the minimum-surplus condition.Without that condition, the two branches may omit assignments mixing zeroes and ones within S.
- Measure drops: Including S in the cover decreases the measure by at least min{|S|/2, p/2}, where p is the graph surplus.The complementary branch has a drop governed by the surplus of independent sets containing S.
- Measure drops: Excluding S from the cover decreases k by |N(S)|, while the LP analysis bounds the resulting measure using surplus of sets containing S.The proof relates the new LP value to |N(S)| and the surplus of an associated independent set.
- Minimum-surplus sets: When |S|≥2 and surplus(S)=surplus(G), the two branches yield a (1,1) drop in the analyzed measure.This follows from the general drop bounds for selecting or excluding S.
- Finding branching sets: If such a minimum-surplus independent set exists, the algorithm can find one in polynomial time by solving LPVC after fixing pairs of nonadjacent vertices to 0.The resulting zero-valued vertex set has size at least two and preserves minimum surplus.
4.2 (1,1) drops in the measure
This section identifies several cases that yield a (1, 1) drop in the measure, including minimum-surplus sets, structural neighborhood conditions, and preprocessing after branching.
- A minimum-surplus set of size at least 2 can be branched on to obtain a (1, 1) drop in the measure.
- When the graph has surplus at least 2 and a vertex or set can be excluded in one branch, the resulting branching vector is (1, 1).
- If G[N(v) \ {u}] is a clique for a neighbor u, some minimum vertex cover excludes either v or u.This structural property supports a branching case with a (1, 1) vector.
- Preprocessing Rule 2 decreases the measure by at least 1/2, so combining it with an arbitrary-vertex branch yields a (1, 1) drop.
- The algorithm applies these branching rules in order and checks whether the relevant cases can be detected in polynomial time.
4.3 A Branching step yielding (1/2, 3/2) drop
When earlier preprocessing and branching rules do not apply, a degree-at-least-4 vertex has minimum surplus at least 3, enabling a branching step with a (1/2, 3/2) drop.
- If no preceding rules apply, choosing a vertex v of degree at least 4 gives surplus(HS) ≥3 for S = {v}.
- The corresponding branching step is summarized as yielding a (1/2, 3/2) drop.
4.4 A Branching step yielding (1, 3/2, 3/2) drop
A subsequent branching rule combines the inclusion branch's 1/2 drop with later rules B1–B3, producing a net (1, 3/2, 3/2) drop.
- If B1, B2, or B3 applies after including a branched vertex, the combined step has drop (1, 3/2, 3/2).The vector is obtained as (1, 1/2 + 1, 1/2 + 1).
- Figure 5 illustrates the branches of rules B5 and B6, while Figure 6 depicts the branching step with the three-component drop.
4.5 The Final branching step
After all earlier rules fail, the remaining graph is 3-regular, and the algorithm performs a final branching step whose analysis is handled separately.
- When preprocessing and earlier branching rules do not apply, the graph is 3-regular.
- The algorithm selects a vertex and executes the final branching step more carefully to simplify the analysis of its measure drop.
- Figure 7 provides an outline of this last step.
4.6 Complete Algorithm and Correctness
The complete algorithm combines exhaustive preprocessing with branching on irreducible graphs, using structural lemmas to establish the measure decreases needed for its runtime bound.
- Algorithm outline: The algorithm exhaustively applies preprocessing rules, then handles connected components separately and solves components of size at most 10 optimally.The complete algorithm is outlined in Figure 8.
- Branching analysis: B6 dominates the runtime through branching vector (3/2, 3/2, 5/2, 5/2, 2), yielding the recurrence T(μ) ≤ T(μ − 1) + 2T(μ − 3/2).The recurrence solves to 2.3146^μ.
- Correctness: Structural lemmas show that degree-4 vertices persist after B6 and that irreducible graphs have shortest cycle length at least 7.These properties support the required subsequent branching and locality of preprocessing effects.
- Runtime: The resulting algorithm solves Vertex Cover above LP in time O*(2.3146^(k−vc*(G))).The theorem states this bound directly.
5 Applications
The Vertex Cover above LP algorithm is transferred through reductions to several above-guarantee and structural-deletion problems, obtaining improved exponential dependencies and a smaller kernel.
- Above Guarantee Vertex Cover: Above Guarantee Vertex Cover is solvable in time O*(2.3146^ℓ), where ℓ is the excess of minimum vertex cover size over maximum matching size.This follows because the LP relaxation value is at least the maximum matching size.
- Reductions: Known reductions yield O*(2.3146^k) algorithms for Almost 2-SAT, Almost 2-SAT(v), RHorn-Backdoor Detection Set, and KVDpm.The stated corollary applies the Vertex Cover above LP result through parameter-preserving reductions.
- Transversal reductions: The (X,Y)-Transversal Set problem reduces to Above Guarantee Vertex Cover via an auxiliary graph whose independent sets correspond to (X,Y)-induced subgraphs.The construction uses two copies of the input vertex set and matching edges between corresponding copies.
- Structural deletion: Odd Cycle Transversal and Split Vertex Deletion are solvable in time O*(2.3146^k).They are obtained as corollaries for choices of X and Y in the transversal framework.
- König-based problems: KVD, Vertex Cover Param by OCT, and Vertex Cover Param by KVD are solvable in time O*(1.5214^k).The KVD result uses reductions and structural properties of König graphs, including a matching characterization.
- Kernelization: The kernel for standard Vertex Cover has at most 2k − c log k vertices for any fixed constant c.The bound follows from uniqueness of the LP optimum in the reduced instance.
6 Conclusion
The paper identifies LP-value drops in branching as a powerful parameterized-complexity technique and connects agvc to other problems through parameterized reductions.
- LP-value drops provide a powerful way to analyze branching algorithms in parameterized complexity.
- The authors view their algorithm as a starting point for improving agvc and possibly classical Vertex Cover running-time bounds.
- Parameterized reductions connect agvc with several other parameterized problems, including Almost 2-SAT and Odd Cycle Transversal.
- Because the parameter changes in these reductions are linear, kernelization upper and lower bounds transfer between the connected problems subject to reduction direction.
7 Appendix: Problem Definitions
The appendix defines the parameterized problems and graph or formula classes used throughout, including above-guarantee Vertex Cover, deletion problems, and backdoor detection.
- Above Guarantee Vertex Cover: Above Guarantee Vertex Cover asks whether a graph has a vertex cover of size at most |M| + ℓ, parameterized by ℓ above a maximum matching size.
- Vertex Cover: LP-parameterized Vertex Cover asks for a cover of size at most k, parameterized by k −⌈vc*(G)⌉, where vc*(G) is the minimum LPVC value.
- Odd Cycle Transversal: Odd Cycle Transversal asks whether deleting at most k vertices makes a graph bipartite, while its edge version deletes at most k edges instead.
- Split Vertex Deletion: A split graph has vertices partitionable into a clique and an independent set; Split Vertex Deletion asks whether at most k vertices can create one.
- König Vertex Deletion: A König graph has equal maximum-matching and minimum-vertex-cover sizes, and König Vertex Deletion asks whether deleting at most k vertices produces one.
- Almost 2-SAT and RHBDS: Almost 2-SAT deletes at most k clauses, or variables in its variable version, so the resulting formula becomes satisfiable; RHBDS deletes at most k variables to obtain a renamable Horn formula.