Document Open Access Logo

Computing Homomorphisms in Hereditary Graph Classes: The Peculiar Case of the 5-Wheel and Graphs with No Long Claws

Authors Michał Dębski, Zbigniew Lonc, Karolina Okrasa , Marta Piecyk , Paweł Rzążewski

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.14.pdf
  • Filesize: 0.92 MB
  • 16 pages

Document Identifiers

Author Details

Michał Dębski
  • Faculty of Mathematics and Information Science, Warsaw University of Technology, Poland
Zbigniew Lonc
  • Faculty of Mathematics and Information Science, Warsaw University of Technology, Poland
Karolina Okrasa
  • Faculty of Mathematics and Information Science, Warsaw University of Technology, Poland
  • Institute of Informatics, University of Warsaw, Poland
Marta Piecyk
  • Faculty of Mathematics and Information Science, Warsaw University of Technology, Poland
Paweł Rzążewski
  • Faculty of Mathematics and Information Science, Warsaw University of Technology, Poland
  • Institute of Informatics, University of Warsaw, Poland

Funding

MD, MP, and PRz were supported by Polish National Science Centre grant no. 2018/31/D/ST6/00062. KO was supported by Polish National Science Centre grant no. 2021/41/N/ST6/01507.

Cite As Get BibTex

Michał Dębski, Zbigniew Lonc, Karolina Okrasa, Marta Piecyk, and Paweł Rzążewski. Computing Homomorphisms in Hereditary Graph Classes: The Peculiar Case of the 5-Wheel and Graphs with No Long Claws. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ISAAC.2022.14

Abstract

For graphs G and H, an H-coloring of G is an edge-preserving mapping from V(G) to V(H). In the H-Coloring problem the graph H is fixed and we ask whether an instance graph G admits an H-coloring. A generalization of this problem is H-ColoringExt, where some vertices of G are already mapped to vertices of H and we ask if this partial mapping can be extended to an H-coloring.
We study the complexity of variants of H-Coloring in F-free graphs, i.e., graphs excluding a fixed graph F as an induced subgraph. For integers a,b,c ⩾ 1, by S_{a,b,c} we denote the graph obtained by identifying one endvertex of three paths on a+1, b+1, and c+1 vertices, respectively. For odd k ⩾ 5, by W_k we denote the graph obtained from the k-cycle by adding a universal vertex.
As our main algorithmic result we show that W_5-ColoringExt is polynomial-time solvable in S_{2,1,1}-free graphs. This result exhibits an interesting non-monotonicity of H-ColoringExt with respect to taking induced subgraphs of H. Indeed, W_5 contains a triangle, and K_3-Coloring, i.e., classical 3-coloring, is NP-hard already in claw-free (i.e., S_{1,1,1}-free) graphs. Our algorithm is based on two main observations:  
1) W_5-ColoringExt in S_{2,1,1}-free graphs can be in polynomial time reduced to a variant of the problem of finding an independent set intersecting all triangles, and 
2) the latter problem can be solved in polynomial time in S_{2,1,1}-free graphs. 
We complement this algorithmic result with several negative ones. In particular, we show that W_5-Coloring is NP-hard in P_t-free graphs for some constant t and W_5-ColoringExt is NP-hard in S_{3,3,3}-free graphs of bounded degree. This is again uncommon, as usually problems that are NP-hard in S_{a,b,c}-free graphs for some constant a,b,c are already hard in claw-free graphs

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph coloring
  • Theory of computation → Graph algorithms analysis
Keywords
  • graph homomorphism
  • forbidden induced subgraphs
  • precoloring extension

Metrics

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

Related Versions

