Enumerating minimal subset feedback vertex sets

DOI10.1007/s00453-012-9731-6zbMath1303.05189OpenAlexW2053536525WikidataQ60488401 ScholiaQ60488401MaRDI QIDQ472481

Charis Papadopoulos, Yngve Villanger, Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch

Publication date: 19 November 2014

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9731-6

zbMATH Keywords

NP-hard problemsexact exponential algorithmssubset feedback vertex set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Faster exact algorithms for some terminal set problems ⋮ Enumerating minimal connected dominating sets in graphs of bounded chordality ⋮ Computing weighted subset transversals in \(H\)-free graphs ⋮ Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs ⋮ Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs ⋮ Minimal dominating sets in interval graphs and trees ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Enumeration of minimal connected dominating sets for chordal graphs ⋮ Enumeration and maximum number of minimal connected vertex covers in graphs ⋮ Classifying subset feedback vertex set for \(H\)-free graphs ⋮ Parameterized complexity of multicut in weighted trees ⋮ Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs ⋮ Solving target set selection with bounded thresholds faster than \(2^n\) ⋮ Exact algorithms for restricted subset feedback vertex set in chordal and split graphs ⋮ Unnamed Item ⋮ Enumerating Minimal Tropical Connected Sets ⋮ Solving Target Set Selection with Bounded Thresholds Faster than 2^n ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs ⋮ Computing subset transversals in \(H\)-free graphs ⋮ Subset feedback vertex set in chordal and split graphs ⋮ Subset feedback vertex set on graphs of bounded independent set size ⋮ Node multiway cut and subset feedback vertex set on graphs of bounded mim-width

Cites Work

• Exact exponential algorithms.
• Improved algorithms for feedback vertex set problems
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• The complexity of generalized clique covering
• On enumerating all minimal solutions of feedback problems
• Efficient graph representations
• A 4 k ² kernel for feedback vertex set
• Faster fixed parameter tractable algorithms for finding feedback vertex sets
• Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• Finding Induced Subgraphs via Minimal Triangulations
• A measure & conquer approach for the analysis of exact algorithms
• On Feedback Vertex Set New Measure and New Structures
• An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
• Multiway cuts in node weighted graphs
• Reducibility among Combinatorial Problems
• Enumerating Minimal Subset Feedback Vertex Sets
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Exact Computation of Maximum Induced Forest