Odd Multiway Cut in Directed Acyclic Graphs

DOI10.1137/18M1176087zbMath1443.68123OpenAlexW3036391239MaRDI QIDQ3300762

Sahand Mozaffari, Karthekeyan Chandrasekaran, Matthias Mnich

Publication date: 30 July 2020

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

Full work available at URL: https://doi.org/10.1137/18m1176087

zbMATH Keywords

approximation algorithmsfixed-parameter tractabilityodd multiway cut

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (1)

A survey of parameterized algorithms and the complexity of edge modification

Cites Work

• Unnamed Item
• Unnamed Item
• Parameterized complexity dichotomy for \textsc{Steiner Multicut}
• Finding odd cycle transversals.
• Linear kernels and linear-time algorithms for finding large cuts
• Parameterized graph separation problems
• Packing non-zero \(A\)-paths in group-labelled graphs
• Geometric algorithms and combinatorial optimization.
• Packing odd paths
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Fixed-parameter tractability for subset feedback set problems with parity constraints
• An improved integrality gap for the Călinescu-Karloff-Rabani relaxation for multiway cut
• MIN-MAX theorems for packing and covering odd \((u,v)\)-trails
• Quick but odd growth of cacti
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Parameterized Tractability of Multiway Cut with Parity Constraints
• Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset
• Finding small separators in linear time via treewidth reduction
• The even-path problem for graphs and digraphs
• The Complexity of Multiterminal Cuts
• Compression via Matroids
• Faster Parameterized Algorithms Using Linear Programming
• Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs
• Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
• Paths, Trees, and Flowers
• Hitting Selected (Odd) Cycles
• Linear Time Parameterized Algorithms via Skew-Symmetric Multicuts
• Linear-Time FPT Algorithms via Network Flow
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Parameterized Algorithms
• Maximum matching and a polyhedron with 0,1-vertices

This page was built for publication: Odd Multiway Cut in Directed Acyclic Graphs