Subset feedback vertex set on graphs of bounded independent set size
DOI10.1016/j.tcs.2020.01.029zbMath1435.68244OpenAlexW3003449463MaRDI QIDQ2304562
Spyridon Tzimas, Charis Papadopoulos
Publication date: 12 March 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10221/
NP-completenesspolynomial-time algorithmW[1-hardness]subset feedback vertex setnode multiway cutgraphs of bounded independent set size
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (8)
Cites Work
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
- Enumerating minimal subset feedback vertex sets
- Parameterized graph separation problems
- Strong computational lower bounds via parameterized complexity
- Feedback vertex set on AT-free graphs
- On the parameterized complexity of multiple-interval graph problems
- The complexity of generalized clique covering
- Efficient graph representations
- A randomized polynomial kernel for subset feedback vertex set
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
- Feedback vertex set on graphs of low clique-width
- Faster exact algorithms for some terminal set problems
- An improved parameterized algorithm for the minimum node multiway cut problem
- Subset feedback vertex sets in chordal graphs
- Faster Exact Algorithms for Some Terminal Set Problems
- On Multiway Cut Parameterized above Lower Bounds
- Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- Node-Deletion Problems on Bipartite Graphs
- An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
- Multiway cuts in node weighted graphs
- Exact Algorithms via Monotone Local Search
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Max flows in O(nm) time, or better
- Parameterized Algorithms
- Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs
- Subset feedback vertex set in chordal and split graphs
This page was built for publication: Subset feedback vertex set on graphs of bounded independent set size