PaperlayerView exact revision on arXiv

Source-linked AI summary

An iterative rounding $2$-approximation for Feedback Vertex Set via AI-assisted proof of an extreme point property

Karthekeyan Chandrasekaran, Chandra Chekuri, Shubhang Kulkarni

arXiv:2609.04414v1cs.DS

TL;DR

Earlier FVS 2-approximations used local-ratio and primal-dual methods, while a conjectured extreme-point route to iterative rounding remained unproved. This paper proves the extreme-point properties for two strong-density formulations and obtains polynomial-time iterative-rounding 2-approximations.

  • Problem

    The conjectured extreme-point property of the strong-density LP, which could support iterative rounding for FVS, remained unproved.

    Source: §1 · p. 2

  • Method

    The paper proves extreme-point properties for the vertex-based strong-density and edge-based strong-density polyhedra, then uses their structure to construct iterative-rounding algorithms.

    Source: §1 · pp. 2–3

  • Results

    At least 1/2: every extreme point of either polyhedron for a graph containing a cycle has a coordinate at least 1/2, and the resulting algorithms are polynomial-time 2-approximations.

    Source: §1 · pp. 3–4

  • Takeaways & Limitations

    The edge formulation’s polynomial-time separation oracle and compact extended formulation support iterative-rounding 2-approximations, including one that avoids the Ellipsoid method.

    Source: §1 · p. 4

    No computational study has yet tested instance-specific gains; LP solving can be slow because of many constraints, and iterative rounding is typically slow.

    Source: §5 · p. 31

Abstract

from arXiv · show

We consider the Feedback Vertex Set problem (FVS): the input is an undirected graph $G=(V,E)$ and the goal is to find a minimum-cardinality (or a min-cost in the weighted case) subset $S \subseteq V$ of vertices such that $G-S$ has no cycles. A $2$-approximation via the local-ratio method was developed in the mid 90's by Bafna, Berman and Fujito (1995) and by Becker and Geiger (1996), and this approximation ratio is tight under UGC. The local-ratio algorithms were later interpreted as primal-dual algorithms via an LP relaxation by Chudak, Goemans, Hochbaum, and Williamson (1998). All known $2$-approximation algorithms for FVS have been via local-ratio and primal-dual methods, and in a quest to obtain a new LP rounding algorithm, it was conjectured (Fiorini 2021) that the Strong-Density polyhedron developed by Chudak, Goemans, Hochbaum, and Williamson has an extreme point property: every basic feasible solution to the LP has a variable with value at least $1/2$. We prove this conjecture. We also consider a related Strong-Edge-Density polyhedron and show the same extreme point property. The advantage of this polyhedron is that it admits a polynomial-time separation oracle and also a compact extended formulation. These results lead to polynomial-time iterative rounding $2$-approximation algorithms. The proof of the extreme point property is of independent technical interest and key ideas in the proof were suggested by AI tools.

1 Introduction

The paper proves the conjectured extreme-point property for the strong-density polyhedron and establishes the same property for an edge-based formulation, yielding iterative-rounding 2-approximations for FVS. It explains the formulations, proof ideas, algorithmic consequences, and connections to related deletion problems.

1 Introduction

  • Earlier 2-approximation algorithms used local-ratio or primal-dual methods, while the LP relaxations motivating Fiorini’s conjecture were not known to be polynomial-time solvable.The conjecture sought an extreme-point property that could support iterative rounding.Source: §1 · p. 2
  • PEdge−SD(G) imposes inequalities on edge-induced subgraphs and is strictly contained in PSD(G), which uses vertex-induced subgraphs.Figure 1 exhibits a point in PSD(G) that violates an edge-subset constraint.Source: §1 · p. 3, Figure 1 · p. 4
  • For graphs containing a cycle, every extreme point of PSD(G) and PEdge−SD(G) has some coordinate at least 1/2.These are the two structural results underlying the paper’s iterative-rounding algorithms.Source: §1 · p. 3
  • The results yield polynomial-time iterative-rounding 2-approximations: PSD(G) uses Ellipsoid round-or-cut, while PEdge−SD(G) supports direct rounding through separation or a compact extended formulation.The extended-formulation approach avoids the Ellipsoid method.Source: §1 · pp. 3–4

1.2 Related Work

  • The conjecture was motivated as a stepping stone toward LP-based approximations for treewidth deletion and Subset-FVS, whose approximation questions remain open or unresolved.The cited discussion gives Subset-FVS bounds of 2 and 8 and notes that LP-based approximations for treewidth deletion remain open.Source: §1 · p. 4

