Document Open Access Logo

Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth

Authors Dániel Marx, Valia Mitsou

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.28.pdf
  • Filesize: 0.99 MB
  • 15 pages

Document Identifiers

Author Details

Dániel Marx
Valia Mitsou

Cite As Get BibTex

Dániel Marx and Valia Mitsou. Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.28

Abstract

Choosability, introduced by Erdös, Rubin, and Taylor [Congr. Number. 1979], is a well-studied concept in graph theory: we say that a graph is c-choosable if for any assignment of a list of c colors to each vertex, there is a proper coloring where each vertex uses a color from its list. We study the complexity of deciding choosability on graphs of bounded treewidth. It follows from earlier work that 3-choosability can be decided in time 2^(2^(O(w)))*n^(O(1)) on graphs of treewidth w. We complement this result by a matching lower bound giving evidence that double-exponential dependence on treewidth may be necessary for the problem: we show that an algorithm with running time 2^(2^(o(w)))*n^(O(1)) would violate the Exponential-Time Hypothesis (ETH). We consider also the optimization problem where the task is to delete the minimum number of vertices to make the graph 4-choosable, and demonstrate that dependence on treewidth becomes tripleexponential for this problem: it can be solved in time 2^(2^(2^(O(w))))*n^(O(1)) on graphs of treewidth w, but an algorithm with running time 2^(2^(2^(o(w))))*n^(O(1)) would violate ETH.

Subject Classification

Keywords
  • Parameterized Complexity
  • List coloring
  • Treewidth
  • Lower bounds under ETH

Metrics

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

