A $2$-Approximation for Directed Feedback Vertex Set in Locally Semicomplete and Quasi-Transitive Digraphs

1 Introduction

• General digraphs have no constant-factor DFVS approximation under the Unique Games Conjecture, motivating stronger guarantees on structured classes.Weighted DFVS has a randomized factor-2 approximation on tournaments, and the two classes studied here also include sparse digraphs such as certain path orientations.Source: §1 · p. 2
• Locally semicomplete digraphs strictly generalize semicomplete digraphs and tournaments, while retaining local density without requiring global semicompleteness.They may contain induced directed cycles of unbounded length, so hitting directed triangles alone does not solve DFVS.Source: §1 · p. 2

Our Results

• The randomized factor-2 approximation for weighted DFVS on locally semicomplete digraphs runs in O(n^18 log(2n/δ)) time for success probability at least 1 − δ.The algorithm always outputs a feedback vertex set.Source: Our Results · p. 3
• The randomized factor-2 approximation for weighted DFVS on quasi-transitive digraphs improves the deterministic 9/4-approximation, at the cost of randomization.Its running time is O(N^17 log(2N/δ)) for success probability at least 1 − δ.Source: Our Results · p. 3
• Factor 2 is optimal under the Unique Games Conjecture because tournaments belong to both locally semicomplete and quasi-transitive digraphs.Source: Our Results · p. 3

Feedback vertex set

• A weighted feedback vertex set is a vertex set whose removal leaves an acyclic digraph, and weighted DFVS minimizes its total weight.A randomized factor-f approximation always returns a feedback vertex set and achieves weight at most f · OPT with probability at least 1/2.Source: §2 · p. 4

Semicomplete and locally semicomplete digraphs

• A locally semicomplete digraph has semicomplete in- and out-neighborhoods at every vertex, and this property is preserved by induced subdigraphs.A semicomplete digraph has at least one arc between every pair of distinct vertices.Source: §2 · p. 4

Semicomplete DFVS approximation

• The semicomplete-digraph routine gives a randomized factor-2 approximation for weighted DFVS in O(n^17) time, with success probability at least 1/2.It extends the tournament routine by reducing directed 2-cycles edge by edge and applying that routine to the remaining tournament with residual weights.Source: §2 · p. 4

Round decomposition

• A round-decomposable locally semicomplete digraph is a composition of strong semicomplete modules over a round local-tournament quotient.The quotient's cyclic ordering specifies consecutive in- and out-neighborhoods.Source: §2 · pp. 4–5

Structural classification

• Every connected locally semicomplete digraph is round-decomposable, neither semicomplete nor round-decomposable, or semicomplete but not round-decomposable.A polynomial-time algorithm identifies the case and supplies a corresponding certificate.Source: §2 · p. 5

Quasi-transitive digraphs

• A quasi-transitive digraph has an arc between the endpoints of every directed two-edge path, and this property is hereditary under induced subdigraphs.A strong quasi-transitive digraph that is not semicomplete decomposes over a strong semicomplete quotient into singleton or non-strong quasi-transitive modules.Source: §2 · p. 5

3.1 Strongly Connected Components

• A feedback vertex set can be solved componentwise because every directed cycle lies within one strongly connected component, and the component approximation factor is preserved.The union of the component solutions is feasible, and its guarantee holds whenever every component call meets its guarantee.Source: §3.1 · pp. 5–6

3.2 Cycles and Approximation in Digraph Compositions

• A composition is acyclic after deletion exactly when each remaining module and the quotient on nonempty modules are both acyclic.The quotient feedback vertex set consists of representatives of modules emptied by the deletion.Source: §3.2 · p. 6
• Module solutions plus quotient-selected whole-module deletions combine approximation factors by their maximum, using each module’s extra deletion cost Δ_i = w(V(H_i)) − w(F_i).The construction is feasible and has cost bounded by max{α, β} OPT(D, w) when module and quotient costs meet factors α and β.Source: §3.2 · p. 6

3.3 Local-Ratio for Vertex Cover

• The local-ratio vertex-cover routine splits weights into charged and residual parts, returns a cover with zero residual weight, and gives a factor-2 bound on charged weights.It handles self-looped vertices by forcing them into the cover.Source: §3.3 · p. 7

3.4 Structural Facts for Locally Semicomplete Digraphs

• For locally semicomplete digraphs, non-strong connected instances have semicomplete SCCs, while connected non-round-decomposable instances have independence number at most 2.In the strong, non-round-decomposable, non-semicomplete case, every vertex lies on cycles of every length from 3 to |V(D)|; with independence number at most 2, SCCs away from a chosen vertex are semicomplete.Source: §3.4 · pp. 7–8

• Strongly connected components can be solved separately because every directed cycle lies within one component, and their optimum FVS costs add.Source: §4 · p. 8

