Document Open Access Logo

A Linear-Time Parameterized Algorithm for Node Unique Label Cover

Authors Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2017.57.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Subject Classification

Keywords
  • Algorithms and data structures
  • Fixed Parameter Tractability
  • Unique Label Cover
  • Linear Time FPT Algorithms.

Metrics

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

Abstract

The optimization version of the Unique Label Cover problem is at the heart of the Unique Games Conjecture which has played an important role in the proof of several tight inapproximability results. In recent years, this problem has been also studied extensively from the point of view of parameterized complexity. Chitnis et al. [FOCS 2012, SICOMP 2016] proved that this problem is fixed-parameter tractable (FPT) and Wahlström [SODA 2014] gave an FPT algorithm with an improved parameter dependence. Subsequently, Iwata, Wahlström and Yoshida [SICOMP 2016] proved that the edge version of Unique Label Cover can be solved in linear FPT-time, and they left open the existence of such an algorithm for the node version of the problem. In this paper, we resolve this question by presenting the first linear-time FPT algorithm for Node Unique Label Cover.

Cite As Get BibTex

Daniel Lokshtanov, M. S. Ramanujan, and Saket Saurabh. A Linear-Time Parameterized Algorithm for Node Unique Label Cover. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.57

Author Details

Daniel Lokshtanov
M. S. Ramanujan
Saket Saurabh

