k-Product Lists for (Generalized) Feedback Vertex Sets: A Tool for Designing FPT Algorithms
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "k-Product Lists for (Generalized) Feedback Vertex Sets".
Jane: Here's the gist of the paper. Enumerating all inclusion-minimal solutions is a powerful approach to designing fixed-parameter tractable (FPT) algorithms However, for the Feedback Vertex Set problem, this approach faces a fundamental obstacle, as the number of minimal feedback vertex sets is not, in general, bounded by any function of the solution size k <ref:2611.15024#pg3> To overcome this limitation, we introduce a data structure called a k-product list <ref:2611.15024#pg2> which implicitly encodes all minimal solutions while admitting non-minimal ones to maintain efficiency <ref:2611.15024#pg5> We present FPT algorithms for computing such lists not only for the Feedback Vertex Set problem but also for its natural generalizations, the l-Forest Deletion Set problem and the r-Pseudoforest Deletion Set problem <ref:2611.15024#pg2>.
Tom: Our framework yields simple FPT algorithms for a wide range of variants, providing the first such results in several cases and demonstrating the broad applicability of our approach <ref:2611.15024#pg6>.
Jane: The paper addresses the difficulty of enumerating minimal feedback vertex sets because their number is not bounded by a function of the solution size k <ref:2611.15024#pg4> The authors introduce a concept called a compact representation, which is a family of pairwise disjoint vertex subsets such that selecting exactly one vertex from each set in C always yields a minimal feedback vertex set <ref:2611.15024#pg5> A k-compact list of feedback vertex sets is defined as a collection L of k-compact representations where every minimal feedback vertex set of G of size at most k is represented by at least one C in L <ref:2611.15024#pg5>.
Tom: This structure allows for the construction of FPT algorithms for many variants <ref:2611.15024#pg4>.
Title and authors: Tom: So we're looking at the paper "k-Product Lists for (Generalized) Feedback Vertex Sets: A Tool for Designing FPT Algorithms." They are tackling the problem of finding all minimal feedback vertex sets, which is tough because there isn't a bound on how many there can be based on the solution size k <ref:2611.15024#pg1>.
Jane: Exactly. The authors introduce this idea called a k-product list, which they say implicitly encodes all those minimal solutions while also letting you include non-minimal ones to keep the algorithm efficient <ref:2611.15024#pg5>.
Lu: That means instead of having to list every single minimal set one by one, you have this structured data that lets you check for small sets much faster <ref:2611.15024#pg5>.
Meng: So for us in production, that structured approach means we can check if a small feedback vertex set exists in fixed-parameter tractable time, which is good <ref:2611.15024#pg4>.
Tom: They show this works not just for the basic feedback vertex set problem but also for more complex versions like the l-Forest Deletion Set and the r-Pseudoforest Deletion Set problems <ref:2611.15024#pg2>.
Jane: And they give us a construction time for these lists that is polynomial relative to the graph size, with an exponential part only in terms of k and L or R <ref:2611.15024#pg3>.
Lu: That running time analysis shows they can actually build these k-product lists in time O of 17k, which is pretty fast compared to what was possible before for the general feedback vertex set problem <ref:2611.15024#pg4>.
Meng: For deployment, the real question is how much overhead this list structure adds when we run it against really large graphs or heavy traffic <ref:2611.15024#pg7>.
Tom: The framework shows that this works for a wide range of variants, including weighted problems with cardinality constraints or nonpartisan problems with capacity constraints on partitions <ref:2611.15024#pg7>.
Jane: They also extend their work to reconfiguration problems, showing that things like Connected l-Forest Deletion Set Reconfiguration are fixed-parameter tractable when parameterized by k plus l <ref:2611.15024#pg5>.
Lu: And they used this idea to solve Nonpartisan F-Deletion Set problems by reducing them to Maximum Weight b-Matching on a bipartite graph built from the k-product list <ref:2611.15024#pg2>.
Meng: That reduction sounds pretty complicated; I wonder how that translates into something we can deploy quickly without it slowing down when it hits real traffic <ref:2611.15024#pg3>.
Tom: The idea is that this list structure helps us find those solutions efficiently, and for conflict-free F-Deletion Set problems, they use a property where if a solution exists, it must be represented by some component in that list <ref:2611.15024#pg7>.
Jane: It really shows how taking something like representation learning and turning it into a structured list can translate directly into concrete fixed-parameter tractable algorithms for many different scenarios <ref:2611.15024#pg4>.
Lu: The one thing they flag as a limitation is that they don't have strong lower bounds on the size of those k-product lists, which means we don't know the absolute worst-case storage requirement <ref:2611.15024#pg2>.
Meng: That lack of a tight lower bound is something I’m worried about when trying to estimate resource needs for production systems <ref:2611.15024#pg3>.
Tom: Right, and that’s the practical hurdle for deployment: you need to know the worst-case storage before you can confidently run it on production traffic <ref:2611.15024#pg3>.
Jane: But they did show that for reconfiguration problems, they get fixed-parameter tractable algorithms parameterized by k plus l or k plus r <ref:2611.15024#pg6>. That adds some complexity to the parameterization but keeps it manageable <ref:2611.15024#pg5>.
Lu: And they did show how this applies to fairness constraints in Nonpartisan F-Deletion Set problems using Maximum Weight b-Matching on a bipartite graph constructed from that list <ref:2611.15024#pg2>. That’s a pretty specific application of the idea <ref:2611.15024#pg8>.
Meng: I just hope the complexity of that reduction doesn't make it too slow when we try to deploy it to something that actually sees real traffic <ref:2611.15024#pg3>.
Tom: So, the paper provides a strong blueprint for using structured representations, like k-product lists, to tackle these combinatorial search problems efficiently parameterized by k <ref:2611.15024#pg6>.
Jane: It’s definitely a tool that opens up new ways to design algorithms for structural graph problems <ref:2611.15024#pg7>.
Lu: The authors are clearly pushing toward those lower bounds on list sizes as the next big theoretical challenge in this area <ref:2611.15024#pg2>.
Meng: I'm curious to see if we can get some practical estimates for those storage requirements soon <ref:2611.15024#pg3>.
Tom: Alright, that’s it for this one on "k-Product Lists for (Generalized) Feedback Vertex Sets: A Tool for Designing FPT Algorithms." Next week, we’re going to look at how AI can steer collective opinion in online communication.
The paper's summary: Tom: So we're looking at the summary of this paper today, "k-Product Lists for (Generalized) Feedback Vertex Sets: A Tool for Designing FPT Algorithms." Basically, they've taken all those complicated minimal solutions and organized them into this structured list called a k-product list.
Jane: That means instead of searching through every single potential feedback vertex set one by one, you have this organized structure that lets you check for the small ones efficiently. It’s about encoding them in a way that makes the search much faster.
Lu: Yeah, they define a compact representation where you pick exactly one vertex from each set in some collection C, and that combination always gives you a minimal feedback vertex set. Then they take the collection of all these representations up to size k and call it a k-compact list.
Meng: So for someone trying to deploy this on a huge network, this list structure means you can check if there's a small feedback vertex set in fixed-parameter tractable time. That’s the practical part for real systems.
Tom: And they show this isn't just for the basic feedback vertex set problem, but it works for these more complex versions too, like l-Forest Deletion Sets and r-Pseudoforest Deletion Sets. It handles those structural constraints cleanly.
Jane: They give us the construction time for these lists, and it's polynomial relative to the graph size, but exponential only in terms of k and L or R. That’s the machinery behind it.
Lu: And they also extended this to reconfiguration problems using something called the Token Jumping rule. It means you can find a good configuration under those rules in time parameterized by k plus l or k plus r. It shows the core idea is robust across different problem statements.
Meng: So for reconfiguration, it's parameterized by k plus some extra constant, which keeps the complexity manageable when k is small. That’s the part that matters for deployment.
Tom: And they showed how this framework helps with fairness constraints in those Nonpartisan F-Deletion Set problems by reducing them to Maximum Weight b-Matching on a bipartite graph built from that list. That’s a pretty specific application of the idea.
Jane: It really shows how taking something like representation learning and turning it into a structured list can translate directly into concrete, deployable fixed-parameter tractable algorithms for many different scenarios.
Lu: The one thing they flag as a limitation is that they don't have strong lower bounds on the size of those k-product lists. This means we don't know the absolute worst-case storage requirement.
Meng: That lack of a tight lower bound is something I’m worried about when trying to estimate resource needs for production systems.
Tom: Right, and that's the practical hurdle for deployment: you need to know the worst-case storage before you can confidently run it on production traffic.
Jane: But they did show that for reconfiguration problems, they get fixed-parameter tractable algorithms parameterized by k plus l or k plus r. That adds some complexity to the parameterization but keeps it manageable.
Lu: And they did show how this applies to fairness constraints in Nonpartisan F-Deletion Set problems using Maximum Weight b-Matching on a bipartite graph constructed from that list. That’s a pretty specific application of the idea.
Meng: I just hope the complexity of that reduction doesn't make it too slow when we try to deploy it to something that actually sees real traffic.
Tom: So, the paper provides a strong blueprint for using structured representations, like k-product lists, to tackle these combinatorial search problems efficiently parameterized by k.
Jane: It’s definitely a tool that opens up new ways to design algorithms for structural graph problems.
Lu: The authors are clearly pushing toward those lower bounds on list sizes as the next big theoretical challenge in this area.
Meng: I'm curious to see if we can get some practical estimates for those storage requirements soon.
Tom: Alright, that’s it for this one on k-Product Lists for (Generalized) Feedback Vertex Sets: A Tool for Designing FPT Algorithms. Next week, we’re going to look at how AI can steer collective opinion in online communication.
The paper's improvements: Tom: So we're talking about how these authors suggest improving their k-product list approach now. They aren't just showing a static structure; they're talking about how to actually use that list in an algorithm.
Jane: Instead of just saying the list exists, they are proposing a way to search through it that is faster than doing a brute force check on all possible sets. It’s about making the actual searching process efficient.
Lu: They introduce two main procedures for this, ComputeList and Search, where ComputeList is the high-level controller and Search does the actual recursive branching to build those k-product representations.
Meng: What’s the kicker here? They rely on an auxiliary problem where they compute a collection, let's call it L hat. This collection represents every minimal F-deletion set of a graph G hat. That sounds like a lot of setup work just to get the right data structure ready for the search.
Tom: And this whole framework is what lets them apply it to all those different problems—the l-Forest Deletion Set and r-Pseudoforest Deletion Set ones. It’s a unified way to handle the structural constraints of the problem.
Jane: So, when you look at the results, they show that this framework yields fixed-parameter tractable algorithms for a wide variety of variants like weighted or connected problems. It’s showing broad applicability across different graph types.
Lu: For the reconfiguration variants, they show that existing algorithms based on k-compact lists can be extended directly to those settings. It’s showing how robust the core idea is across different problem statements.
Meng: I still worry about the complexity of that auxiliary problem, L hat. If we have to solve that thing every time we want to check a graph, does it make the overall runtime too slow for real-time deployment?
Tom: The authors address that by showing the running time for constructing those lists is quite good. It's around O of c six four L times seventeen k squared or something depending on L and R. That’s a lot of work just to build the structure.
Jane: And then they show that even with that setup cost, the final algorithm to compute the list itself runs in O of seventeen k. That’s a big win for the actual search phase.
Lu: The most interesting part for future work, which they mention, is establishing those lower bounds on the size of these k-product lists. They know the structure exists, but they don't know how big it gets in the worst case.
Meng: So they admit they don't fully understand the storage complexity of this list structure yet. That’s a real limitation for me when I think about deploying this on a system with limited memory.
Tom: It sounds like the next step is figuring out those bounds, because if we know how big the list can get, we can design better memory management or pruning techniques.
Jane: The implication here is that taking a high-level idea from representation learning and turning it into a structured list can lead to concrete, deployable fixed-parameter tractable algorithms for many different scenarios.
Lu: The authors are clearly pushing toward those lower bounds on list sizes as the next big theoretical challenge in this area.
Meng: I'm curious to see if we can get some practical estimates for those storage requirements soon.
Tom: Alright, that’s it for this one on k-Product Lists for (Generalized) Feedback Vertex Sets: A Tool for Designing FPT Algorithms. Next week, we’re going to look at how AI can steer collective opinion in online communication.
Conclusion: Tom: So we're wrapping up our look at "k-Product Lists for (Generalized) Feedback Vertex Sets: A Tool for Designing FPT Algorithms." Basically, they showed how encoding minimal solutions into a k-product list creates a unified framework for finding fixed-parameter tractable algorithms across many graph problems.
Jane: It sounds like the main implication is that you don't have to treat every single problem in this family as totally separate; you can use this list structure to tackle them all with the same kind of efficiency.
Lu: Exactly, and they demonstrated it works for things like weighted problems and nonpartisan problems with capacity constraints, parameterizing them by k. It’s showing how representation learning techniques can translate directly into concrete fixed-parameter tractable algorithms.
Meng: I still see the limitation being that they don't have solid lower bounds on the size of those k-product lists. That means we don't know exactly how much memory this list structure will chew up on a massive graph.
Tom: Right, and that’s the practical hurdle for deployment: you need to know the worst-case storage before you can confidently run it on production traffic.
Jane: But they did show that for reconfiguration problems, they get fixed-parameter tractable algorithms parameterized by k plus l or k plus r. That adds some complexity to the parameterization but keeps it manageable.
Lu: And they did show how this applies to fairness constraints in Nonpartisan F-Deletion Set problems using Maximum Weight b-Matching on a bipartite graph constructed from that list. That’s a pretty specific application of the idea.
Meng: I just hope the complexity of that reduction doesn't make it too slow when we try to deploy it to something that actually sees real traffic.
Tom: So, the paper provides a strong blueprint for using structured representations, like k-product lists, to tackle these combinatorial search problems efficiently parameterized by k.
Jane: It’s definitely a tool that opens up new ways to design algorithms for structural graph problems.
Lu: The authors are clearly pushing toward those lower bounds on list sizes as the next big theoretical challenge in this area.
Meng: I'm curious to see if we can get some practical estimates for those storage requirements soon.
Tom: Alright, that’s it for this one on "k-Product Lists for (Generalized) Feedback Vertex Sets: A Tool for Designing FPT Algorithms." Next week, we’re going to look at how AI can steer collective opinion in online communication.
Graduate School of Information Sciences, Tohoku University
cs.DS
Submitted: 2026-11-11
Updated: 2026-11-11
Comments: 38 pages, Full version of the IPEC 2026 paper
Code: https://github.com/srin728/ProductList_analysis
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 92/100
The gist: Enumerating all inclusion-minimal solutions is a powerful approach to designing fixed-parameter tractable (FPT) algorithms However, for the Feedback Vertex Set problem…
Key concepts
- Minimal Feedback Vertex Set
- A minimal feedback vertex set is a smallest group of vertices whose removal breaks all cycles in a graph. The paper struggles with enumerating all such sets efficiently because there isn't a simple bound on how many minimal solutions exist for a given size k.
- k-Product List
- This is a data structure that implicitly represents every minimal solution of size at most k. It works by defining 'k-compact representations,' which are disjoint vertex subsets, ensuring that selecting one from each representation always yields a minimal feedback vertex set.
- FPT Algorithm
- Fixed-Parameter Tractable (FPT) algorithms are designed to solve hard problems by making the running time dependent only on a parameter 'k' (like the solution size), while being polynomial in the input size. The paper uses these algorithms to find solutions for complex graph variants efficiently.
Terminology
Summary
Enumerating all inclusion-minimal solutions is a powerful approach to designing fixed-parameter tractable (FPT) algorithms However, for the Feedback Vertex Set problem, this approach faces a fundamental obstacle, as the number of minimal feedback vertex sets is not, in general, bounded by any function of the solution size k <ref:2611. p. 0 k-Product Lists for (Generalized) Feedback Vertex
Sets: A Tool for Designing FPT Algorithms
Rin Saito #
Graduate School of Information Sciences, Tohoku University, Sendai, Japan
Yuma Tamura #
Graduate School of Information Sciences, Tohoku University, Sendai, Japan
Abstract
Enumerating all inclusion-minimal solutions is a powerful approach to designing fixed-parameter
tractable (FPT) algorithms. However, for the Feedback Vertex Set problem, this approach faces
a fundamental obstacle, as the number of minimal feedback vertex sets is not, in general, bounded by
any function of the solution size k. However, for the Feedback Vertex Set problem, this approach faces
a fundamental obstacle, as the number of minimal feedback vertex sets is not, in general, bounded by
any function of the solution size k. To overcome this limitation, we introduce a data structure called
a k-product list, which implicitly encodes all minimal solutions while admitting non-minimal ones to
maintain efficiency. However, for the Feedback Vertex Set problem, this approach faces
a fundamental obstacle, as the number of minimal feedback vertex sets is not, in general, bounded by
any function of the solution size k. To overcome this limitation, we introduce a data structure called
a k-product list, which implicitly encodes all minimal solutions while admitting non-minimal ones to
maintain efficiency. To overcome this limitation, we introduce a data structure called
a k-product list, which implicitly encodes all minimal solutions while admitting non-minimal ones to
maintain efficiency. We present FPT algorithms for computing such lists not only for the Feedback
Vertex Set problem but also for its natural generalizations, the ℓ-Forest Deletion Set problem
and the r-Pseudoforest Deletion Set problem. We present FPT algorithms for computing such lists not only for the Feedback
Vertex Set problem but also for its natural generalizations, the ℓ-Forest Deletion Set problem
and the r-Pseudoforest Deletion Set problem. Our framework yields simple FPT algorithms
for a wide range of variants, providing the first such results in several cases and demonstrating the
broad applicability of our approach.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Introduction to Minimal Solution Encoding
The paper addresses the difficulty of enumerating minimal feedback vertex sets because their number is not bounded by a function of the solution size k <ref:2611.15024#pg4> The authors introduce a concept called a compact representation, which is a family of pairwise disjoint vertex subsets such that selecting exactly one vertex from each set in C always yields a minimal feedback vertex set <ref:2611. p. 2 Intuitively,
a list of compact representations is a data structure of FPT size that implicitly encodes a
family of minimal feedback vertex sets. Formally, a compact representation of a graph G is a family C of pairwise disjoint vertex
subsets of G such that selecting exactly one vertex from each set in C always yields a minimal
feedback vertex set of G. For a positive integer k, a compact representation C is called
k-compact if |C| ≤ k. A collection L of k-compact representations is called a k-compact list of
feedback vertex sets if every minimal feedback vertex set of G of size at most k is represented
by at least one C ∈ L. To overcome this limitation, we introduce a data structure called
a k-product list, which implicitly encodes all minimal solutions while admitting non-minimal ones to
maintain efficiency. We present FPT algorithms for computing such lists not only for the Feedback
Vertex Set problem but also for its natural generalizations, the ℓ-Forest Deletion Set problem
and the r-Pseudoforest Deletion Set problem.Where the paper says it
Where the paper says it
Where the paper says it
The Algorithmic Framework
The core of the paper is a unified algorithmic framework consisting of two procedures, ComputeList and Search <ref:2611.15024#pg9> ComputeList controls the overall execution, while Search implements a recursive branching algorithm that constructs k-product representations <ref:2611. p. 7 Our framework consists of two procedures: ComputeList and Search. At a high level,
ComputeList controls the overall execution of the algorithm, while Search implements a
recursive branching algorithm that constructs k-product representations. A minimal F-deletion set Dˆ of
Gˆ is said to be compatible with an instance (G, k, F, L, C) of the auxiliary problem if there
exists a minimal F-deletion set D of G satisfying the following three conditions:
|D| ≤ k; and
F ∩ D = ∅; and
C ∪ {L(v) | v ∈ D} represents Dˆ. The goal of the auxiliary problem is to compute a collection Lˆ of ˆk-product representations
that represents every minimal F-deletion set of Gˆ compatible with (G, k, F, L, C).Where the paper says it
Where the paper says it
Analysis for Generalized Deletion Sets
The authors present the framework for both l-forest deletion sets and r-pseudoforest deletion sets <ref:2611.15024#pg2> The running time analysis shows that k-product lists can be constructed in time O∗(64l · 17k)2, or O∗(csr) for l ≥ 0 and r ≥ 1, respectively <ref:2611. p. 3 ) It is known that deciding whether a
given graph admits such a deletion set of size at most k is fixed-parameter tractable when
parameterized by k + ℓ and k + r, respectively [39, 42]. We show that k-product lists for
these generalizations can also be constructed in time O∗
(64ℓ
· 17k
)
2 and O∗
(c
k
r
) for ℓ ≥ 0 and
r ≥ 1, respectively, where cr is a constant depending only on r. We show that k-product lists for
these generalizations can also be constructed in time O∗
(64ℓ
· 17k
)
2 and O∗
(c
k
r
) for ℓ ≥ 0 and
r ≥ 1, respectively, where cr is a constant depending only on r. As a corollary, we obtain
an algorithm for computing a k-product list of feedback vertex sets in time O∗
(17k
).Where the paper says it
Where the paper says it
Applications to Problem Variants
The framework yields FPT algorithms for a wide range of variants, including weighted, connected, nonpartisan, hereditary-property, conflict-free, simultaneous, reconfiguration, and diverse variants <ref:2611.15024#pg7> For the weighted variant with cardinality constraints or the nonpartisan variant with capacity constraints on partitions Vi is fixed-parameter tractable when parameterized by k <ref:2611. p. 1 1 Weighted F-Deletion Set with Cardinality Constraints . 2 Nonpartisan Variant . Yuma Tamura: This work was supported by JSPS KAKENHI Grant Numbers JP25K21148 and
JP24H00686. arXiv:2611. As a consequence, our framework yields FPT algorithms for a wide range of variants of
ℓ-forest deletion sets and r-pseudoforest deletion sets, including the weighted, nonpartisan,
hereditary-constraint, reconfiguration, connected, conflict-free, simultaneous, and diverse
variants (see Section 6 for definitions). For the connected and diverse variants, existing
algorithms based on k-compact lists extend directly to our setting.Where the paper says it
Where the paper says it
Where the paper says it
Conclusion and Open Problems
The paper concludes by showing that both Connected l-Forest Deletion Set Reconfiguration and r-Pseudoforest Deletion Set Reconfiguration are fixed-parameter tractable under the Token Jumping rule when parameterized by k + l and k + r, respectively <ref:2611.15024#pg5>, <ref:2611. p. 0 Yuma Tamura: This work was supported by JSPS KAKENHI Grant Numbers JP25K21148 and
JP24H00686. arXiv:2611. (See Section 2 for formal definitions; when ℓ = r = 0,
these notions coincide with feedback vertex sets. ) It is known that deciding whether a
given graph admits such a deletion set of size at most k is fixed-parameter tractable when
parameterized by k + ℓ and k + r, respectively [39, 42].Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved FPT algorithms for Feedback Vertex Set problems by introducing k-product lists, which implicitly encode all minimal solutions while maintaining efficiency for non-minimal ones. This allows for faster enumeration than standard inclusion-minimal solution approaches, achieving running times like O(17k) for Feedback Vertex Set.
-
Computation of generalized deletion set lists, such as l-Forest Deletion Sets and r-Pseudoforest Deletion Sets, in time O(c k r) or O(13k), providing FPT algorithms for a wide range of structural variants like weighted, connected, and nonpartisan problems.
-
Designing algorithms for combinatorial reconfiguration problems using the k-product list framework by characterizing when two representations are adjacent under the Token Jumping rule via a compressed configuration graph GL. This allows for fixed-parameter tractable solutions to Feedback Vertex Set Reconfiguration parameterized by k.
-
Solving Nonpartisan F-Deletion Set problems by reducing them to Maximum Weight b-Matching on a bipartite graph constructed from the k-product list, enabling an FPT algorithm parameterized by k for fairness constraints.
-
Solving Connected F-Deletion Set problems via reduction to the Group Steiner Tree problem for each product representation, which is known to be fixed-parameter tractable parameterized by k, leading to an FPT algorithm parameterized by k.
-
Solving Conflict-Free F-Deletion Set problems by reducing them to the F+Cluster Independent Set problem and utilizing the property that if a solution S exists, it can be represented by some C in the list. This yields an FPT algorithm parameterized by k for conflict-free variants when H belongs to certain sparse graph classes like Ki,j-free graphs.
-
Solving Simultaneous F-Deletion Set problems by reducing them to the Hitting Set problem using a tuple of k-product lists as hyperedges, resulting in an FPT algorithm parameterized by alpha + k.
Abstract
Enumerating all inclusion-minimal solutions is a powerful approach to designing fixed-parameter tractable (FPT) algorithms. However, for the Feedback Vertex Set problem, this approach faces a fundamental obstacle, as the number of minimal feedback vertex sets is not, in general, bounded by any function of the solution size k. To overcome this limitation, we introduce a data structure called a k-product list, which implicitly encodes all minimal solutions while admitting non-minimal ones to maintain efficiency. We present FPT algorithms for computing such lists not only for the Feedback Vertex Set problem but also for its natural generalizations, the-Forest Deletion Set problem and the r-Pseudoforest Deletion Set problem. Our framework yields simple FPT algorithms for a wide range of variants, providing the first such results in several cases and demonstrating the broad applicability of our approach.
Sources
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time