DROPS

Document

DOI: 10.4230/LIPIcs.IPEC.2017.12

Odd Multiway Cut in Directed Acyclic Graphs

Authors: Karthekeyan Chandrasekaran and Sahand Mozaffari

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

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 shadow-removal 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.

Cite as

Karthekeyan Chandrasekaran and Sahand Mozaffari. Odd Multiway Cut in Directed Acyclic Graphs. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 12:1-12:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chandrasekaran_et_al:LIPIcs.IPEC.2017.12,
  author =	{Chandrasekaran, Karthekeyan and Mozaffari, Sahand},
  title =	{{Odd Multiway Cut in Directed Acyclic Graphs}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{12:1--12:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.12},
  URN =		{urn:nbn:de:0030-drops-85470},
  doi =		{10.4230/LIPIcs.IPEC.2017.12},
  annote =	{Keywords: Odd Multiway Cut, Fixed-Parameter Tractability, Approximation Algorithms}
}

Search Results

Documents authored by Mozaffari, Sahand

Odd Multiway Cut in Directed Acyclic Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message