Odd multiway cut in directed acyclic graphs

Karthekeyan Chandrasekaran, Sahand Mozaffari

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 non-terminal 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 an extension of the shadowremoval framework for 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.

Original languageEnglish (US)
Title of host publication12th International Symposium on Parameterized and Exact Computation, IPEC 2017
EditorsDaniel Lokshtanov, Naomi Nishimura
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770514
DOIs
StatePublished - Feb 1 2018
Event12th International Symposium on Parameterized and Exact Computation, IPEC 2017 - Vienna, Austria
Duration: Sep 6 2017Sep 8 2017

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume89
ISSN (Print)1868-8969

Other

Other12th International Symposium on Parameterized and Exact Computation, IPEC 2017
CountryAustria
CityVienna
Period9/6/179/8/17

Keywords

  • Approximation algorithms
  • Fixed-parameter tractability
  • Odd multiway cut

ASJC Scopus subject areas

  • Software

Cite this

Chandrasekaran, K., & Mozaffari, S. (2018). Odd multiway cut in directed acyclic graphs. In D. Lokshtanov, & N. Nishimura (Eds.), 12th International Symposium on Parameterized and Exact Computation, IPEC 2017 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 89). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.IPEC.2017.12