[Model] MinimumFeedbackArcSet

[isPANN]

Motivation

FEEDBACK ARC SET from Garey & Johnson, A1.1 GT8. A classical NP-complete problem (Karp, 1972) that asks for the minimum number of arcs to remove from a directed graph to make it acyclic. It appears in ranking aggregation, sports tournament scheduling, deadlock avoidance, and causal inference. The problem is the "arc" analogue of the Feedback Vertex Set problem; unlike undirected feedback arc set (which is trivially solvable since every cycle must have an edge and spanning trees are cycle-free), the directed version is NP-complete.

Definition

Name: MinimumFeedbackArcSet
Canonical name: Directed Feedback Arc Set (DFAS); also: Minimum Feedback Arc Set, Minimum Acyclic Subgraph (complement formulation)
Reference: Garey & Johnson, Computers and Intractability, A1.1 GT8

Mathematical definition:

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?

The optimization version (which is the natural Rust model) asks: find the minimum-size subset A' ⊆ A such that G − A' is a directed acyclic graph (equivalently, find the maximum acyclic subgraph).

Variables

• Count: m = |A| binary variables (one per arc)
• Per-variable domain: binary {0, 1} — whether arc a ∈ A is included in the feedback arc set A'
• Meaning: variable x_a = 1 if arc a is selected into the FAS. The configuration (x_0, ..., x_{m-1}) encodes a candidate subset A' ⊆ A. The assignment is valid (a valid FAS) if for every directed cycle C in G, at least one arc of C has x_a = 1.

Schema (data type)

Type name: MinimumFeedbackArcSet
Variants: graph topology (directed graph type parameter)

Field	Type	Description
graph	DirectedGraph	The directed graph G = (V, A) on which a feedback arc set is sought

Notes:

• This is an optimization (minimization) problem: Metric = SolutionSize<i32>, implementing OptimizationProblem.
• The objective is to minimize |A'|, the number of selected arcs.
• Variables are indexed over arcs (edges), not vertices — the configuration space has dimension m = |A|.
• Key getter methods needed: num_vertices() (= |V|), num_edges() (= |A|). Note: although the problem literature uses "arcs" for directed edges, the getter is named num_edges() for consistency with the existing codebase convention (e.g., SimpleGraph::num_edges()).
• The complement formulation (maximum acyclic subgraph) keeps m − |A'| arcs and is equivalent.
• Prerequisite: The codebase does not currently have a DirectedGraph type. A separate issue and PR must be filed and merged to add a directed graph topology type to src/models/graph/ before this model can be implemented. The current graph types (SimpleGraph, PlanarGraph, BipartiteGraph, UnitDiskGraph, KingsSubgraph, TriangularSubgraph) are all undirected.

Complexity

