[Model] PartialFeedbackEdgeSet

[isPANN]

Motivation

PARTIAL FEEDBACK EDGE SET (P20) from Garey & Johnson, A1.1 GT9. A classical NP-complete graph problem asking for the minimum number of edges to remove so that all cycles of length L or less are broken. This generalizes the standard feedback edge set problem (where L = |V|, which is trivially solvable) by restricting attention to short cycles, making the problem hard. It remains NP-complete for any fixed L >= 3.

Associated reduction rules:

• R282: VERTEX COVER -> PARTIAL FEEDBACK EDGE SET (this is the GJ reference reduction, by Yannakakis 1978)
• R115: FEEDBACK EDGE SET -> GROUPING BY SWAPPING (related: FEEDBACK EDGE SET is the L=|V| special case; the Partial variant is the source for P20)

Definition

Name: PartialFeedbackEdgeSet
Canonical name: Partial Feedback Edge Set (also: Bounded-Length Cycle Edge Transversal)
Reference: Garey & Johnson, Computers and Intractability, A1.1 GT9

Mathematical definition:

INSTANCE: Graph G = (V, E), positive integers K <= |E| and L <= |V|.
QUESTION: Is there a subset E' of E with |E'| <= K such that E' contains at least one edge from every circuit of length L or less in G?

The problem is a decision (satisfaction) problem: the answer is YES or NO depending on whether the bounded-length cycle transversal of size at most K exists.

Variables

• Count: |E| (one binary variable per edge)
• Per-variable domain: binary {0, 1} -- whether edge e in E is included in the feedback edge set E'
• Meaning: variable x_e = 1 if edge e is selected for removal. The configuration (x_{e_1}, ..., x_{e_m}) encodes a candidate subset E' of E. The assignment is valid if (1) the number of selected edges is at most K, and (2) every cycle of length <= L in G contains at least one selected edge.

Schema (data type)

Type name: PartialFeedbackEdgeSet<G>
Variants: Graph type G (SimpleGraph, PlanarGraph, BipartiteGraph)

Field	Type	Description
graph	G	The undirected graph G = (V, E)
budget	usize	The budget K: maximum number of edges to remove
max_cycle_length	usize	The cycle length bound L: all cycles of length <= L must be hit

Complexity

• Decision complexity: NP-complete (Yannakakis, 1978; transformation from VERTEX COVER). Remains NP-complete for any fixed L >= 3, and also for bipartite graphs with fixed L >= 4.
• Trivial case: When L = |V| (no length restriction), the problem asks for a feedback edge set, which is equivalent to finding a spanning forest. This is trivially solvable in polynomial time: remove exactly m - n + c edges, where c is the number of connected components (any spanning forest suffices).
• Best known exact algorithm: For general graphs, brute-force enumeration of all 2^|E| subsets of E in O(2^|E| * poly(|V|, |E|)) time, where checking the constraint requires finding all cycles of length <= L (which can be done in O(|V|^L) time by DFS). For the closely related feedback vertex set problem, exact algorithms run in O(1.7548^n) time (Fomin et al., 2006).
• Parameterized: For fixed L, the problem can be approached via bounded search tree methods. When parameterized by the solution size K, the problem is likely FPT for fixed L (since each short cycle provides a bounded branching factor).
• References:
  • [Yannakakis, 1978b] M. Yannakakis, "Node- and edge-deletion NP-complete problems", Proc. 10th STOC, pp. 253-264.
  • [Fomin et al., 2006] F. V. Fomin, S. Gaspers, A. V. Pyatkin, "Finding a minimum feedback vertex set in time O(1.7548^n)", IWPEC 2006.

Specialization

