A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width

DOI10.4230/LIPICS.STACS.2018.42MaRDI QIDQ3304141zbMATH OpenFDO

Authors Lars Jaffke, O-joung Kwon, Jan Arne Telle

Publication date 5 August 2020

Full work available at URL https://arxiv.org/abs/1710.07148

zbMATH Keywords

feedback vertex setgraph classesgraph width parametersleaf powers

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Mim-width. II. The feedback vertex set problem
• Mim-width. I. Induced path problems
• Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width
• Bounding the mim‐width of hereditary graph classes
• Feedback vertex set on AT-free graphs

Cites work

• Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
• Clique-width of path powers
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Computing and Combinatorics
• Faster fixed parameter tractable algorithms for finding feedback vertex sets
• Feedback vertex set on AT-free graphs
• Feedback vertex set on graphs of low clique-width
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Graph classes with structured neighborhoods and algorithmic applications
• Hamilton Paths in Grid Graphs
• Hardness of computing width parameters based on branch decompositions over the vertex set
• scientific article; zbMATH DE number 6118220 (Why is no real title available?)
• scientific article; zbMATH DE number 1979503 (Why is no real title available?)
• scientific article; zbMATH DE number 2044928 (Why is no real title available?)
• Improved algorithms for feedback vertex set problems
• Improved bounds on Bell numbers and on moments of sums of random variables
• Intractability of clique-width parameterizations
• ON DISJOINT CYCLES
• On polygon numbers of circle graphs and distance hereditary graphs
• On the clique-width of some perfect graph classes
• Pairwise compatibility graphs: a survey
• Parameterized and Exact Computation
• Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width
• Reducibility among combinatorial problems
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

Cited in

(15)

• Mim-width. I. Induced path problems
• Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
• Mim-width. II. The feedback vertex set problem
• Subset feedback vertex set on graphs of bounded independent set size
• Mim-width. III. Graph powers and generalized distance domination problems
• scientific article; zbMATH DE number 4041287 (Why is no real title available?)
• Generalized distance domination problems and their complexity on graphs of bounded mim-width
• Subset feedback vertex set on graphs of bounded independent set size
• On the tractability of optimization problems on \(H\)-graphs
• More applications of the d-neighbor equivalence: connectivity and acyclicity constraints
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width
• Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
• Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
• Finding induced subgraphs from graphs with small mim-width

This page was built for publication: A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3304141)