Source: VERTEX COVER
Target: FEEDBACK ARC SET
Motivation: Establishes NP-completeness of FEEDBACK ARC SET via polynomial-time reduction from VERTEX COVER by splitting each vertex into an in-node and out-node connected by an internal arc, so that selecting a vertex cover corresponds to selecting the internal arcs that break every directed cycle.

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

GJ Source Entry

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

Reference: [Karp, 1972]. Transformation from VERTEX COVER.
Comment: Remains NP-complete for digraphs in which no vertex has total indegree and out-degree more than 3, and for edge digraphs [Gavril, 1977a]. Solvable in polynomial time for planar digraphs [Luchesi, 1976]. The corresponding problem for undirected graphs is trivially solvable in polynomial time.

Reduction Algorithm

Summary:
Given a MinimumVertexCover instance (G=(V,E), w) where G is an undirected graph with n=|V|, m=|E|, and vertex weights w: V → ℤ, construct a MinimumFeedbackArcSet instance (G'=(V',A'), w') as follows:

1. Vertex splitting: For each vertex v ∈ V, create two nodes: v^in and v^out. So V' = {v^in, v^out : v ∈ V}, giving |V'| = 2n.
2. Internal arcs: For each vertex v ∈ V, add arc (v^in → v^out) with weight w'(v^in → v^out) = w(v). These n arcs represent the vertices of G. Including this arc in the FAS corresponds to "selecting" vertex v in the vertex cover.
3. Crossing arcs: For each undirected edge {u,v} ∈ E, add two arcs: (u^out → v^in) and (v^out → u^in), each with weight w' = M, where M = 1 + Σ_{v ∈ V} w(v) (the penalty factor). These 2m arcs encode the adjacency of G.
4. Penalty factor: M is chosen so that any FAS containing a crossing arc has total weight ≥ M > the weight of any feasible vertex cover (since the heaviest possible VC uses all vertices, costing exactly Σ w(v) < M). Therefore, no optimal FAS will ever include a crossing arc.
5. Key invariant: Every directed cycle in G' must traverse at least one internal arc. A directed cycle necessarily follows the pattern: ... → u^in → u^out → v^in → v^out → u^in → ... (passing through two internal arcs and two crossing arcs). Since the penalty factor M ensures that no optimal FAS uses crossing arcs, the minimum-weight FAS consists entirely of internal arcs whose corresponding vertices form a minimum-weight vertex cover of G.
6. Solution extraction: Given an optimal FAS A', extract S = {v ∈ V : (v^in → v^out) ∈ A'}. This S is a minimum-weight vertex cover of G.

Correctness:

