Document Open Access Logo

A Sub-Exponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs

Authors Jayakrishnan Madathil, Roohani Sharma, Meirav Zehavi

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.28.pdf
  • Filesize: 0.59 MB
  • 14 pages

Document Identifiers

Author Details

Jayakrishnan Madathil
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
Roohani Sharma
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
Meirav Zehavi
  • Ben-Gurion University, Beer-Sheva, Israel

Funding

  • Zehavi, Meirav: Supported by ISF grant no. 1176/18.

Acknowledgements

We thank Daniel Lokshtanov and Saket Saurabh for insightful discussions on bisection in semicomplete digraphs.

Cite As Get BibTex

Jayakrishnan Madathil, Roohani Sharma, and Meirav Zehavi. A Sub-Exponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 28:1-28:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.MFCS.2019.28

Abstract

Given an n-vertex digraph D and a non-negative integer k, the Minimum Directed Bisection problem asks if the vertices of D can be partitioned into two parts, say L and R, such that |L| and |R| differ by at most 1 and the number of arcs from R to L is at most k. This problem, in general, is W-hard as it is known to be NP-hard even when k=0. We investigate the parameterized complexity of this problem on semicomplete digraphs. We show that Minimum Directed Bisection on semicomplete digraphs is one of a handful of problems that admit sub-exponential time fixed-parameter tractable algorithms. That is, we show that the problem admits a 2^{O(sqrt{k} log k)}n^{O(1)} time algorithm on semicomplete digraphs. We also show that Minimum Directed Bisection admits a polynomial kernel on semicomplete digraphs. To design the kernel, we use (n,k,k^2)-splitters. To the best of our knowledge, this is the first time such pseudorandom objects have been used in the design of kernels. We believe that the framework of designing kernels using splitters could be applied to more problems that admit sub-exponential time algorithms via chromatic coding. To complement the above mentioned results, we prove that Minimum Directed Bisection is NP-hard on semicomplete digraphs, but polynomial time solvable on tournaments.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
Keywords
  • bisection
  • semicomplete digraph
  • tournament
  • fpt algorithm
  • chromatic coding
  • polynomial kernel
  • splitters

Metrics

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