1 Introduction

  • Solvable LP-based approximations can give instance-specific guarantees by comparing the LP optimum with the rounded solution, rather than relying only on the general 2-factor guarantee.The paper identifies this as a practical motivation for LP-based approximations.Source: §1 · p. 5

1.1 Technical Overview and AI Disclosure

  • For PSD(G), assuming every coordinate is below 1/2 yields conditional supermodularity and an almost-laminar tight basis; AI tools suggested a forest structure and counting lemma used in the proof.The polyhedra can have arbitrary nonnegative integer coefficients, unlike the common {0,1}-coefficient setting for extreme-point results.Source: §1.1 · p. 5
  • For PEdge−SD(G), uncrossing gives a laminar family of tight edge sets; an adapted counting argument proves its structural result, and mutual inclusion arguments establish equivalence with the orientation polyhedron.The vertex sets induced by laminar edge sets may still intersect.Source: §1.1 · p. 6

2 Extreme Point Property of Strong Density Polyhedron

This section develops structural tools for a contradiction proof of the Strong Density extreme-point property, including uncrossing, a structured basis, and a forest-based counting argument. Assuming all variables are below 1/2 leads to incompatible bounds on sharing loss among block roots; the section also shows that the polyhedron implies the FVS cycle-hitting inequalities.

2 Extreme Point Property of Strong Density Polyhedron

  • Corollary 1 states that every vertex subset S whose induced subgraph G[S] contains a cycle satisfies |NZ(S)| ≥ 3, and that FVS hitting-set inequalities are implied in PSD(G).Source: §2 · p. 8

2.1 Conditional Supermodularity and Uncrossing

  • When every coordinate is less than 1/2, f_x is supermodular, and tight sets intersecting in at least two vertices can be uncrossed into tight intersection and union sets.The uncrossing argument also establishes the row identity row(A) + row(B) = row(A ∩ B) + row(A ∪ B).Source: §2.1 · pp. 8–9

2.2 Almost-Laminar Basis Structure

  • Theorem 3 gives a basis from an almost-laminar tight-set family whose rows and zero-coordinate unit vectors are independent and span all variables; each set induces a 2-connected graph with at least three positive coordinates.It also ensures that for nested basis sets A ⊂ B, some vertex in B \ A has a positive coordinate.Source: §2.2 · p. 10

2.3 Forest Structure of Almost-Laminar Family

  • The inclusion poset of the almost-laminar basis family has a forest as its Hasse diagram because each set has at most one minimal proper superset.This relies on the basis sets having at least three vertices; almost-laminarity alone does not ensure a forest when singleton sets are allowed.Source: §2.3 · p. 13

2.4 Counting Lemmas for Contradiction

  • The counting argument sets p = |L| = n − |Z|; when every block is a single set and block roots are disjoint, p equals the block count and each root has at least three positive-coordinate vertices.The supplied passage introduces this as a simple case of the contradiction argument.Source: §2.2 · p. 10, §2.4 · p. 14
  • Corollary 2 gives σglobal ≥ 2t, using the block-surplus bound |NZ(Vhat_i)| ≥ k_i + 2.Source: §2.4 · p. 15

2.4.1 Proof of Theorem 1

  • Assuming all x_u < 1/2 forces σglobal ≥ 2t, but the block roots have σglobal ≤ 2t − 3, a contradiction.For t = 1 there is no sharing across blocks, also contradicting σglobal ≥ 2t.Source: §2.4.1 · p. 15

2.4.2 Proof of the Union Feasibility Inequality

  • For r pairwise-at-most-one-intersecting tight sets, Lemma 7 bounds sharing loss by 2r − 3 because union feasibility limits the surplus from shared vertices.The bound applies when r ≥ 2.Source: §2.4 · p. 15, §2.4.2 · p. 17

2.4.3 Proof of the Block Surplus Lemma

  • Induction on each block’s containment tree proves that every set S has |NZ(S)| ≥ kS + 2, yielding the root block-surplus bound.Here kS counts sets in the subtree rooted at S.Source: §2.4 · p. 15, §2.4.3 · p. 17

3 Extreme Point Property of Edge Strong Density Polyhedron

The section develops an extreme-point argument for the Edge Strong Density polyhedron, using a laminar tight-basis structure and technical counting bounds to rule out solutions with every coordinate below 1/2. It then derives an iterative-rounding 2-approximation for Feedback Vertex Set using an exponential-constraint LP with a polynomial-time separation oracle.