Compositions and round-decomposable LSDs

• Round-decomposable locally semicomplete digraphs admit a factor-2 approximation by combining module solutions with an exact FVS for the round quotient.The quotient's lightest in-neighborhood is an optimum FVS; composition combines approximation factors by their maximum, not their product.Source: §4 · p. 8

The non-round-decomposable case

• For a non-round-decomposable strong input, a pivot's 2- and 3-cycle requirements form a vertex-cover instance whose local-ratio solution removes those cycles.Source: §4 · p. 8
• After that deletion, the pivot's SCC is a singleton or round-decomposable, while other SCCs are semicomplete; trying every pivot yields a factor-2 solution.When the pivot is outside an optimum FVS, charged and residual weight bounds combine to give factor 2, and an optimum can always leave at least one vertex.Source: §4 · pp. 8–9

Quasi-transitive digraphs

• For quasi-transitive digraphs, recursively solving smaller modules and applying the semicomplete routine to the quotient preserves factor 2 at every recursion level.Independent repetitions make every call succeed with high probability, even when input weights depend on earlier outcomes.Source: §4 · p. 9

5 A 2-Approximation for DFVS in LSDs

• The LSD algorithm first handles round-decomposable instances, then applies pivot reduction to other strong instances, and combines these routines with semicomplete FVS and SCC decomposition.Source: §5 · p. 9

5.1 The Round-Decomposable Case

• For a round decomposition, the algorithm 2-approximates FVS within each semicomplete module and solves the round quotient exactly before combining the solutions.The combination yields a factor-2 approximation when every module call meets its guarantee.Source: §5.1 · p. 9, §5.1.2 · p. 10

5.1.1 An Exact Algorithm for the Round Quotient

• In a round local tournament, every in-neighborhood and out-neighborhood is an FVS, and a minimum-weight one is optimal and computable in linear time.The algorithm accumulates all in-neighborhood weights in one scan of the arcs.Source: §5.1.1 · p. 9

5.1.2 The Round Algorithm and Its Analysis

• The round routine always returns an FVS and achieves factor 2 when all module calls succeed; amplification gives success probability at least 1−ε in O(n^17 log(2m/ε)) time.The routine uses k=⌈log2(2m/ε)⌉ repetitions for m modules.Source: §5.1.2 · p. 10

5.2 The Non-Round-Decomposable Case

• For a strong LSD that is neither semicomplete nor round-decomposable, the pivot reduction removes vertices covering 2- and 3-cycles through the pivot, leaving SCCs solvable by the two routines.The pivot candidate is feasible, and its factor-2 guarantee holds when the pivot is outside an optimum FVS and the amplified calls succeed.Source: §5.2 · pp. 10–11

5.3 The Full Algorithm

• The full algorithm handles components independently, using the round-decomposable routine, semicomplete routine, or pivot enumeration for other strong LSDs.For each pivot candidate, it keeps the lightest solution; the pivot analysis guarantees a factor-2 solution when the pivot avoids an optimum FVS.Source: §5.3 · p. 12, §5.3.1 · p. 12

5.3.1 Correctness, Success Probability, and Running Time

• With probability at least 1−δ, the full algorithm returns a factor-2 weighted DFVS for an LSD in O(n^18 log(2n/δ)) time.It always returns a feasible feedback vertex set.Source: §5.3.1 · p. 12

6.1 The Algorithm

• The algorithm handles SCCs separately, solves semicomplete inputs with an amplified routine, and recursively combines module solutions with a solution for the semicomplete quotient.The canonical decomposition supplies proper, nonempty quasi-transitive modules.Source: §6.1 · p. 13, §6.2 · p. 14

6.2 Correctness, Approximation Guarantee, and Running Time

• With probability at least 1−δ, the algorithm returns a factor-2 weighted DFVS for an N-vertex quasi-transitive digraph in O(N^17 log(2N/δ)) time.Its output is always feasible.Source: §6.2 · p. 14
• The composition framework preserves feasibility unconditionally and gives a factor-2 guarantee when the recursive module calls and quotient call succeed.Amplified semicomplete calls and a union bound provide the claimed success probability.Source: §6.2 · p. 14

Declaration of AI Assistance

• ChatGPT 5.5 and 5.6 assisted with language refinement and restructuring the exposition.Source: Declaration of AI Assistance · p. 14

A Amplifying the Semicomplete Routine

• The routine runs the semicomplete algorithm independently k times and returns a minimum-weight output.Source: A Amplifying the Semicomplete Routine · p. 17
• The output is always an FVS and is a factor-2 approximation with probability at least 1−2^-k, in O(kn^17) time.If any repetition meets the factor-2 guarantee, the lightest output does too.Source: A Amplifying the Semicomplete Routine · p. 17