Document Open Access Logo

Odd Multiway Cut in Directed Acyclic Graphs

Authors Karthekeyan Chandrasekaran, Sahand Mozaffari

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2017.12.pdf
  • Filesize: 0.58 MB
  • 12 pages

Document Identifiers

Author Details

Karthekeyan Chandrasekaran
Sahand Mozaffari

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.IPEC.2017.12

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.

Subject Classification

Keywords
  • Odd Multiway Cut
  • Fixed-Parameter Tractability
  • Approximation Algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Karthekeyan Chandrasekaran and Sahand Mozaffari. Odd Multiway Cut in Directed Acyclic Graphs. https://arxiv.org/abs/????.????, 2017.
  2. Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, and Dániel Marx. Directed subset feedback vertex set is fixed-parameter tractable. ACM Trans. Algorithms, 11(4):28:1-28:28, 2015. URL: http://dx.doi.org/10.1145/2700209.
  3. Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, and Dániel Marx. Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. SIAM J. Comput., 42(4):1674-1696, 2013. URL: http://dx.doi.org/10.1137/12086217X.
  4. Maria Chudnovsky, Jim Geelen, Bert Gerards, Luis A. Goddyn, Michael Lohman, and Paul D. Seymour. Packing non-zero a-paths in group-labelled graphs. Combinatorica, 26(5):521-532, 2006. URL: http://dx.doi.org/10.1007/s00493-006-0030-1.
  5. Ross Churchley, Bojan Mohar, and Hehui Wu. Weak duality for packing edge-disjoint odd (u, v)-trails. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '16, pages 2086-2094, 2016. Google Scholar
  6. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  7. Jack Edmonds. Maximum matching and a polyhedron with 0, 1-vertices. Journal of Research of the National Bureau of Standards, 69(1-2):125-130, 1965. Google Scholar
  8. Jack Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17(3):449-467, 1965. Google Scholar
  9. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. URL: http://dx.doi.org/10.1007/3-540-29953-X.
  10. Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer, 1988. URL: http://dx.doi.org/10.1007/978-3-642-78240-4.
  11. Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci., 74(3):335-349, 2008. URL: http://dx.doi.org/10.1016/j.jcss.2007.06.019.
  12. Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, and Magnus Wahlström. Fixed-parameter tractability of multicut in directed acyclic graphs. SIAM J. Discrete Math., 29(1):122-144, 2015. URL: http://dx.doi.org/10.1137/120904202.
  13. Andrea S. LaPaugh and Christos H. Papadimitriou. The even-path problem for graphs and digraphs. Networks, 14(4):507-513, 1984. URL: http://dx.doi.org/10.1002/net.3230140403.
  14. Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. Faster parameterized algorithms using linear programming. ACM Trans. Algorithms, 11(2):15:1-15:31, 2014. URL: http://dx.doi.org/10.1145/2566616.
  15. Daniel Lokshtanov and M. S. Ramanujan. Parameterized tractability of multiway cut with parity constraints. In Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer, editors, Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, volume 7391 of Lecture Notes in Computer Science, pages 750-761. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31594-7_63.
  16. Sridharan Ramanujan. Parameterized Graph Separation Problems: New Techniques and Algorithms. PhD thesis, The Institute of Mathematical Sciences, Chennai, 2013. Google Scholar
  17. Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics. Springer, 2003. Google Scholar
  18. Alexander Schrijver and Paul D. Seymour. Packing odd paths. J. Comb. Theory, Ser. B, 62(2):280-288, 1994. URL: http://dx.doi.org/10.1006/jctb.1994.1070.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact