Odd Multiway Cut in Directed Acyclic Graphs

DOI10.4230/LIPICS.IPEC.2017.12zbMATH Open1443.68124arXiv1708.02323OpenAlexW2962809577MaRDI QIDQ5111871FDOQ5111871

Karthekeyan Chandrasekaran, Sahand Mozaffari

Publication date: 27 May 2020

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.

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)

Cites Work

• Geometric algorithms and combinatorial optimization
• Paths, Trees, and Flowers
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Parametrized complexity theory.
• Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
• Parameterized Algorithms
• Maximum matching and a polyhedron with 0,1-vertices
• Packing non-zero \(A\)-paths in group-labelled graphs
• Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
• Faster Parameterized Algorithms Using Linear Programming
• Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• Parameterized Tractability of Multiway Cut with Parity Constraints
• The even-path problem for graphs and digraphs
• Packing odd paths
• Weak duality for packing edge-disjoint odd (u, v)-trails

Cited In (2)

• Title not available (Why is that?)
• On the parameterized complexity of deletion to \(\mathcal{H}\)-free strong components

Recommendations

• Multiway cuts in node weighted graphs 👍 👎
• Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs 👍 👎
• Maximum directed cuts in acyclic digraphs 👍 👎
• Hardness of cut problems in directed graphs 👍 👎
• Cuts in undirected graphs. I 👍 👎
• Cuts in undirected graphs. II 👍 👎
• On the hardness of finding near-optimal multicuts in directed acyclic graphs 👍 👎
• Odd Multiway Cut in Directed Acyclic Graphs 👍 👎
• Title not available (Why is that?) 👍 👎

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)