[Rule] MinimumVertexCover to MinimumFeedbackVertexSet

[isPANN]

Source: VERTEX COVER
Target: FEEDBACK VERTEX SET
Motivation: Establishes NP-completeness of MinimumFeedbackVertexSet via polynomial-time reduction from MinimumVertexCover, showing that every undirected edge can be converted into a directed 2-cycle so that a vertex cover in the original graph corresponds exactly to a feedback vertex set in the constructed digraph.

Reference: Garey & Johnson, Computers and Intractability, A1.1 GT7

GJ Source Entry

[GT7] FEEDBACK VERTEX SET
INSTANCE: Directed graph G = (V,A), positive integer K ≤ |V|.
QUESTION: Is there a subset V' ⊆ V with |V'| ≤ K such that V' contains at least one vertex from every directed cycle in G?

Reference: [Karp, 1972]. Transformation from VERTEX COVER.
Comment: Remains NP-complete for digraphs having no in- or out-degree exceeding 2, for planar digraphs with no in- or out-degree exceeding 3 [Garey and Johnson, ——], and for edge digraphs [Gavril, 1977a], but can be solved in polynomial time for reducible graphs [Shamir, 1977]. The corresponding problem for undirected graphs is also NP-complete.

Reduction Algorithm

Summary:
Given a MinimumVertexCover instance (G=(V,E), k) where G is an undirected graph, construct a MinimumFeedbackVertexSet instance (G'=(V',A'), k') as follows:

1. Vertex set: V' = V (one vertex in G' for each vertex in G; no new vertices are added).
2. Arc set: For each undirected edge {u,v} ∈ E, add both directed arcs (u→v) and (v→u) to A'. Each undirected edge becomes a directed 2-cycle of length 2: u→v→u.
3. Budget parameter: Set k' = k.
4. Key invariant: Every 2-cycle u→v→u in G' corresponds to an edge {u,v} in G. Hitting all 2-cycles is equivalent to covering all edges. Any longer directed cycle must traverse some arc (u,v), and {u,v} is an edge of G, so if S covers all edges then S already contains u or v, breaking that longer cycle as well. Hence FVS(G') = VC(G).
5. Solution extraction: Any FVS of size ≤ k in G' is a vertex cover of size ≤ k in G, and vice versa.

Correctness:

• (⇒) If S is a vertex cover for G of size ≤ k, then for every directed 2-cycle u→v→u in G', at least one of u, v is in S (since {u,v} ∈ E). Hence S is a FVS for G' of size ≤ k.
• (⇐) If S is a FVS for G' of size ≤ k, then for every arc (u,v) ∈ A', the 2-cycle u→v→u is broken, so at least one of u, v is in S. Since every edge {u,v} ∈ E generated arcs in both directions, S covers every edge of G.

Size Overhead

Symbols:

• n = num_vertices of source graph G
• m = num_edges of source graph G

Target metric (code name)	Polynomial (using symbols above)
num_vertices	num_vertices
num_arcs	2 * num_edges

Derivation:

• Vertices: same vertex set, no additions → |V'| = n
• Arcs: each undirected edge {u,v} yields two directed arcs (u→v) and (v→u) → |A'| = 2m

Validation Method

• Closed-loop test: reduce a MinimumVertexCover instance to MinimumFeedbackVertexSet, solve target with BruteForce, extract solution (same vertex set), verify it is a valid vertex cover on the original undirected graph
• Check that the minimum FVS size in G' equals the minimum VC size in G
• Test with a path graph P_n (minimum VC = ⌈(n−1)/2⌉): the constructed digraph has 2(n−1) arcs forming n−1 independent 2-cycles; minimum FVS = ⌈(n−1)/2⌉ ✓
• Test with a complete graph K_n (minimum VC = n−1): verify minimum FVS = n−1 in the all-pairs bidirected digraph

Example

Source instance (MinimumVertexCover):
Graph G with 7 vertices {0, 1, 2, 3, 4, 5, 6} and 8 edges:

• Edges: {0,1}, {0,2}, {0,3}, {1,2}, {1,3}, {3,4}, {4,5}, {5,6}
• Structure: K4 minus edge {2,3} on vertices {0,1,2,3}, plus a path 3–4–5–6. Contains two triangles: {0,1,2} and {0,1,3}. Three vertices (0, 1, 3) have degree 3; vertices 2, 4, 5 have degree 2; vertex 6 has degree 1.
• Minimum vertex cover: k = 4, for example {0, 1, 3, 5}:
  • {0,1} covered by 0 ✓, {0,2} covered by 0 ✓, {0,3} covered by 0 ✓
  • {1,2} covered by 1 ✓, {1,3} covered by 1 ✓
  • {3,4} covered by 3 ✓, {4,5} covered by 5 ✓, {5,6} covered by 5 ✓