References

  1. Mohammad Hossein Bateni, Mohammad Taghi Hajiaghayi, and Dániel Marx. Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth. J. ACM, 58(5):21, 2011. URL: http://dx.doi.org/10.1145/2027216.2027219.
  2. M. Biró, Mihály Hujter, and Zsolt Tuza. Precoloring extension. I. interval graphs. Discrete Mathematics, 100(1-3):267-279, 1992. URL: http://dx.doi.org/10.1016/0012-365X(92)90646-W.
  3. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets Möbius: fast subset convolution. In David S. Johnson and Uriel Feige, editors, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 67-74. ACM, 2007. URL: http://dx.doi.org/10.1145/1250790.1250801.
  4. Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, and Michal Pilipczuk. Subexponential parameterized algorithm for interval completion. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1116-1131. SIAM, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch78.
  5. Leizhen Cai. Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett., 58(4):171-176, 1996. URL: http://dx.doi.org/10.1016/0020-0190(96)00050-6.
  6. Yixin Cao. Linear recognition of almost interval graphs. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1096-1115. SIAM, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch77.
  7. Yixin Cao and Dániel Marx. Chordal editing is fixed-parameter tractable. In Ernst W. Mayr and Natacha Portier, editors, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5-8, 2014, Lyon, France, volume 25 of LIPIcs, pages 214-225. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2014.214.
  8. Yixin Cao and Dániel Marx. Interval deletion is fixed-parameter tractable. ACM Transactions on Algorithms, 11(3):21:1-21:35, 2015. URL: http://dx.doi.org/10.1145/2629595.
  9. Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, and Yngve Villanger. Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci., 74(7):1188-1198, 2008. URL: http://dx.doi.org/10.1016/j.jcss.2008.05.002.
  10. Janka Chlebíková and Klaus Jansen. The d-precoloring problem for k-degenerate graphs. Discrete Mathematics, 307(16):2042-2052, 2007. URL: http://dx.doi.org/10.1016/j.disc.2005.12.049.
  11. Bruno Courcelle. The monadic second-order logic of graphs. I. recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990. URL: http://dx.doi.org/10.1016/0890-5401(90)90043-H.
  12. 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.
  13. Marek Cygan, Dániel Marx, Marcin Pilipczuk, and Michal Pilipczuk. Hitting forbidden subgraphs in graphs of bounded treewidth. In Erzsébet Csuhaj-Varjú, Martin Dietzfelbinger, and Zoltán Ésik, editors, Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II, volume 8635 of Lecture Notes in Computer Science, pages 189-200. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44465-8_17.
  14. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 150-159. IEEE Computer Society, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.23.
  15. Frank K. H. A. Dehne, Michael R. Fellows, Michael A. Langston, Frances A. Rosamond, and Kim Stevens. An o(2^O(k)n³ FPT algorithm for the undirected feedback vertex set problem. Theory Comput. Syst., 41(3):479-492, 2007. URL: http://dx.doi.org/10.1007/s00224-007-1345-z.
  16. Paul Erdős, Arthur L Rubin, and Herbert Taylor. Choosability in graphs. Congr. Numer, 26:125-157, 1979. Google Scholar
  17. Michael R Fellows, Fedor V Fomin, Daniel Lokshtanov, Frances Rosamond, Saket Saurabh, Stefan Szeider, and Carsten Thomassen. On the complexity of some colorful problems parameterized by treewidth. Information and Computation, 209(2):143-153, 2011. Google Scholar
  18. Fedor V. Fomin and Yngve Villanger. Subexponential parameterized algorithm for minimum fill-in. SIAM J. Comput., 42(6):2197-2216, 2013. URL: http://dx.doi.org/10.1137/11085390X.
  19. Markus Frick and Martin Grohe. The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Logic, 130(1-3):3-31, 2004. URL: http://dx.doi.org/10.1016/j.apal.2004.01.007.
  20. Elisabeth Gassner. The Steiner forest problem revisited. J. Discrete Algorithms, 8(2):154-163, 2010. URL: http://dx.doi.org/10.1016/j.jda.2009.05.002.
  21. Shai Gutner and Michael Tarsi. Some results on (a:b)-choosability. Discrete Mathematics, 309(8):2260-2270, 2009. Google Scholar
  22. Ian Holyer. The NP-completeness of edge-coloring. SIAM Journal on computing, 10(4):718-720, 1981. Google Scholar
  23. M. Hujter and Zs. Tuza. Precoloring extension. II. Graphs classes related to bipartite graphs. Acta Math. Univ. Comenian. (N.S.), 62(1):1-11, 1993. Google Scholar
  24. Mihály Hujter and Zsolt Tuza. Precoloring extension III: Classes of perfect graphs. Combinatorics, Probability & Computing, 5:35-56, 1996. URL: http://dx.doi.org/10.1017/S0963548300001826.
  25. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62:367-375, 2001. Google Scholar
  26. 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
  27. Yoichi Iwata, Keigo Oka, and Yuichi Yoshida. Linear-time FPT algorithms via network flow. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1749-1761. SIAM, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.127.
  28. Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. A near-optimal planarization algorithm. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1802-1811. SIAM, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.130.
  29. Klaus Jansen and Petra Scheffler. Generalized coloring for tree-like graphs. Discrete Applied Mathematics, 75(2):135-155, 1997. URL: http://dx.doi.org/10.1016/S0166-218X(96)00085-6.
  30. Haim Kaplan, Ron Shamir, and Robert Endre Tarjan. Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM J. Comput., 28(5):1906-1922, 1999. URL: http://dx.doi.org/10.1137/S0097539796303044.
  31. J. Kratochvíl. Precoloring extension with fixed color bound. Acta Math. Univ. Comenian. (N.S.), 62(2):139-153, 1993. Google Scholar
  32. Jan Kratochvíl and Zsolt Tuza. Algorithmic complexity of list colorings. Discrete Applied Mathematics, 50(3):297-302, 1994. URL: http://dx.doi.org/10.1016/0166-218X(94)90150-3.
  33. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Known algorithms on graphs on bounded treewidth are probably optimal. In Dana Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 777-789. SIAM, 2011. URL: http://dx.doi.org/10.1137/1.9781611973082.61.
  34. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS, 105:41-72, 2011. URL: http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/view/96.
  35. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Slightly superexponential parameterized problems. In Dana Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 760-776. SIAM, 2011. URL: http://dx.doi.org/10.1137/1.9781611973082.60.
  36. 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.
  37. Dániel Marx. NP-completeness of list coloring and precoloring extension on the edges of planar graphs. Journal of Graph Theory, 49(4):313-324, 2005. URL: http://dx.doi.org/10.1002/jgt.20085.
  38. Dániel Marx. Precoloring extension on unit interval graphs. Discrete Applied Mathematics, 154(6):995-1002, 2006. URL: http://dx.doi.org/10.1016/j.dam.2005.10.008.
  39. Dániel Marx. Chordal deletion is fixed-parameter tractable. Algorithmica, 57(4):747-768, 2010. URL: http://dx.doi.org/10.1007/s00453-008-9233-8.
  40. Dániel Marx and Ildikó Schlotter. Obtaining a planar graph by vertex deletion. Algorithmica, 62(3-4):807-822, 2012. URL: http://dx.doi.org/10.1007/s00453-010-9484-z.
  41. Takao Nishizeki, Jens Vygen, and Xiao Zhou. The edge-disjoint paths problem is NP-complete for series-parallel graphs. Discrete Applied Mathematics, 115(1-3):177-186, 2001. URL: http://dx.doi.org/10.1016/S0166-218X(01)00223-2.
  42. Guoqiang Pan and Moshe Y. Vardi. Fixed-parameter hierarchies inside PSPACE. In LICS, pages 27-36. IEEE Computer Society, 2006. Google Scholar
  43. Michal Pilipczuk. Problems parameterized by treewidth tractable in single exponential time: A logical approach. In Filip Murlak and Piotr Sankowski, editors, Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Warsaw, Poland, August 22-26, 2011. Proceedings, volume 6907 of Lecture Notes in Computer Science, pages 520-531. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-22993-0_47.
  44. M. S. Ramanujan and Saket Saurabh. Linear time parameterized algorithms via skew-symmetric multicuts. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1739-1748. SIAM, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.126.
  45. Bruce A. Reed, Kaleigh Smith, and Adrian Vetta. Finding odd cycle transversals. Oper. Res. Lett., 32(4):299-301, 2004. URL: http://dx.doi.org/10.1016/j.orl.2003.10.009.
  46. Zsolt Tuza. Graph colorings with local constraints - a survey. Discussiones Mathematicae Graph Theory, 17(2):161-228, 1997. URL: http://dx.doi.org/10.7151/dmgt.1049.
  47. Johan M. M. van Rooij, Hans L. Bodlaender, and Peter Rossmanith. Dynamic programming on tree decompositions using generalised fast subset convolution. In Amos Fiat and Peter Sanders, editors, Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings, volume 5757 of Lecture Notes in Computer Science, pages 566-577. Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-642-04128-0_51.
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