• (⇒) If S is a vertex cover for G of weight W, then A' = {(v^in → v^out) : v ∈ S} is a FAS of weight W. For any directed cycle C in G', C must use some crossing arc (u^out → v^in) for edge {u,v} ∈ E, and the cycle continues through (v^in → v^out) or (u^in → u^out). Since S covers {u,v}, at least one of these internal arcs is in A', so C is broken.
• (⇐) If A' is an optimal FAS, then A' contains only internal arcs: any FAS containing a crossing arc has weight ≥ M = 1 + Σ w(v), but the all-vertices vertex cover gives a FAS of weight Σ w(v) < M, so a crossing arc is never optimal. Then S = {v ∈ V : (v^in → v^out) ∈ A'} is a vertex cover: for each edge {u,v} ∈ E, the cycle u^in → u^out → v^in → v^out → u^in must be broken, so at least one of (u^in → u^out) or (v^in → v^out) is in A', meaning at least one of u, v is in S. The weight of S equals the weight of A'.

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	2 * num_vertices
num_arcs	num_vertices + 2 * num_edges

Derivation:

• Vertices: each original vertex v split into v^in and v^out → |V'| = 2n
• Arcs: n internal arcs (one per vertex) + 2m crossing arcs (two per edge) → |A'| = n + 2m

Note: MinimumFeedbackArcSet currently has empty size_fields. The num_vertices() and num_arcs() getters need to be added to the model as part of this PR for the #[reduction(overhead = {...})] macro to compile.

Validation Method

• Closed-loop test: reduce a weighted MinimumVertexCover instance to MinimumFeedbackArcSet, solve target with BruteForce, extract vertex cover (vertices whose internal arcs are in the FAS), verify it is a valid vertex cover on the original graph
• Check that the minimum-weight FAS in G' equals the minimum-weight VC in G
• Verify that the constructed digraph has exactly n + 2m arcs and 2n vertices
• Verify that internal arcs carry vertex weights and crossing arcs carry the penalty factor M = 1 + Σ w(v)
• Verify that no optimal FAS includes a crossing arc (any such FAS would cost ≥ M > Σ w(v) ≥ optimal VC weight)

Example

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

• Edges: {0,1}, {0,2}, {1,2}, {1,3}, {2,4}, {3,4}, {3,5}
• Vertex weights: w = [3, 2, 4, 5, 6, 1] (w(0)=3, w(1)=2, w(2)=4, w(3)=5, w(4)=6, w(5)=1)
• (Two triangles sharing vertices 1,2,3, with leaf vertex 5 attached to 3)
• Minimum weight vertex cover: {1, 2, 3} with weight 2+4+5 = 11:
  • {0,1} by 1 ✓, {0,2} by 2 ✓, {1,2} by 1,2 ✓, {1,3} by 1,3 ✓
  • {2,4} by 2 ✓, {3,4} by 3 ✓, {3,5} by 3 ✓

Constructed target instance (MinimumFeedbackArcSet):
Directed graph G' with 12 vertices and 20 arcs:

• Penalty factor: M = 1 + Σ w(v) = 1 + (3+2+4+5+6+1) = 22

Vertices: {0^in, 0^out, 1^in, 1^out, 2^in, 2^out, 3^in, 3^out, 4^in, 4^out, 5^in, 5^out}

Internal arcs (6 total, one per original vertex, weight = w(v)):

• (0^in → 0^out) w'=3, (1^in → 1^out) w'=2, (2^in → 2^out) w'=4
• (3^in → 3^out) w'=5, (4^in → 4^out) w'=6, (5^in → 5^out) w'=1

Crossing arcs (14 total, two per original edge, each with weight M=22):

• Edge {0,1}: (0^out → 1^in) w'=22 and (1^out → 0^in) w'=22
• Edge {0,2}: (0^out → 2^in) w'=22 and (2^out → 0^in) w'=22
• Edge {1,2}: (1^out → 2^in) w'=22 and (2^out → 1^in) w'=22
• Edge {1,3}: (1^out → 3^in) w'=22 and (3^out → 1^in) w'=22
• Edge {2,4}: (2^out → 4^in) w'=22 and (4^out → 2^in) w'=22
• Edge {3,4}: (3^out → 4^in) w'=22 and (4^out → 3^in) w'=22
• Edge {3,5}: (3^out → 5^in) w'=22 and (5^out → 3^in) w'=22

Total arcs: 6 + 14 = 20 arcs. (n + 2m = 6 + 14 = 20 ✓)

Example directed cycles in G':

• C_01: 0^in → 0^out → 1^in → 1^out → 0^in (length-4 cycle via edge {0,1})
• C_02: 0^in → 0^out → 2^in → 2^out → 0^in (length-4 cycle via edge {0,2})
• C_13: 1^in → 1^out → 3^in → 3^out → 1^in (length-4 cycle via edge {1,3})

Solution mapping:

• Selected internal arcs: A' = {(1^in → 1^out), (2^in → 2^out), (3^in → 3^out)}, total weight = 2+4+5 = 11
• Cycle C_01 broken: (1^in → 1^out) ∈ A' ✓
• Cycle C_02 broken: (2^in → 2^out) ∈ A' ✓
• Cycle C_13 broken: (1^in → 1^out) ∈ A' ✓
• All 7 corresponding cycles are broken by at least one internal arc in A' ✓
• Extracted vertex cover: S = {1, 2, 3} (vertices whose internal arcs are in A')
• Verification on G: all 7 edges covered ✓
• VC weight = FAS weight = 11 ✓

Why crossing arcs are never optimal: Any single crossing arc costs M=22, but the all-vertices VC {0,1,2,3,4,5} gives a FAS of weight Σ w(v) = 21 < 22 = M. So no optimal solution includes a crossing arc.

Greedy trap: Vertex 5 has the lowest weight (w(5)=1) and might be greedily selected first. But it only covers edge {3,5}, which is already covered by vertex 3 in any minimum VC containing vertex 3. Meanwhile, vertex 0 (w(0)=3) covers two edges ({0,1} and {0,2}), but selecting vertex 1 (w(1)=2) is cheaper and also covers {0,1}. The unique optimum {1,2,3} with weight 11 beats both the lighter-but-redundant choices and the heavier alternatives like {0,2,3} (weight 12).

References

• [Karp, 1972]: [Karp1972] Richard M. Karp (1972). "Reducibility among combinatorial problems". In: Complexity of Computer Computations. Plenum Press.
• [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.
• [Luchesi, 1976]: [Luchesi1976] Claudio L. Luchesi (1976). "A Minimax Equality for Directed Graphs". University of Waterloo.