Constructed target instance (MinimumFeedbackVertexSet):
Directed graph G' with 7 vertices {0, 1, 2, 3, 4, 5, 6} and 16 arcs:

• From edge {0,1}: arcs (0→1) and (1→0)
• From edge {0,2}: arcs (0→2) and (2→0)
• From edge {0,3}: arcs (0→3) and (3→0)
• From edge {1,2}: arcs (1→2) and (2→1)
• From edge {1,3}: arcs (1→3) and (3→1)
• From edge {3,4}: arcs (3→4) and (4→3)
• From edge {4,5}: arcs (4→5) and (5→4)
• From edge {5,6}: arcs (5→6) and (6→5)

Directed cycles in G': eight 2-cycles ({0↔1}, {0↔2}, {0↔3}, {1↔2}, {1↔3}, {3↔4}, {4↔5}, {5↔6}) plus longer cycles induced by the triangles (e.g., 0→1→2→0 from triangle {0,1,2} and 0→1→3→0 from triangle {0,1,3}). Hitting all 2-cycles automatically breaks longer cycles too.

Target budget: K' = k = 4

Solution mapping:

• Minimum FVS in G': {0, 1, 3, 5}
  • Breaks 2-cycle {0↔1}: vertex 0 ∈ FVS ✓
  • Breaks 2-cycle {0↔2}: vertex 0 ∈ FVS ✓
  • Breaks 2-cycle {0↔3}: vertex 0 ∈ FVS ✓
  • Breaks 2-cycle {1↔2}: vertex 1 ∈ FVS ✓
  • Breaks 2-cycle {1↔3}: vertex 1 ∈ FVS ✓
  • Breaks 2-cycle {3↔4}: vertex 3 ∈ FVS ✓
  • Breaks 2-cycle {4↔5}: vertex 5 ∈ FVS ✓
  • Breaks 2-cycle {5↔6}: vertex 5 ∈ FVS ✓
  • Remaining graph on {2, 4, 6}: arcs (2→0), (2→1), (4→3), (4→5), (6→5) all point to removed vertices — no arcs remain among {2, 4, 6}, so the induced subgraph is edgeless, hence acyclic ✓
• Extracted vertex cover in G: {0, 1, 3, 5} — same set
• Verification: all 8 edges of G are covered ✓
• FVS size = 4 = k ✓

Greedy trap: Vertices 0, 1, and 3 all have degree 3 (tied for maximum). Vertex 3 appears in only 2 of 5 optimal solutions, while vertex 0 appears in 4 of 5. If a greedy max-degree heuristic commits to vertex 3 early while skipping both 0 and 1, it can be forced into a suboptimal cover of size 5. The 5 distinct optimal solutions — {0,1,3,5}, {0,1,4,5}, {0,1,4,6}, {0,2,3,5}, {1,2,3,5} — illustrate that the dense near-K4 subgraph and the path tail interact in non-trivial ways.

References

• [Karp, 1972]: [Karp1972] Richard M. Karp (1972). "Reducibility among combinatorial problems". In: Complexity of Computer Computations. Plenum Press.
• [Garey and Johnson, ——]: (not found in bibliography)
• [Gavril, 1977a]: [Gavril1977a] F. Gavril (1977). "Some {NP}-complete problems on graphs". In: Proceedings of the 11th Conference on Information Sciences and Systems, pp. 91–95. Johns Hopkins University.
• [Shamir, 1977]: [Shamir1977] Adi Shamir (1977). "Finding minimum cutsets in reducible graphs". Laboratory for Computer Science, Massachusetts Institute of Technology.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	Target problem (FeedbackVertexSet) does not exist in the codebase yet; novel reduction
Non-trivial	✅ Pass	Converts undirected edges to directed 2-cycles; constructs a digraph from an undirected graph
Correctness	❌ Fail	Step 4 of the algorithm contains a false claim; validation section has an incorrect formula
Well-written	⚠️ Warn	Minor issues in worked example justification; overall structure is good

Overall: 2 passed, 1 failed, 1 warning

---

Usefulness