• This is a generalization of: VERTEX COVER restricted to triangle-free graphs (when L = 3, every cycle of length 3 = triangle must be hit; on graphs where every edge is in a triangle, this is close to vertex cover)
• Special cases:
  • L = |V|: Feedback Edge Set (polynomial-time solvable; equivalent to finding a spanning forest)
  • L = 3: every triangle must be hit by at least one edge removal
  • L = 4 on bipartite graphs: still NP-complete

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), positive integers K <= |E| and L <= |V|.
QUESTION: Is there a subset E' of E with |E'| <= K such that E' contains at least one edge from every circuit of length L or less in G?
Reference: [Yannakakis, 1978b]. Transformation from VERTEX COVER.
Comment: Remains NP-complete for any fixed L >= 3 and for bipartite graphs (with fixed L >= 4). However, if L = |V|, i.e., if we ask that E' contain an edge from every cycle in G, then the problem is trivially solvable in polynomial time.

How to solve

• It can be solved by (existing) bruteforce. Enumerate all subsets E' of E with |E'| <= K; for each subset, check if every cycle of length <= L in G contains at least one edge from E'. Cycle enumeration can be done by DFS up to depth L.
• It can be solved by reducing to integer programming. Introduce binary variable x_e for each edge e in E. For each cycle C = (e_1, ..., e_t) with t <= L, add constraint sum_{e in C} x_e >= 1. Minimize sum x_e subject to sum x_e <= K. (Note: the number of cycle constraints can be exponential, so a lazy constraint generation / cutting plane approach is needed in practice.)
• Other: (none identified)

Example Instance

Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 9 edges:

• Edges: {0,1}, {1,2}, {2,0}, {2,3}, {3,4}, {4,2}, {3,5}, {5,4}, {0,3}
• Budget K = 3
• Max cycle length L = 4

Cycles of length <= 4 (7 total):

• Length 3: (0,1,2) using edges {0,1}, {1,2}, {0,2}
• Length 3: (0,2,3) using edges {0,2}, {2,3}, {0,3}
• Length 3: (2,3,4) using edges {2,3}, {3,4}, {2,4}
• Length 3: (3,4,5) using edges {3,4}, {4,5}, {3,5}
• Length 4: (0,1,2,3) using edges {0,1}, {1,2}, {2,3}, {0,3}
• Length 4: (0,2,4,3) using edges {0,2}, {2,4}, {3,4}, {0,3}
• Length 4: (2,3,5,4) using edges {2,3}, {3,5}, {4,5}, {2,4}

No solution with K = 2 exists (verified by exhaustive search), so K = 3 is necessary.

Partial feedback edge set E' = {{0,2}, {2,3}, {3,4}} (size 3 = K):

• Triangle (0,1,2): edge {0,2} in E' — hit
• Triangle (0,2,3): edges {0,2}, {2,3} in E' — hit
• Triangle (2,3,4): edges {2,3}, {3,4} in E' — hit
• Triangle (3,4,5): edge {3,4} in E' — hit
• 4-cycle (0,1,2,3): edge {2,3} in E' — hit
• 4-cycle (0,2,4,3): edges {0,2}, {3,4} in E' — hit
• 4-cycle (2,3,5,4): edge {2,3} in E' — hit

All 7 cycles of length <= 4 are hit. |E'| = 3 <= K = 3. Answer: YES.

There are 5 distinct valid solutions with K = 3: {{0,1},{2,3},{3,4}}, {{1,2},{2,3},{3,4}}, {{0,2},{2,3},{3,4}}, {{0,2},{2,3},{3,5}}, and {{0,2},{2,3},{4,5}}.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in the reduction graph
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	❌ Fail	Incorrect complexity bound cited for Fomin et al. (2006)
Well-written	⚠️ Warn	Example section has self-corrections and messy reasoning

Overall: 2 passed, 1 failed, 1 warning

---

Usefulness

The problem PartialFeedbackEdgeSet does not exist in the current codebase. It is a classical problem from Garey & Johnson (GT9) with clear connections to Vertex Cover (via the Yannakakis 1978 reduction). The issue identifies two associated reduction rules (R282 and R115), providing graph connectivity. The motivation clearly explains what the problem is and why it matters.

Result: Pass

Non-trivial