• Decision complexity: NP-complete (Karp, 1972; transformation from VERTEX COVER per Garey & Johnson's presentation).
• Best known exact algorithm: O*(2^n) time via dynamic programming over subsets of vertices (Held-Karp style DP over vertex orderings; see Fomin & Kratsch, Exact Exponential Algorithms, Springer, 2010). This is the best known worst-case bound for the general directed FAS problem; improving this to sub-2^n is an explicit open problem. This is the bound to use in declare_variants!.
• Alternative exact approach: O*(2^m) brute force over arc subsets, where m = |A| (enumerate all 2^m subsets A' ⊆ A and check acyclicity). Practical exact methods use branch-and-bound with ILP or cycle enumeration (Baharev, Schichl, Neumaier, Achterberg, 2021).
• Polynomial-time solvable cases: Planar digraphs (Lucchesi & Younger, 1978; via the Lucchesi-Younger theorem relating minimum FAS to maximum cycle packing). Also solvable for DAGs (trivially: empty FAS).
• FPT (parameterized by k): Fixed-parameter tractable: O(4^k · k! · n^{O(1)}) algorithm. Note: FAS is FPT via a standard reduction to Directed Feedback Vertex Set (DFVS); the FPT algorithm is originally for DFVS by Chen, Liu, Lu, O'Sullivan, and Razgon (2008), and the FAS result follows because any FAS instance on G can be transformed to a DFVS instance on the line digraph of G with the same parameter. Whether FAS has a polynomial kernel remains open.
• References:
  • R.M. Karp (1972). "Reducibility Among Combinatorial Problems." Complexity of Computer Computations, pp. 85–103. Plenum Press. Original NP-completeness proof.
  • F.V. Fomin and D. Kratsch (2010). Exact Exponential Algorithms. Springer. Texts in Theoretical Computer Science. Reference for O*(2^n) DP approach to feedback arc set problems.
  • C.L. Lucchesi and D.H. Younger (1978). "A minimax theorem for directed graphs." Journal of the London Mathematical Society, 17(3):369–374. Polynomial time for planar digraphs.
  • J. Chen, Y. Liu, S. Lu, B. O'Sullivan, I. Razgon (2008). "A Fixed-Parameter Algorithm for the Directed Feedback Vertex Set Problem." Journal of the ACM, 55(5), Article 21. FPT result for DFVS; applicable to FAS via reduction to DFVS on the line digraph.
  • A. Baharev, H. Schichl, A. Neumaier, T. Achterberg (2021). "An Exact Method for the Minimum Feedback Arc Set Problem." ACM Journal of Experimental Algorithmics, 26, Article 1.4. Practical exact solver.

Specialization

• This is a special case of: (none — FAS is a fundamental problem)
• Known special cases: FAS on tournament graphs (every pair of vertices has exactly one arc; solvable in O*(1.6181^n) and has a 3-approximation), FAS on planar digraphs (polynomial time)
• Restriction: The undirected analogue (minimum feedback edge set in an undirected graph) is trivially polynomial — it equals m − (n − c) where c is the number of connected components (i.e., the number of non-tree edges in a spanning forest). The directed version is fundamentally harder due to directed cycle structure.

Extra Remark

Full book text:

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.

How to solve

• It can be solved by (existing) bruteforce. Enumerate all 2^m subsets A' ⊆ A; for each candidate, check if G − A' is a DAG (using a DFS-based cycle detection in O(n + m)). Total time O(2^m · (n + m)).
• It can be solved by reducing to integer programming. Introduce binary variable x_a for each arc a; minimize ∑x_a subject to: for each directed cycle C in G, ∑_{a ∈ C} x_a ≥ 1. (Exponentially many constraints, handled via iterative constraint generation / branch-and-cut.)
• Other: Dynamic programming over vertex subsets in O*(2^n) time (Held-Karp style; Fomin & Kratsch, 2010); exact branch-and-bound solvers (Baharev et al. 2021); FPT algorithms parameterized by k.

Example Instance

Directed graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 9 arcs:

• Arc list (indexed 0–8):
  • a₀: (0→1), a₁: (1→2), a₂: (2→0) — forms directed cycle C₁: 0→1→2→0
  • a₃: (1→3), a₄: (3→4), a₅: (4→1) — forms directed cycle C₂: 1→3→4→1
  • a₆: (2→5), a₇: (5→3), a₈: (3→0)

All simple directed cycles:

• C₁: 0 → 1 → 2 → 0 (arcs a₀, a₁, a₂)
• C₂: 1 → 3 → 4 → 1 (arcs a₃, a₄, a₅)
• C₃: 0 → 1 → 3 → 0 (arcs a₀, a₃, a₈)
• C₄: 2 → 5 → 3 → 0 → 1 → 2 (arcs a₆, a₇, a₈, a₀, a₁)

Budget: K = 2

Minimum FAS analysis:

• Can we break all cycles with 2 arcs?
  • Select A' = {a₂, a₅} = {(2→0), (4→1)}:
    • C₁ (a₀, a₁, a₂): a₂ ∈ A' ✓
    • C₂ (a₃, a₄, a₅): a₅ ∈ A' ✓
    • C₃ (a₀, a₃, a₈): neither a₂ nor a₅ appears. NOT broken ✗
  • Select A' = {a₀, a₄} = {(0→1), (3→4)}:
    • C₁ (a₀, a₁, a₂): a₀ ∈ A' ✓
    • C₂ (a₃, a₄, a₅): a₄ ∈ A' ✓
    • C₃ (a₀, a₃, a₈): a₀ ∈ A' ✓
    • C₄ (a₆, a₇, a₈, a₀, a₁): a₀ ∈ A' ✓
    • All cycles broken! ✓
  • Minimum FAS = {a₀, a₄} = {(0→1), (3→4)}, size = 2.

Verification:
After removing arcs (0→1) and (3→4), remaining arcs: (1→2), (2→0), (1→3), (4→1), (2→5), (5→3), (3→0). Check for directed cycles among remaining arcs by tracing from every vertex with outgoing arcs:

• From vertex 1: outgoing arcs = (1→2), (1→3).
  • 1→2→0 (vertex 0 has no outgoing arcs, sink) → dead end. ✓
  • 1→2→5→3→0 (sink) → dead end. ✓
  • 1→3→0 (sink) → dead end. ✓
  • No cycle through vertex 1. ✓
• From vertex 2: outgoing arcs = (2→0), (2→5).
  • 2→0 (sink) → dead end. ✓
  • 2→5→3→0 (sink) → dead end. ✓
  • No cycle through vertex 2. ✓
• From vertex 3: outgoing arcs = (3→0).
  • 3→0 (sink) → dead end. ✓
  • No cycle through vertex 3. ✓
• From vertex 4: outgoing arcs = (4→1).
  • 4→1→2→0 (sink) → dead end. ✓
  • 4→1→2→5→3→0 (sink) → dead end. ✓
  • 4→1→3→0 (sink) → dead end. ✓
  • No cycle through vertex 4. ✓
• From vertex 5: outgoing arcs = (5→3).
  • 5→3→0 (sink) → dead end. ✓
  • No cycle through vertex 5. ✓
• From vertex 0: no outgoing arcs (a₀ removed). Vertex 0 is a sink. ✓
• No directed cycle exists in the residual graph — this is a DAG. ✓

Budget: K = 2 → answer is YES (FAS of size ≤ 2 exists). For K = 1 → answer is NO (each of C₁, C₂, C₃ shares only arc a₀ between C₁ and C₃; removing a₀ still leaves C₂ intact).

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in the reduction graph; strong motivation with concrete applications
Non-trivial	✅ Pass	Distinct feasibility constraints (directed cycle hitting) from all existing problems
Correctness	⚠️ Warn	Minor factual inaccuracies in complexity section; O*(2^n) bound attribution unclear; no DirectedGraph type in codebase
Well-written	⚠️ Warn	Schema references nonexistent DirectedGraph type; GT8 numbering confusion; otherwise thorough and detailed

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

Pass. MinimumFeedbackArcSet does not exist in the codebase (pred show MinimumFeedbackArcSet returns "Unknown problem"). The motivation is strong: Feedback Arc Set is one of Karp's original 21 NP-complete problems (#8 in Karp's list), with concrete applications in ranking aggregation, tournament scheduling, deadlock avoidance, and causal inference. The issue mentions connections to existing problems (it is the "arc analogue" of Feedback Vertex Set, and has a reduction from Vertex Cover per Karp 1972). Solver methods are identified (brute-force, ILP, DP).

Non-trivial

Pass. MinimumFeedbackArcSet has genuinely different feasibility constraints from all 24 existing problems. Its constraint is "hit every directed cycle with at least one arc" on a directed graph -- no existing problem operates on directed graphs or has directed-cycle-hitting semantics. It is not a renaming or variant of any existing model. The closest existing problem is MinimumVertexCover (hitting edges rather than directed cycles), which is structurally very different.

Correctness

Warn. Several minor issues found:

1. Karp numbering confusion: The issue states FAS is "Item GT8 on Karp's original list of 21 NP-complete problems." GT8 is the Garey & Johnson appendix number, not a Karp list number. In Karp's 1972 paper, the problems are not numbered with "GT" prefixes -- that numbering system is from Garey & Johnson (1979). Karp's list has FAS as problem Reduction to unit-disk graphs #8 in the reduction tree (SAT -> Feedback Arc Set), which is correct in substance but the citation format is wrong.

2. NP-completeness reduction chain: The issue says "transformation from VERTEX COVER" which matches the Garey & Johnson book text. However, in Karp's original 1972 paper, FAS is reduced from SAT directly (not via Vertex Cover). The Vertex Cover -> FAS reduction is from Garey & Johnson's presentation. This is a minor citation imprecision.

3. O*(2^n) exact algorithm attribution: The issue attributes the O*(2^n) DP algorithm to "Bodlaender et al." and cites a 2009 kernelization survey paper. I could not verify that this specific paper contains an O*(2^n) algorithm for Minimum Feedback Arc Set. The O*(2^n) bound for FAS via DP over vertex orderings (Held-Karp style) is widely stated in the literature (e.g., Wikipedia on Feedback Arc Set confirms "O*(2^n) time via dynamic programming"), but the specific attribution to Bodlaender et al. (2009) is unverified. The Baharev et al. (2021) paper in ACM JEA is correctly cited and verified.

4. Luchesi vs Lucchesi: The issue spells the name "Luchesi" (one 'c') in some places. The correct spelling is "Lucchesi" (Claudio Leonardo Lucchesi). The 1978 paper in J. London Math. Soc. is real and verified.

5. FPT claim: The issue states "O(n^{O(1)} * 4^k * k!) algorithm via iterative compression" without a specific citation. This bound should be attributed to a specific paper for verifiability.

Well-written

Warn. The issue is generally thorough and well-structured, with a detailed worked example. Specific concerns:

1. Schema references nonexistent type: The schema proposes DirectedGraph as the graph type parameter, but the codebase has no DirectedGraph type. All existing graph types are: HyperGraph, SimpleGraph, PlanarGraph, BipartiteGraph, UnitDiskGraph, KingsSubgraph, TriangularSubgraph. A new directed graph type would need to be implemented first, which is a significant prerequisite not mentioned in the issue.

2. Missing getter method num_arcs(): The issue proposes num_arcs() as a getter, but this naming convention does not exist in the codebase. Existing problems use num_edges(), num_vertices(), num_vars(), num_clauses(), etc. The naming should be clarified -- will it be num_edges() or num_arcs()?

3. Complexity section mixes decision and optimization: The complexity section discusses both the decision problem (NP-complete) and the optimization problem (exact algorithms), which is appropriate, but the declare_variants! complexity string is not explicitly proposed. For implementation, a concrete string like "2^num_vertices" would be needed.

4. Example quality is good: The worked example with 6 vertices and 9 arcs is non-trivial, fully worked, and hand-verifiable. The "greedy trap" analysis is a nice touch. One minor issue: cycle C_4 enumeration has a self-correction in the text ("wait: a_8 is (3->0), so: ...") which should be cleaned up.

5. Symbol consistency is good: Variables (m, A, A', G, V) are consistently used across sections.

Recommendations

• Clarify the prerequisite: implementing MinimumFeedbackArcSet requires a new DirectedGraph type in the codebase, which is a separate model/infrastructure task
• Fix the Karp/Garey-Johnson numbering attribution
• Provide a specific citation for the O*(2^n) DP algorithm (e.g., reference the Held-Karp style DP directly, or cite Fomin & Kratsch "Exact Exponential Algorithms" textbook)
• Correct spelling to "Lucchesi" throughout
• Clean up the self-correction in the example's cycle C_4 enumeration

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; classical NP-complete problem (Karp's 21)
Non-trivial	✅ Pass	Distinct from all existing problems; directed graph + cycle-breaking objective is unique
Correctness	⚠️ Warn	One inaccurate citation attribution; minor author name inconsistency
Well-written	⚠️ Warn	Schema references non-existent DirectedGraph type; minor notation issues

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

Pass. MinimumFeedbackArcSet does not exist in the codebase (pred show returns not found). The problem is one of Karp's original 21 NP-complete problems (GT8 in Garey-Johnson) and has clear applications in ranking aggregation, deadlock avoidance, and causal inference. The motivation section is substantive and well-justified. The problem connects to the existing reduction graph via Vertex Cover (per Garey-Johnson's transformation) and potentially SAT, enabling future reduction rules.

Non-trivial

Pass. MinimumFeedbackArcSet is genuinely distinct from all 24 existing problems in the codebase:

• It operates on directed graphs (all current graph problems use undirected graphs)
• Its feasibility constraint is cycle-breaking (no existing problem has this structure)
• Variables are indexed over arcs/edges, not vertices (unlike MIS, MVC, MDS, etc.)
• It is not a variant or restriction of any existing problem

Correctness

Warn. Most claims are accurate, but there are issues:

1. Karp (1972) reference — correct. Feedback Arc Set is indeed one of Karp's 21 NP-complete problems. The Garey-Johnson book (GT8) states "Transformation from VERTEX COVER" which matches the issue's claim. Confirmed via multiple sources.

2. Lucchesi-Younger (1978) — correct but name inconsistency. The issue body uses both "Luchesi" (in the book text quote) and "Lucchesi" (in the references). The correct spelling is Lucchesi (Cláudio L. Lucchesi). The "Luchesi" spelling appears to come from Garey-Johnson's original text. The theorem and its implication (polynomial-time solvability for planar digraphs) are correct.

3. Baharev et al. (2021) — correct. Confirmed: published in ACM Journal of Experimental Algorithmics, Volume 26, Article 1.4, DOI: 10.1145/3446429. The description of their method (lazy cycle enumeration, branch-and-cut) matches.

4. Bodlaender et al. (2009) citation — inaccurate attribution. The issue cites "Bodlaender, Fomin, Lokshtanov, Penninkx, Saurabh, Thilikos (2009). Kernelization survey. Exact O*(2^n) DP baseline." However, this paper is actually "(Meta) Kernelization" (FOCS 2009) and is about kernelization meta-theorems, not about establishing the O*(2^n) DP bound for FAS. The O*(2^n) DP for minimum feedback arc set is a well-known result based on Held-Karp style dynamic programming over vertex subsets/orderings, but it should not be attributed to this specific paper. Recommendation: Replace this citation with a direct reference to the Held-Karp DP approach or cite a source that explicitly states the O*(2^n) bound for FAS.

5. O(2^n) complexity claim — correct.* The best known exact algorithm is indeed O*(2^n) via dynamic programming over vertex subsets (Held-Karp style), confirmed by multiple sources including the Wikipedia article on feedback arc sets.

6. FPT claim — needs verification. The issue mentions "O(n^{O(1)} · 4^k · k!) algorithm via iterative compression" but does not cite a specific paper for this bound. This should have a concrete citation.

Well-written

Warn. The issue is generally well-structured and thorough, but has some issues:

Strengths:

• All template sections are present and substantive
• The example is non-trivial (6 vertices, 9 arcs, 4 cycles) and fully worked
• Brute-force solvability is confirmed
• The "greedy trap" discussion adds pedagogical value

Issues to address:

1. DirectedGraph type does not exist in the codebase. The schema proposes graph: DirectedGraph but the codebase only has SimpleGraph, PlanarGraph, BipartiteGraph, UnitDiskGraph, KingsSubgraph, and TriangularSubgraph — all undirected. Implementing this model will require creating a new directed graph type. This should be explicitly noted in the issue as a prerequisite.

2. "P19" designation is unclear. The opening line says "FEEDBACK ARC SET (P19) from Garey & Johnson, A1.1 GT8." The "P19" is ambiguous — it could be page 19 or problem Implement integer programming solver for Coloring problem #19 in some listing. The Garey-Johnson designation is GT8, which is clear enough on its own.

3. Missing num_arcs getter clarification. The issue mentions num_arcs() as a getter method but the codebase convention uses num_edges() for edge counts. Since this is a directed graph, using num_arcs() may be appropriate, but this naming choice should be explicitly justified against the codebase pattern.

4. Verification section is slightly incomplete. The DAG verification after removing {a_0, a_4} only checks paths starting from vertices 0 and 1 explicitly. While the conclusion is correct (the graph is indeed a DAG), a complete verification should trace from all vertices with outgoing arcs (especially vertex 4, which has outgoing arc a_5=(4->1)).

5. FPT citation missing. The FPT algorithm bound "O(n^{O(1)} · 4^k · k!)" is stated without a specific citation.

Recommendations

• Fix the Bodlaender et al. citation to properly attribute the O*(2^n) DP result
• Add a note that implementing this model requires creating a DirectedGraph topology type as a prerequisite
• Add a specific citation for the FPT result
• Standardize the author spelling to "Lucchesi" throughout (the "Luchesi" variant in the book text quote can remain as a faithful quotation)