On Weighted Graph Separation Problems and Flow Augmentation

DOI10.1137/22M153118XzbMATH Open1530.05074arXiv2208.14841MaRDI QIDQ6187079FDOQ6187079

Authors:

Publication date: 10 January 2024

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

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.

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

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

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)

Cites Work

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

Cited In (2)

• Solving hard cut problems via flow-augmentation
• Directed flow-augmentation

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)