This problem has genuinely different feasibility constraints from all existing problems in the codebase. No existing problem involves finding a minimum edge subset that hits all cycles up to a bounded length. The closest problems are MinimumVertexCover (vertex deletion, not edge deletion, and no cycle-length constraint) and standard Feedback Edge Set (which is polynomial-time for unbounded L). The bounded-length cycle constraint is what makes this NP-hard and structurally distinct.

Result: Pass

Correctness

References verified:

1. Yannakakis, 1978b — "Node- and edge-deletion NP-complete problems", Proc. 10th STOC, pp. 253-264. Verified. The paper exists at ACM DL and Semantic Scholar. The paper does establish NP-completeness for edge-deletion problems including cycle-related properties. The claim that this is the source of NP-completeness for the Partial Feedback Edge Set problem (via transformation from Vertex Cover) is consistent with the GJ reference.

2. Fomin, Gaspers, Pyatkin (2006) — "Finding a minimum feedback vertex set in time O(1.7548^n)", IWPEC 2006. The paper exists but the bound is misquoted. The issue body states "O(1.7347^n)" but the actual paper title and result is O(1.7548^n). See Springer. Additionally, this result is for the Feedback Vertex Set problem, not the Partial Feedback Edge Set — so citing it as evidence of the best known algorithm for this problem is misleading. No specific exact algorithm for Partial Feedback Edge Set is identified.

Result: Fail — The Fomin et al. complexity bound is incorrectly stated as 1.7347^n instead of 1.7548^n, and it applies to a different problem (Feedback Vertex Set, not Partial Feedback Edge Set).

Well-written

Template completeness: All required sections are present (Motivation, Name, Reference, Definition, Variables, Schema, Complexity, How to solve, Example Instance).

Definition: The formal definition is clear and matches the GJ formulation. The satisfaction/decision framing is appropriate.

Naming: PartialFeedbackEdgeSet is acceptable — as a satisfaction problem, it does not need a Minimum/Maximum prefix (consistent with Satisfiability, KSatisfiability, etc.).

Symbol consistency: Symbols are generally consistent across sections (G, V, E, K, L, E').

Example quality: The example is non-trivial (6 vertices, 9 edges) and the final answer is worked through. However, the example contains visible self-corrections and stream-of-consciousness reasoning ("wait, edge {5,4} and {3,5}" and "Actually: (3,5,4)..."). This makes the example harder to follow and suggests it was not carefully proofread. The cycle enumeration should be cleaned up into a definitive list without inline corrections.

ILP solver note: The How to solve section correctly notes that the ILP formulation may require exponential cycle constraints, but this is fine for the implementation since brute-force is the primary solver.

Result: Warn — The example section needs cleanup to remove self-corrections and present a clean worked example.

Recommendations

• Fix the Fomin et al. bound from 1.7347^n to 1.7548^n
• Clarify that the Fomin et al. result is for Feedback Vertex Set, not this problem — or find a specific exact algorithm reference for Partial Feedback Edge Set
• Clean up the example section to remove inline corrections and present a polished cycle enumeration
• Consider adding a declare_variants! complexity string — the brute-force bound O(2^|E| * poly) would be appropriate as a baseline

[isPANN]

Issue Quality Check — Model (Re-check)

Previous check: 2026-03-12 — 2 passed, 1 failed, 1 warning. This re-check: Same results — issue body appears unedited since last check.

Check	Result	Details
Usefulness	✅ Pass	Novel problem not in the reduction graph; planned reductions identified
Non-trivial	✅ Pass	Distinct feasibility constraints from all 112 existing problems
Correctness	❌ Fail	Fomin et al. (2006) complexity bound misquoted as 1.7347^n (actual: 1.7548^n)
Well-written	⚠️ Warn	Example contains inline self-corrections; needs cleanup

Overall: 2 passed, 1 failed, 1 warning

---

Usefulness

PartialFeedbackEdgeSet does not exist in the codebase (pred show fails). The issue identifies two associated reduction rules:

• R282: Vertex Cover → Partial Feedback Edge Set (Yannakakis 1978 — the GJ reference reduction)
• R115: Feedback Edge Set → Grouping by Swapping (related connection)

This provides concrete graph connectivity. Motivation clearly explains the problem's classical significance (GJ GT9) and the key insight that bounding cycle length L makes the otherwise-polynomial feedback edge set problem NP-complete.

Result: Pass

Non-trivial

The problem has genuinely distinct feasibility constraints from all existing problems. The closest are:

• MinimumFeedbackVertexSet — vertex deletion (not edge deletion), no cycle-length bound
• MinimumFeedbackArcSet — arc deletion in directed graphs, no cycle-length bound

No existing problem involves finding a minimum edge subset that hits all cycles up to a bounded length L. The max_cycle_length parameter is the distinguishing structural feature.

Result: Pass

Correctness

Yannakakis (1978b): ✅ Verified. "Node- and Edge-Deletion NP-Complete Problems", Proc. 10th STOC, pp. 253-264. Paper exists (ACM DL, Semantic Scholar). Establishes NP-completeness for edge-deletion problems including cycle-related properties, consistent with GJ's citation for GT9.

Fomin, Gaspers, Pyatkin (2006): ❌ Bound misquoted. The issue body states "O(1.7347^n)" but the actual result is O(1.7548^n) (IWPEC 2006, Algorithmica 2008). The O(1.7347^n) bound is from a different paper (Fomin & Villanger 2010, on maximum induced forests). Additionally, the issue correctly notes this is for Feedback Vertex Set, not Partial Feedback Edge Set — but the wrong number is still a factual error.

Best known algorithm: No specialized exact algorithm for Partial Feedback Edge Set was found in the literature. The brute-force O(2^|E|) bound stated in the issue is the de facto best known, which is appropriate.

Result: Fail — Incorrect complexity bound cited (1.7347^n → should be 1.7548^n).

Well-written

Template completeness: All required sections present — Motivation, Name, Reference, Definition, Variables, Schema, Complexity, How to solve, Example Instance with expected outcome. ✅

Definition: Clear and matches GJ formulation exactly. Satisfaction framing is correct. ✅

Naming: PartialFeedbackEdgeSet — satisfaction problem, no optimization prefix needed. ✅

Symbol consistency: Symbols (G, V, E, K, L, E') are consistent across sections. Schema field names (graph, budget, max_cycle_length) are clear. ✅

Example quality: The example (6 vertices, 9 edges, K=3, L=4) is non-trivial and exercises the core bounded-length cycle structure with both 3-cycles and 4-cycles. The expected outcome (E' = {{2,0}, {3,4}, {0,3}}) is provided with verification. However, the example contains visible self-corrections and stream-of-consciousness reasoning ("wait, edge {5,4} and {3,5}", "Actually: (3,5,4)...") that should be cleaned up into a definitive presentation.

Result: Warn — Example needs cleanup to remove inline corrections.

Recommendations

• Fix Fomin et al. bound from 1.7347^n to 1.7548^n (or remove the aside entirely since it's for a different problem)
• Clean up the example section: remove inline corrections, present a definitive cycle enumeration
• The journal version (Algorithmica 2008) adds Razgon as 4th author: Fomin, Gaspers, Pyatkin, Razgon
• Consider specifying the declare_variants! complexity string explicitly: "2^num_edges" (matching brute-force bound)

[isPANN]

Fix-issue changelog

• Complexity: Fixed Fomin et al. bound from O(1.7347^n) to O(1.7548^n) (confirmed via IWPEC 2006)
• Example — missing cycle: Added triangle (0,2,3) using edges {0,2}, {2,3}, {0,3}. The graph has 7 cycles of length ≤ 4, not 6.
• Example — incorrect solution: Changed E' from {{0,2}, {3,4}, {0,3}} to {{0,2}, {2,3}, {3,4}}. The previous solution missed cycle (2,3,5,4) — edge {3,4} is not in that cycle (it goes 3→5→4, not 3→4 directly). All corrections verified by exhaustive Python enumeration.
• Example — added completeness info: K=2 infeasibility confirmed; all 5 valid K=3 solutions listed.

Applied by /fix-issue.