References

  1. Noga Alon, Daniel Lokshtanov, and Saket Saurabh. Fast FAST. In Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I, pages 49-58, 2009. URL: https://doi.org/10.1007/978-3-642-02927-1_6.
  2. Noga Alon, Raphael Yuster, and Uri Zwick. Color-Coding. J. ACM, 42(4):844-856, 1995. URL: https://doi.org/10.1145/210332.210337.
  3. Jørgen Bang-Jensen and Gregory Z. Gutin. Digraphs - theory, algorithms and applications. Springer, 2002. Google Scholar
  4. Florian Barbero, Christophe Paul, and Michal Pilipczuk. Exploring the Complexity of Layout Parameters in Tournaments and Semicomplete Digraphs. ACM Trans. Algorithms, 14(3):38:1-38:31, 2018. URL: https://doi.org/10.1145/3196276.
  5. Florian Barbero, Christophe Paul, and Michal Pilipczuk. Strong immersion is a well-quasi-ordering for semicomplete digraphs. Journal of Graph Theory, 90(4):484-496, 2019. URL: https://doi.org/10.1002/jgt.22408.
  6. Stéphane Bessy, Fedor V Fomin, Serge Gaspers, Christophe Paul, Anthony Perez, Saket Saurabh, and Stéphan Thomassé. Kernels for feedback arc set in tournaments. Journal of Computer and System Sciences, 77(6):1071-1078, 2011. Google Scholar
  7. Thang Nguyen Bui and Andrew Peck. Partitioning Planar Graphs. SIAM J. Comput., 21(2):203-215, 1992. URL: https://doi.org/10.1137/0221016.
  8. Paul Camion. Chemins et circuits hamiltoniens des graphes complets. Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences, 249(21):2151-2152, 1959. Google Scholar
  9. Maria Chudnovsky and Paul D. Seymour. A well-quasi-order for tournaments. J. Comb. Theory, Ser. B, 101(1):47-53, 2011. URL: https://doi.org/10.1016/j.jctb.2010.10.003.
  10. M Cygan, F V Fomin, L Kowalik, D Lokshtanov, D Marx, M Pilipczuk, M Pilipczuk, and S Saurabh. Parameterized algorithms. Springer, 2015. Google Scholar
  11. Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Minimum bisection is fixed parameter tractable. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 323-332, 2014. URL: https://doi.org/10.1145/2591796.2591852.
  12. Josep Díaz and George B. Mertzios. Minimum Bisection Is NP-hard on Unit Disk Graphs. In Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II, pages 251-262, 2014. URL: https://doi.org/10.1007/978-3-662-44465-8_22.
  13. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  14. Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier, and Anke Truß. Fixed-parameter tractability results for feedback set problems in tournaments. J. Discrete Algorithms, 8(1):76-86, 2010. URL: https://doi.org/10.1016/j.jda.2009.08.001.
  15. Uriel Feige. Faster FAST(Feedback Arc Set in Tournaments). CoRR, abs/0911.5094, 2009. URL: http://arxiv.org/abs/0911.5094.
  16. Uriel Feige and Orly Yahalom. On the complexity of finding balanced oneway cuts. Inf. Process. Lett., 87(1):1-5, 2003. URL: https://doi.org/10.1016/S0020-0190(03)00251-5.
  17. Fedor V. Fomin and Michal Pilipczuk. Subexponential Parameterized Algorithm for Computing the Cutwidth of a Semi-complete Digraph. In Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings, pages 505-516, 2013. URL: https://doi.org/10.1007/978-3-642-40450-4_43.
  18. Alexandra Fradkin. Forbidden structures and algorithms in graphs and digraphs. PhD thesis, Princeton University, 2011. Google Scholar
  19. M. R. Garey, David S. Johnson, and Larry J. Stockmeyer. Some Simplified NP-Complete Graph Problems. Theor. Comput. Sci., 1(3):237-267, 1976. URL: https://doi.org/10.1016/0304-3975(76)90059-1.
  20. Klaus Jansen, Marek Karpinski, Andrzej Lingas, and Eike Seidel. Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs. SIAM J. Comput., 35(1):110-119, 2005. URL: https://doi.org/10.1137/S009753970139567X.
  21. Marek Karpinski and Warren Schudy. Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament. In Algorithms and Computation - 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I, pages 3-14, 2010. URL: https://doi.org/10.1007/978-3-642-17517-6_3.
  22. Ilhee Kim. On containment relations in directed graphs. PhD thesis, Princeton University, 2013. Google Scholar
  23. Ilhee Kim and Paul D. Seymour. Tournament minors. J. Comb. Theory, Ser. B, 112:138-153, 2015. URL: https://doi.org/10.1016/j.jctb.2014.12.005.
  24. Michael Lampis, Georgia Kaouri, and Valia Mitsou. On the algorithmic effectiveness of digraph decompositions and complexity measures. Discrete Optimization, 8(1):129-138, 2011. URL: https://doi.org/10.1016/j.disopt.2010.03.010.
  25. Dániel Marx. Parameterized graph separation problems. Theor. Comput. Sci., 351(3):394-406, 2006. URL: https://doi.org/10.1016/j.tcs.2005.10.007.
  26. Moni Naor, Leonard J. Schulman, and Aravind Srinivasan. Splitters and Near-Optimal Derandomization. In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pages 182-191, 1995. URL: https://doi.org/10.1109/SFCS.1995.492475.
  27. Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Contraction Decomposition in Unit Disk Graphs and Algorithmic Applications in Parameterized Complexity. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1035-1054, 2019. URL: https://doi.org/10.1137/1.9781611975482.64.
  28. Harald Räcke. Optimal hierarchical decompositions for congestion minimization in networks. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 255-264, 2008. URL: https://doi.org/10.1145/1374376.1374415.
  29. L Rédei. Ein kombinatorischer Satz. Satz. Acta Litt. Szeged, 7:39-43, 1934. Google Scholar
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