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/

zbMATH Keywords

NP-completenesspolynomial-time algorithmW[1-hardness]subset feedback vertex setnode multiway cutgraphs of bounded independent set size

Mathematics Subject Classification ID

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)

Computing weighted subset transversals in \(H\)-free graphs ⋮ Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Classifying subset feedback vertex set for \(H\)-free graphs ⋮ A parameterized algorithm for subset feedback vertex set in tournaments ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Computing subset transversals in \(H\)-free graphs ⋮ Node multiway cut and subset feedback vertex set on graphs of bounded mim-width

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