Pass. The target problem FeedbackVertexSet (or MinimumFeedbackVertexSet) does not currently exist in the reduction graph. The codebase has 24 problem types and none of them is FVS. This is a classic Karp reduction (Vertex Cover → Feedback Node Set appears in Karp's 1972 reduction tree, and Garey & Johnson GT7 explicitly states "Transformation from VERTEX COVER"). The reduction would add a new problem node and a new edge to the graph.

Non-trivial

Pass. The reduction constructs a directed graph from an undirected graph by replacing each undirected edge with a pair of directed arcs (a 2-cycle). This is a genuine structural transformation — the source is an undirected graph problem and the target is a directed graph problem with a fundamentally different feasibility condition (hitting all directed cycles vs. covering all edges). It is not a variable substitution, subtype coercion, or identity reduction.

Correctness

Fail. The references are valid but the algorithm description contains a factual error, and the validation section has an incorrect claim.

References verified:

• Karp 1972 — Confirmed. The Karp reduction tree shows Vertex Cover → Feedback Node Set. The paper exists and is correctly cited (Plenum Press, pp. 85-103). Already in the project bibliography as karp1972.
• Garey & Johnson 1979, GT7 — Confirmed. GT7 is Feedback Vertex Set, and the entry states "Transformation from VERTEX COVER." Already in bibliography as garey1979.

Algorithm error in Step 4:
The issue claims: "Every directed cycle in G' is one of these 2-cycles (the graph has no other cycles because every arc came from a symmetric pair)."

This is false. Consider a triangle {0,1,2} in the source graph. The constructed digraph contains arcs 0→1, 1→2, 2→0 (among others), forming a directed 3-cycle. In general, any cycle in the undirected graph induces directed cycles of the same length in the constructed digraph.

The reduction is still correct — hitting all 2-cycles (which is equivalent to covering all edges) automatically hits all longer cycles too, since every edge of a longer cycle is also a 2-cycle. But the stated justification is wrong and should be corrected to:

Every 2-cycle u→v→u corresponds to edge {u,v}. Hitting all 2-cycles is equivalent to covering all edges. Any longer directed cycle c must traverse some arc (u,v), and {u,v} is an edge of G, so if S covers all edges then S already contains u or v, breaking c as well. Hence FVS(G') = VC(G).

Validation section error:
The issue states: "Test with a path graph P_n (minimum VC = n−1)". The minimum vertex cover of a path P_n on n vertices is ⌈(n−1)/2⌉, not n−1. For example, P_4 (path on 4 vertices, 3 edges) has minimum VC = 2, not 3. This should be corrected.

Well-written

Warn. The issue is generally well-structured and follows the template well. All required sections are present and substantive. The example is worked through in detail with a non-trivial 6-vertex graph. However:

1. Algorithm Step 4 justification is incorrect (detailed above) — this is the main issue affecting implementability, since a developer reading the invariant would be confused by the false claim.
2. Validation formula error for path graph VC size (detailed above).
3. Symbol consistency is good — n, m, V, E, V', A' are used consistently; overhead table uses code metric names (num_vertices, num_arcs) that would match a directed graph problem's getters.
4. Example quality is good — 6 vertices, 7 edges, fully worked through with solution verification. The "greedy trap" note is a nice touch.
5. Note: The target problem MinimumFeedbackVertexSet does not yet exist as a model in the codebase, so implementing this rule will also require a new [Model] issue for the FVS problem itself. The overhead table references num_arcs which would need to be a getter on the new FVS type.

Recommendations

• Fix the false claim in Step 4 about only 2-cycles existing. Replace with a correct argument that hitting all 2-cycles suffices.
• Fix the path graph VC formula in the validation section: min VC of P_n is ⌈(n−1)/2⌉, not n−1.
• Consider filing a companion [Model] issue for MinimumFeedbackVertexSet (directed graph variant) before or alongside this rule, since the target problem does not yet exist.

[isPANN]

Fixed two errors identified in the review: corrected Step 4's false claim that G' contains only 2-cycles (longer cycles do exist but are automatically broken by any vertex cover), and fixed the minimum vertex cover formula for path P_n from n−1 to ⌈(n−1)/2⌉.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	Target problem (FeedbackVertexSet) not yet in codebase; novel reduction
Non-trivial	⚠️ Warn	Borderline — the construction is a direct structural embedding (each undirected edge becomes a bidirected 2-cycle), with no gadgets or auxiliary variables
Correctness	✅ Pass	References verified; reduction is the classic Karp (1972) construction confirmed by multiple sources
Well-written	⚠️ Warn	Minor notation issues and unverifiable target metric name

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

The target problem MinimumFeedbackVertexSet (or FeedbackVertexSet) does not exist in the codebase. Running pred show FeedbackVertexSet and pred show MinimumFeedbackVertexSet both fail. No existing path from MinimumVertexCover to any FeedbackVertexSet variant exists, so this would be a novel reduction adding a new edge to the reduction graph.

Note: This rule requires a new model issue for FeedbackVertexSet to be implemented first.

Non-trivial

The reduction replaces each undirected edge {u,v} with two directed arcs (u->v) and (v->u), keeping the same vertex set and budget. This means Vertex Cover is essentially a special case of Directed Feedback Vertex Set where all induced cycles have length 2. Multiple academic sources confirm this characterization:

"Its NP-completeness follows easily by a reduction from Vertex Cover, which is a special case of DFVS where all induced cycles have length two." — Data reduction for directed feedback vertex set (arXiv:2308.15900)

While the correctness argument is sound (hitting all 2-cycles implies hitting all longer cycles that must traverse some 2-cycle arc), the construction itself is a direct structural embedding with no gadgets, penalty terms, or auxiliary variables. This is borderline between "genuine structural transformation" and "subtype coercion." The issue is rated Warn rather than Fail because:

1. It does involve a change from undirected to directed graphs (different input structures).
2. The correctness proof that VC(G) = FVS(G') is non-obvious to someone unfamiliar with the result.
3. The reduction is historically significant (one of Karp's original 21).

Correctness

References verified:

• [Karp, 1972]: Confirmed. Richard M. Karp, "Reducibility among Combinatorial Problems", in Complexity of Computer Computations, Plenum Press, 1972, pp. 85-103. Already in the project bibliography as karp1972. Feedback Node Set is problem feat: Implement remaining reduction rules #7 in Karp's 21 NP-complete problems, and the reduction tree confirms Vertex Cover -> Feedback Node Set as a direct reduction.

• [Garey & Johnson, 1979]: Confirmed. Computers and Intractability: A Guide to the Theory of NP-Completeness. Already in the project bibliography as garey1979. GT7 is indeed Feedback Vertex Set. The GJ entry quoted in the issue matches the known content of Appendix A.

• [Gavril, 1977a] and [Shamir, 1977]: These are secondary references quoted from the GJ entry, not directly used in the reduction. Not independently verified but consistent with known literature.

The reduction construction itself (replace each undirected edge with two directed arcs) is confirmed as the standard reduction from VC to Directed FVS by multiple academic sources.

Important clarification on the reduction target: The issue title says "FEEDBACK VERTEX SET" and the GJ entry defines it on directed graphs. The issue correctly constructs a directed graph. However, the issue body alternates between calling the target "FeedbackVertexSet" and "MinimumFeedbackVertexSet" — the naming should be consistent. Per codebase conventions (minimization problems use Minimum prefix), it should be MinimumFeedbackVertexSet.

Note on Karp's original reduction: One source (Grokipedia) claims Karp's original DFVS reduction was from "exact cover by 3-sets" rather than from vertex cover. However, multiple other sources (Wikipedia, Karp's reduction tree) and the project's own references.md confirm the Vertex Cover -> Feedback Node Set path. The two are not contradictory — Karp may have shown multiple reduction paths. The VC -> DFVS reduction via bidirected arcs is well-established regardless of which specific path Karp used in his original paper.

Well-written

Template completeness: All required sections are present and substantive. The issue includes Source, Target, Motivation, Reference, Reduction Algorithm, Size Overhead, Validation Method, and Example sections. Good.

Minor issues:

1. Target metric name unverifiable: The overhead table lists num_arcs as a target metric. Since the target problem does not exist in the codebase, this cannot be verified against pred show. If the model is implemented as a directed graph problem, the metric might be num_arcs or num_edges depending on the implementation. This should be reconciled when the model is created.

2. Problem naming inconsistency: The issue uses both "FeedbackVertexSet" and "MinimumFeedbackVertexSet" in the body. Per codebase conventions, the problem name should consistently be MinimumFeedbackVertexSet.

3. AI-generated warnings: Multiple sections are marked with "Unverified: AI-generated" warnings, which is appropriate transparency but suggests the content should be reviewed by a domain expert.

4. Example quality: The example is well-constructed — 6 vertices, 7 edges, non-trivial structure, fully worked through with verification. The "greedy trap" observation is a nice touch. Good.

5. Algorithm completeness: The reduction algorithm is clear, step-by-step, and implementable. The correctness proof with both directions (forward and backward) is complete. Good.

Recommendations

• Consider creating a companion [Model] issue for MinimumFeedbackVertexSet first, since the target problem does not exist in the codebase. The rule cannot be implemented without the model.
• Standardize the problem name to MinimumFeedbackVertexSet throughout the issue.
• Clarify whether the target metric should be num_arcs or num_edges — this depends on how the directed graph model exposes its size fields.