References

  1. Hans L. Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pages 226-234, 1993. Google Scholar
  2. Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. 25(6):1305-1317, 1996. Google Scholar
  3. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. An O(c^k n) 5-approximation algorithm for treewidth. In FOCS, pages 499-508, 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.60.
  4. Jianer Chen, Yang Liu, and Songjian Lu. An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica, 55(1):1-13, 2009. URL: http://dx.doi.org/10.1007/s00453-007-9130-6.
  5. Rajesh Hemant Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, and Michal Pilipczuk. Designing FPT algorithms for cut problems using randomized contractions. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 460-469, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.29.
  6. Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk. On multiway cut parameterized above lower bounds. TOCT, 5(1):3, 2013. URL: http://dx.doi.org/10.1145/2462896.2462899.
  7. Frederic Dorn. Planar subgraph isomorphism revisited. In STACS, pages 263-274, 2010. Google Scholar
  8. Michael R. Fellows and Michael A. Langston. Nonconstructive tools for proving polynomial-time decidability. J. ACM, 35(3):727-739, 1988. URL: http://dx.doi.org/10.1145/44483.44491.
  9. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, M. S. Ramanujan, and Saket Saurabh. Solving d-sat via backdoors to small treewidth. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 630-641, 2015. Google Scholar
  10. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Planar f-deletion: Approximation, kernelization and optimal FPT algorithms. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 470-479, 2012. Google Scholar
  11. Martin Grohe. Computing crossing numbers in quadratic time. In Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 231-236, 2001. Google Scholar
  12. Martin Grohe. Computing crossing numbers in quadratic time. J. Comput. Syst. Sci., 68(2):285-302, 2004. Google Scholar
  13. Martin Grohe, Ken ichi Kawarabayashi, and Bruce A. Reed. A simple algorithm for the graph minor decomposition - logic meets structural graph theory. In SODA, pages 414-431, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.30.
  14. Sylvain Guillemot. FPT algorithms for path-transversal and cycle-transversal problems. Discrete Optimization, 8(1):61-71, 2011. Google Scholar
  15. Ken ichi Kawarabayashi. Planarity allowing few error vertices in linear time. In FOCS, pages 639-648, 2009. URL: http://dx.doi.org/10.1109/FOCS.2009.45.
  16. Ken ichi Kawarabayashi, Yusuke Kobayashi, and Bruce A. Reed. The disjoint paths problem in quadratic time. J. Comb. Theory, Ser. B, 102(2):424-435, 2012. URL: http://dx.doi.org/10.1016/j.jctb.2011.07.004.
  17. Ken ichi Kawarabayashi and Bojan Mohar. Graph and map isomorphism and all polyhedral embeddings in linear time. In STOC, pages 471-480, 2008. URL: http://dx.doi.org/10.1145/1374376.1374443.
  18. Ken ichi Kawarabayashi, Bojan Mohar, and Bruce A. Reed. A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width. In FOCS, pages 771-780, 2008. URL: http://dx.doi.org/10.1109/FOCS.2008.53.
  19. Ken ichi Kawarabayashi and Bruce A. Reed. Computing crossing number in linear time. In STOC, pages 382-390, 2007. URL: http://dx.doi.org/10.1145/1250790.1250848.
  20. Ken ichi Kawarabayashi and Bruce A. Reed. A nearly linear time algorithm for the half integral parity disjoint paths packing problem. In SODA, pages 1183-1192, 2009. URL: http://dx.doi.org/10.1145/1496770.1496898.
  21. Ken ichi Kawarabayashi and Bruce A. Reed. An (almost) linear time algorithm for odd cycles transversal. In SODA, pages 365-378, 2010. Google Scholar
  22. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  23. Yoichi Iwata, Keigo Oka, and Yuichi Yoshida. Linear-time fpt algorithms via network flow. In SODA, pages 1749-1761, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.127.
  24. Yoichi Iwata, Keigo Oka, and Yuichi Yoshida. Linear-time fpt algorithms via network flow. In SODA, pages 1749-1761, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.127.
  25. Yoichi Iwata, Magnus Wahlström, and Yuichi Yoshida. Half-integrality, lp-branching, and FPT algorithms. SIAM J. Comput., 45(4):1377-1411, 2016. URL: http://dx.doi.org/10.1137/140962838.
  26. Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. A near-optimal planarization algorithm. In SODA, pages 1802-1811, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.130.
  27. Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 767-775, 2002. Google Scholar
  28. Subhash Khot. On the unique games conjecture (invited survey). In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, June 9-12, 2010, pages 99-121, 2010. Google Scholar
  29. Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. Faster parameterized algorithms using linear programming. ACM Transactions on Algorithms, 11(2):15:1-15:31, 2014. URL: http://dx.doi.org/10.1145/2566616.
  30. Daniel Lokshtanov, M. S. Ramanujan, and Saket Saurabh. Linear time parameterized algorithms for subset feedback vertex set. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 935-946, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_76.
  31. Dániel Marx. Parameterized graph separation problems. Theor. Comput. Sci., 351(3):394-406, 2006. URL: http://dx.doi.org/10.1016/j.tcs.2005.10.007.
  32. M. S. Ramanujan. A faster parameterized algorithm for group feedback edge set. In Graph-Theoretic Concepts in Computer Science - 42nd International Workshop, WG 2016, Istanbul, Turkey, June 22-24, 2016, Revised Selected Papers, pages 269-281, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53536-3_23.
  33. M. S. Ramanujan and Saket Saurabh. Linear time parameterized algorithms via skew-symmetric multicuts. In SODA, pages 1739-1748, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.126.
  34. B. Reed. Finding approximate separators and computing tree-width quickly. In Proceedings of the 24th Annual ACM symposium on Theory of Computing (STOC'92), pages 221-228. ACM, 1992. Google Scholar
  35. Neil Robertson and Paul D. Seymour. Graph minors .xiii. the disjoint paths problem. J. Comb. Theory, Ser. B, 63(1):65-110, 1995. Google Scholar
  36. Neil Robertson and Paul D. Seymour. Graph minors. XVIII. tree-decompositions and well-quasi-ordering. J. Comb. Theory, Ser. B, 89(1):77-108, 2003. Google Scholar
  37. Neil Robertson and Paul D. Seymour. Graph minors. XX. wagner’s conjecture. J. Comb. Theory, Ser. B, 92(2):325-357, 2004. Google Scholar
  38. Magnus Wahlström. Half-integrality, LP-branching and FPT algorithms. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1762-1781, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.128.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact