Odd Multiway Cut in Directed Acyclic Graphs

DOI10.4230/LIPICS.IPEC.2017.12MaRDI QIDQ5111871zbMATH OpenOpenAlexFDO

Authors Karthekeyan Chandrasekaran, Sahand Mozaffari

Publication date 27 May 2020

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

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)

Abstract: We investigate the odd multiway node (edge) cut problem where the input is a graph with a specified collection of terminal nodes and the goal is to find a smallest subset of nonterminal nodes (edges) to delete so that the terminal nodes do not have an odd length path between them. In an earlier work, Lokshtanov and Ramanujan showed that both odd multiway node cut and odd multiway edge cut are fixed-parameter tractable (FPT) when parameterized by the size of the solution in undirected graphs. In this work, we focus on directed acyclic graphs (DAGs) and design a fixed-parameter algorithm. Our main contribution is a broadening of the shadow-removal framework to address parity problems in DAGs. We complement our FPT results with tight approximability as well as polyhedral results for 2 terminals in DAGs. Additionally, we show inapproximability results for odd multiway edge cut in undirected graphs even for 2 terminals.

Recommendations

• Odd multiway cut in directed acyclic graphs
• Multiway cuts in node weighted graphs
• Maximum directed cuts in acyclic digraphs
• On the hardness of finding near-optimal multicuts in directed acyclic graphs
• scientific article; zbMATH DE number 3987305
• Cuts in undirected graphs. I
• Hardness of cut problems in directed graphs
• Cuts in undirected graphs. II

Cites work

• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Directed Subset Feedback Vertex Set is fixed-parameter tractable
• Faster parameterized algorithms using linear programming
• Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
• Geometric algorithms and combinatorial optimization
• Maximum matching and a polyhedron with 0,1-vertices
• Packing non-zero \(A\)-paths in group-labelled graphs
• Packing odd paths
• Parameterized algorithms
• Parameterized tractability of multiway cut with parity constraints
• Parametrized complexity theory.
• Paths, Trees, and Flowers
• The even-path problem for graphs and digraphs
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Weak duality for packing edge-disjoint odd \((u, v)\)-trails

Cited in

(3)

• scientific article; zbMATH DE number 7559446 (Why is no real title available?)
• On the parameterized complexity of deletion to \(\mathcal{H}\)-free strong components
• Odd multiway cut in directed acyclic graphs

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

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