3 Extreme Point Property of Edge Strong Density Polyhedron

  • Assuming every coordinate is below 1/2 leads to a contradiction, establishing the extreme-point property for PEdge−SD(G).If there is one maximal basis set, the global sharing loss is 0; with at least two, the proof derives incompatible lower and upper bounds.Source: §3 · p. 17, §3.3.1 · p. 24
  • Every edge subset whose induced subgraph contains a cycle has at least three positive-coordinate vertices in its support.The argument applies the cycle constraint and the assumption that every coordinate is below 1/2.Source: §3 · p. 18

3.1 Supermodularity and Uncrossing

  • For xu < 1, fx is supermodular, with equality in the supermodularity inequality exactly when V(A) ∩ V(B) = V(A ∩ B); intersecting tight sets uncross to tight intersection and union.The uncrossing also preserves the sum of the corresponding row vectors.Source: §3.1 · p. 19

3.2 Laminar Basis Structure

  • A laminar tight basis exists with |L| + |Z| = |V|, whose sets induce 2-connected graphs with at least three positive-coordinate vertices and whose strict inclusions add a positive-coordinate vertex.The basis rows together with the zero-coordinate unit vectors are linearly independent.Source: §3.2 · p. 20

3.3 Counting Lemmas for Contradiction

  • Each maximal set satisfies |NZ(bFi)| ≥ ki + 2, yielding the global sharing-loss lower bound σglobal ≥ 2t.Here ki counts the laminar sets contained in maximal set bFi, and t is the number of maximal sets.Source: §3.3 · p. 24

3.3.1 Proof of Theorem 2

  • For t ≥ 2, pairwise edge-disjoint maximal sets yield σglobal ≤ σ(A) ≤ 2t − 3 by Lemma 14, a contradiction; when t = 1, σglobal = 0, also a contradiction.Source: §3.3.1 · p. 24

3.3.2 Proof of Lemma 14

  • For pairwise edge-disjoint tight sets, the edges incident to any vertex in their union are partitioned among the sets containing that vertex.The proof sets dAj(v) = 0 when v is not in V(Aj).Source: §3.3.2 · p. 25
  • For r ≥ 2, the proof of Lemma 14 bounds the integral sharing loss by σ(A) ≤ 2r − 3.The preceding proof steps invoke xv < 1/2 when σ(A) is nonzero.Source: §3.3.2 · p. 26

3.3.3 Proof of Lemma 15

  • Lemma 15 is proved by induction on the laminar-family tree, using the leaf case, child-set bounds, and Lemma 14’s sharing-loss bound.Applying the resulting property to the root S = bFi proves the lemma.Source: §3.3.3 · p. 26

3.4 Iterative Rounding via Edge Strong Density Polyhedron

  • The Edge Strong Density LP yields a 2-approximation by iteratively choosing a vertex with value at least 1/2 and removing it.An extreme-point optimum can be computed in polynomial time using the Ellipsoid method and a separation oracle implemented via submodular minimization; the LP has exponentially many constraints. The guarantee is relative to the starting extreme-point LP optimum.Source: §3.4 · p. 27
  • The Edge Strong Density iterative-rounding algorithm uses an LP with exponentially many constraints, unlike the polynomial-constraint LP designed in Section 4.Source: §3.4 · p. 27

4 Orientation Polyhedron

The section relates edge strong-density constraints to an orientation-based formulation and uses that relationship to obtain another iterative-rounding 2-approximation for FVS.

4 Orientation Polyhedron

  • The authors connect the edge strong-density polyhedron to the orientation formulation for FVS in, enabling an alternative iterative-rounding 2-approximation using a polynomial-size LP.The orientation-based formulations arise from viewing FVS as a density-deletion problem.Source: §4 · p. 27

4.1 Edge Strong Density Polyhedron and Orientation Polyhedron

  • PEdge−SD(G) equals Qorient(G); the authors prove both inclusions, including by rounding a Farkas certificate to an integral edge-subset inequality.The proof uses the Edge-SD constraint for a non-empty edge subset.Source: §4.1 · pp. 28–30

4.2 Iterative Rounding via Orientation Polyhedron

  • Enumerating constraints x_u≥1/2 avoids relying on extended-space extreme points, preserves the unconstrained optimum in at least one LP, and yields a 2-approximation using a polynomial-sized LP.The projected polyhedron has an optimal extreme point with some coordinate at least 1/2, although an extended-space extreme point need not have a large original coordinate.Source: §4.2 · p. 31

5 Conclusion

The conclusion identifies computational improvements for the paper’s LP-based approaches as future work. It also points to Treewidth Deletion and Subset Feedback Vertex Set as related problems where stronger approximation results remain of interest.

