Node multiway cut and subset feedback vertex set on graphs of bounded mim-width

DOI10.1007/s00453-022-00936-wOpenAlexW2977258053MaRDI QIDQ5970812

Jan Arne Telle, Benjamin Bergougnoux, Charis Papadopoulos

Publication date: 3 May 2022

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

rank-widthmim-widthsubset feedback vertex setnode multiway cutneighbor equivalence

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (5)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph classes with structured neighborhoods and algorithmic applications
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
• Enumerating minimal subset feedback vertex sets
• Feedback vertex set on AT-free graphs
• Graph minors. X: Obstructions to tree-decomposition
• The complexity of generalized clique covering
• A randomized polynomial kernel for subset feedback vertex set
• Output-polynomial enumeration on graphs of bounded (local) linear MIM-width
• Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• 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
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• 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 algorithms for vertex partitioning problems parameterized by clique-width
• Approximating clique-width and branch-width
• Rank-width and vertex-minors
• On Multiway Cut Parameterized above Lower Bounds
• Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• Treewidth: Characterizations, Applications, and Computations
• The Complexity of Multiterminal Cuts
• An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
• Multiway cuts in node weighted graphs
• More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints
• Exact Algorithms via Monotone Local Search
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• Graph-Theoretic Concepts in Computer Science
• Hardness of computing width parameters based on branch decompositions over the vertex set
• Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs

This page was built for publication: Node multiway cut and subset feedback vertex set on graphs of bounded mim-width