References

  1. Tara Abrishami, Maria Chudnovsky, Cemil Dibek, and Paweł Rzążewski. Polynomial-time algorithm for maximum independent set in bounded-degree graphs with no long induced claws. In Niv Buchbinder Joseph (Seffi) Naor, editor, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference, January 9-12, 2022, pages 1448-1470. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977073.61.
  2. V.E. Alekseev. The effect of local constraints on the complexity of determination of the graph independence number. Combinatorial-algebraic methods in applied mathematics, pages 3-13, 1982. (in Russian). Google Scholar
  3. Vladimir E. Alekseev. Polynomial algorithm for finding the largest independent sets in graphs without forks. Discrete Applied Mathematics, 135(1-3):3-16, 2004. URL: https://doi.org/10.1016/S0166-218X(02)00290-1.
  4. Laurent Beaudou, Florent Foucaud, and Reza Naserasr. Smallest C_2l+1-critical graphs of odd-girth 2k+1. In Manoj Changat and Sandip Das, editors, Algorithms and Discrete Applied Mathematics - 6th International Conference, CALDAM 2020, Hyderabad, India, February 13-15, 2020, Proceedings, volume 12016 of Lecture Notes in Computer Science, pages 184-196. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-39219-2_16.
  5. Flavia Bonomo, Maria Chudnovsky, Peter Maceli, Oliver Schaudt, Maya Stein, and Mingxian Zhong. Three-coloring and list three-coloring of graphs without induced paths on seven vertices. Comb., 38(4):779-801, 2018. URL: https://doi.org/10.1007/s00493-017-3553-8.
  6. Andrei A. Bulatov. H-Coloring dichotomy revisited. Theor. Comput. Sci., 349(1):31-39, 2005. URL: https://doi.org/10.1016/j.tcs.2005.09.028.
  7. Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 319-330. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.37.
  8. Paul A. Catlin. Graph homomorphisms into the five-cycle. J. Comb. Theory, Ser. B, 45(2):199-211, 1988. URL: https://doi.org/10.1016/0095-8956(88)90069-X.
  9. Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt, and Mingxian Zhong. Obstructions for three-coloring graphs without induced paths on six vertices. J. Comb. Theory, Ser. B, 140:45-83, 2020. URL: https://doi.org/10.1016/j.jctb.2019.04.006.
  10. Maria Chudnovsky, Shenwei Huang, Pawel Rzążewski, Sophie Spirkl, and Mingxian Zhong. Complexity of C_k-coloring in hereditary classes of graphs. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 31:1-31:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.31.
  11. Maria Chudnovsky, Jason King, MichałPilipczuk, PawełRzążewski, and Sophie Spirkl. Finding large H-colorable subgraphs in hereditary graph classes. SIAM J. Discret. Math., 35(4):2357-2386, 2021. URL: https://doi.org/10.1137/20M1367660.
  12. Maria Chudnovsky, Marcin Pilipczuk, Michal Pilipczuk, and Stéphan Thomassé. Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs. CoRR, abs/1907.04585, 2019. URL: http://arxiv.org/abs/1907.04585.
  13. Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk, and Stéphan Thomassé. Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set problem in H-free graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2260-2278. SIAM, 2020. Google Scholar
  14. Maria Chudnovsky and Paul D. Seymour. Claw-free graphs. v. global structure. J. Comb. Theory, Ser. B, 98(6):1373-1410, 2008. URL: https://doi.org/10.1016/j.jctb.2008.03.002.
  15. Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation, 85(1):12-75, 1990. URL: https://doi.org/10.1016/0890-5401(90)90043-H.
  16. Michał Dębski, Zbigniew Lonc, Karolina Okrasa, Marta Piecyk, and Paweł Rzążewski. Computing homomorphisms in hereditary graph classes: the peculiar case of the 5-wheel and graphs with no long claws. CoRR, abs/2205.13270, 2022. URL: https://doi.org/10.48550/arXiv.2205.13270.
  17. Jack Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449-467, 1965. URL: https://doi.org/10.4153/CJM-1965-045-4.
  18. Thomas Emden-Weinert, Stefan Hougardy, and Bernd Kreuter. Uniquely colourable graphs and the hardness of colouring graphs of large girth. Comb. Probab. Comput., 7(4):375-386, 1998. URL: http://journals.cambridge.org/action/displayAbstract?aid=46667.
  19. Yuri Faenza, Gianpaolo Oriolo, and Gautier Stauffer. Solving the weighted stable set problem in claw-free graphs via decomposition. J. ACM, 61(4):20:1-20:41, 2014. URL: https://doi.org/10.1145/2629600.
  20. Alastair Farrugia. Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard. Electron. J. Comb., 11(1), 2004. URL: http://www.combinatorics.org/Volume_11/Abstracts/v11i1r46.html, URL: https://doi.org/10.37236/1799.
  21. Tomás Feder and Pavol Hell. Edge list homomorphisms. Unpublished manuscript, available at URL: http://theory.stanford.edu/~tomas/edgelist.ps.
  22. Tomás Feder and Pavol Hell. List homomorphisms to reflexive graphs. Journal of Combinatorial Theory, Series B, 72(2):236-250, 1998. URL: https://doi.org/10.1006/jctb.1997.1812.
  23. Tomás Feder, Pavol Hell, and Jing Huang. List homomorphisms and circular arc graphs. Combinatorica, 19(4):487-505, 1999. URL: https://doi.org/10.1007/s004939970003.
  24. Tomás Feder, Pavol Hell, and Jing Huang. Bi-arc graphs and the complexity of list homomorphisms. Journal of Graph Theory, 42(1):61-80, 2003. URL: https://doi.org/10.1002/jgt.10073.
  25. Peter Gartland and Daniel Lokshtanov. Independent set on P_k-free graphs in quasi-polynomial time. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 613-624. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00063.
  26. Petr A. Golovach, Matthew Johnson, Daniël Paulusma, and Jian Song. A survey on the computational complexity of coloring graphs with forbidden subgraphs. Journal of Graph Theory, 84(4):331-363, 2017. URL: https://doi.org/10.1002/jgt.22028.
  27. Petr A. Golovach, Daniël Paulusma, and Jian Song. Closing complexity gaps for coloring problems on H-free graphs. Inf. Comput., 237:204-214, 2014. URL: https://doi.org/10.1016/j.ic.2014.02.004.
  28. Andrzej Grzesik, Tereza Klimošová, Marcin Pilipczuk, and Michał Pilipczuk. Polynomial-time algorithm for Maximum Weight Independent Set on P₆-free graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pages 1257-1271. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.77.
  29. Pavol Hell and Jaroslav Nešetřil. Graphs and homomorphisms. Oxford University Press, 2004. Google Scholar
  30. Pavol Hell and Jaroslav Nešetřil. On the complexity of H-coloring. J. Comb. Theory, Ser. B, 48(1):92-110, 1990. URL: https://doi.org/10.1016/0095-8956(90)90132-J.
  31. Chính T. Hoàng, Marcin Kamiński, Vadim V. Lozin, Joe Sawada, and Xiao Shu. Deciding k-colorability of P₅-free graphs in polynomial time. Algorithmica, 57(1):74-81, 2010. URL: https://doi.org/10.1007/s00453-008-9197-8.
  32. Chính T. Hoàng, Brian Moore, Daniel Recoskie, Joe Sawada, and Martin Vatshelle. Constructions of k-critical P₅-free graphs. Discret. Appl. Math., 182:91-98, 2015. URL: https://doi.org/10.1016/j.dam.2014.06.007.
  33. Ian Holyer. The NP-completeness of edge-coloring. SIAM J. Comput., 10:718-720, 1981. Google Scholar
  34. Shenwei Huang. Improved complexity results on k-coloring P_t-free graphs. Eur. J. Comb., 51:336-346, 2016. URL: https://doi.org/10.1016/j.ejc.2015.06.005.
  35. Marcin Kamiński and Anna Pstrucha. Certifying coloring algorithms for graphs without long induced paths. Discret. Appl. Math., 261:258-267, 2019. URL: https://doi.org/10.1016/j.dam.2018.09.031.
  36. Daniel Leven and Zvi Galil. NP-completeness of finding the chromatic index of regular graphs. J. Algorithms, 4(1):35-44, 1983. URL: https://doi.org/10.1016/0196-6774(83)90032-9.
  37. Daniel Lokshtanov, Martin Vatshelle, and Yngve Villanger. Independent Set in P₅-free graphs in polynomial time. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pages 570-581. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.43.
  38. Vadim V. Lozin and Martin Milanič. A polynomial algorithm to find an independent set of maximum weight in a fork-free graph. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006, pages 26-30. ACM Press, 2006. URL: http://dl.acm.org/citation.cfm?id=1109557.1109561.
  39. Vadim V. Lozin and Martin Milanič. A polynomial algorithm to find an independent set of maximum weight in a fork-free graph. J. Discrete Algorithms, 6(4):595-604, 2008. URL: https://doi.org/10.1016/j.jda.2008.04.001.
  40. Konrad Majewski, Tomás Masařík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, and Marek Sokołowski. Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument. CoRR, abs/2203.04836, 2022. accepted to ICALP 2022. URL: https://doi.org/10.48550/arXiv.2203.04836.
  41. George J. Minty. On maximal independent sets of vertices in claw-free graphs. J. Comb. Theory, Ser. B, 28(3):284-304, 1980. URL: https://doi.org/10.1016/0095-8956(80)90074-X.
  42. Paolo Nobili and Antonio Sassano. An O(n² log n) algorithm for the weighted stable set problem in claw-free graphs. Math. Program., 186(1):409-437, 2021. URL: https://doi.org/10.1007/s10107-019-01461-5.
  43. Karolina Okrasa and PawełRzążewski. Complexity of the list homomorphism problem in hereditary graph classes. In Markus Bläser and Benjamin Monmege, editors, 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16-19, 2021, Saarbrücken, Germany (Virtual Conference), volume 187 of LIPIcs, pages 54:1-54:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.STACS.2021.54.
  44. Marta Piecyk and Paweł Rzążewski. Fine-grained complexity of the list homomorphism problem: Feedback vertex set and cutwidth. In Markus Bläser and Benjamin Monmege, editors, 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16-19, 2021, Saarbrücken, Germany (Virtual Conference), volume 187 of LIPIcs, pages 56:1-56:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.STACS.2021.56.
  45. Marcin Pilipczuk, Michał Pilipczuk, and Paweł Rzążewski. Quasi-polynomial-time algorithm for Independent Set in P_t-free graphs via shrinking the space of induced paths. In Hung Viet Le and Valerie King, editors, 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021, pages 204-209. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976496.23.
  46. Najiba Sbihi. Algorithme de recherche d'un stable de cardinalite maximum dans un graphe sans etoile. Discrete Mathematics, 29(1):53-76, 1980. (in French). Google Scholar
  47. Sophie Spirkl, Maria Chudnovsky, and Mingxian Zhong. Four-coloring P₆-free graphs. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1239-1256. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.76.
  48. Robert Endre Tarjan. Decomposition by clique separators. Discret. Math., 55(2):221-232, 1985. URL: https://doi.org/10.1016/0012-365X(85)90051-2.
  49. Dmitriy Zhuk. A proof of the CSP dichotomy conjecture. J. ACM, 67(5):30:1-30:78, 2020. URL: https://doi.org/10.1145/3402029.
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