On Weighted Graph Separation Problems and Flow Augmentation

DOI10.1137/22M153118XMaRDI QIDQ6187079zbMATH OpenFDO

Authors

Publication date 10 January 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

parameterized complexitydirected flow augmentationweighted directed subset feedback vertex setweighted group feedback vertex setweighted multicut

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Flows in graphs (05C21) Signed and weighted graphs (05C22)

Abstract: One of the first application of the recently introduced technique of emph{flow-augmentation} [Kim et al., STOC 2022] is a fixed-parameter algorithm for the weighted version of extsc{Directed Feedback Vertex Set}, a landmark problem in parameterized complexity. In this note we explore applicability of flow-augmentation to other weighted graph separation problems parameterized by the size of the cutset. We show the following. -- In weighted undirected graphs extsc{Multicut} is FPT, both in the edge- and vertex-deletion version. -- The weighted version of extsc{Group Feedback Vertex Set} is FPT, even with an oracle access to group operations. -- The weighted version of extsc{Directed Subset Feedback Vertex Set} is FPT. Our study reveals extsc{Directed Symmetric Multicut} as the next important graph separation problem whose parameterized complexity remains unknown, even in the unweighted setting.

Recommendations

• Directed flow-augmentation
• Directed Subset Feedback Vertex Set is fixed-parameter tractable
• Directed subset feedback vertex set is fixed-parameter tractable
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Solving hard cut problems via flow-augmentation

Cites work

• scientific article; zbMATH DE number 5485529 (Why is no real title available?)
• Almost 2-SAT is fixed-parameter tractable
• Compression via Matroids
• Constant ratio fixed-parameter approximation of the edge multicut problem
• Designing FPT algorithms for cut problems using randomized contractions
• Directed flow-augmentation
• Directed subset feedback vertex set is fixed-parameter tractable
• FPT algorithms for path-transversal and cycle-transversal problems
• Finding odd cycle transversals.
• Finding small separators in linear time via treewidth reduction
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
• Fixed-parameter tractability of multicut parameterized by the size of the cutset
• Half-integrality, LP-branching, and FPT algorithms
• Multicut Is FPT
• Parameterized complexity of weighted multicut in trees
• Parameterized graph separation problems
• Randomized Contractions Meet Lean Decompositions
• Representative sets and irrelevant vertices: new tools for kernelization
• The complexity of temporal constraint satisfaction problems
• The minimum k-way cut of bounded size is fixed-parameter tractable
• When recursion is better than iteration: a linear-time algorithm for acyclicity with few error vertices

Cited in

(6)

• Solving hard cut problems via flow-augmentation
• Flow-augmentation. I: Directed graphs
• Parameterized complexity of MinCSP over the point algebra
• Almost consistent systems of linear equations
• Directed flow-augmentation
• Flow-augmentation. III: Complexity dichotomy for Boolean CSPS parameterized by the number of unsatisfied constraints

This page was built for publication: On Weighted Graph Separation Problems and Flow Augmentation

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