5 Conclusion

  • LP-solving can be slow because PEdge−SD(G) and Qorient(G) have many constraints, and iterative rounding is typically slow.The authors leave computational study of instance-based approximations and faster exact or near-optimal LP-solving and rounding algorithms for future work.Source: §5 · p. 31
  • For Treewidth Deletion, the authors identify generalizing FVS LP approaches and improving the constant factor of randomized constant-approximation as open directions.They also mention designing a deterministic constant-approximation.Source: §5 · p. 31
  • For SFVS, the best-known upper and lower approximation bounds are 8 and 2, respectively, and a compact LP relaxation has integrality gap at most 13.Improving the compact relaxation’s upper bound remains open.Source: §5 · p. 32

A Iterative Rounding via Strong Density Polyhedron

The section addresses the obstacle that the strong-density polyhedron cannot be optimized over in known polynomial time. It uses the extreme-point result and conditional supermodularity with the ellipsoid algorithm to obtain a polynomial-time 2-approximation.

A Iterative Rounding via Strong Density Polyhedron

  • The strong-density polyhedron PSD(G) has exponentially many constraints and no known efficient separation oracle, so Theorem 1 alone does not yield an immediate iterative-rounding algorithm.The difficulty is that polynomial-time optimization over PSD(G) is not known.Source: A Iterative Rounding via Strong… · p. 33
  • The algorithm combines Theorem 1’s extreme-point result and conditional supermodularity of fx with the ellipsoid algorithm to achieve a polynomial-time 2-approximation.The section’s approach uses a round-or-cut strategy embedded in iterative rounding.Source: A Iterative Rounding via Strong… · pp. 33–34

A.1 Separation below the 1/2-threshold

When every remaining coordinate is below 1/2, the section gives a polynomial-time way to find violated strong-density inequalities or certify feasibility. It reduces the search to submodular minimization, once for each edge.

A.1 Separation below the 1/2-threshold

  • When all coordinates are below 1/2, violated strong-density inequalities can be found in polynomial time.The method applies to sets containing at least one edge.Source: §A.1 · p. 34
  • For each edge e, submodular minimization finds a set maximizing fx among sets containing e; the largest such value equals the maximum over all edge-containing sets.The minimization uses hx,e, which is submodular because −fx is submodular.Source: §A.1 · p. 34
  • If the maximum fx value is positive, its set yields a violated strong-density inequality; otherwise, x satisfies the strong-density constraints.Thus one submodular minimization per edge determines whether the maximum is positive.Source: §A.1 · p. 34

A.2 Produce-Witness Subroutine

Produce-Witness uses a weak separation oracle and the ellipsoid method to obtain a useful fractional solution despite the lack of general polynomial-time separation for PSD(G). It either finds a coordinate at least 1/2 or reaches a vertex of PSD(G) with such a coordinate.

A.2 Produce-Witness Subroutine

  • Produce-Witness uses a weak oracle whose returned halfspaces are valid for PSD(G), and which never rejects a point in PSD(G).The oracle uses residual separation after restricting to coordinates outside the set at least 1/2.Source: §A.2 · p. 35
  • The ellipsoid method finds an accepted point with cost at most LPSD(G), whose restriction outside the coordinates at least 1/2 lies in the corresponding residual polyhedron.This gives properties (i) and (iii) of the witness procedure.Source: §A.2 · p. 35
  • If the accepted point has a coordinate at least 1/2, the procedure returns it; otherwise, it is optimal for PSD(G) and the algorithm seeks a vertex.The accepted point with all coordinates below 1/2 lies in PSD(G).Source: §A.2 · p. 35
  • The vertex search uses at most |V| auxiliary LPs; Theorem 1 ensures the resulting vertex has a coordinate at least 1/2, and the algorithm runs in polynomial time.If the weak oracle finds such a coordinate during an auxiliary run, the procedure stops early; otherwise, it acts as an exact separation oracle throughout.Source: §A.2 · pp. 35–36

A.3 The Algorithm

The section presents an iterative-rounding 2-approximation for FVS built around Produce-Witness. It establishes that the algorithm runs in polynomial time.

A.3 The Algorithm

  • The algorithm uses Produce-Witness in an iterative-rounding approach to obtain a 2-approximation for FVS.Source: §A.3 · p. 36
  • Each iteration removes a nonempty set Ai from the current graph while it contains a cycle, and the algorithm returns a feedback vertex set.The input is a graph with non-negative vertex costs.Source: §A.3 · p. 36
  • The algorithm runs in polynomial time: each iteration deletes at least one vertex, so there are at most |V| iterations, and Produce-Witness runs in polynomial time.Source: §A.3 · p. 36
  • For each i, zi = min{cᵀx : x ∈ PSD(Hi)}; the initial value z0 is at most OPT, and since Ht is a forest, zt equals 0.Source: §A.3 · pp. 36–37
Loading 2609.04414v1…