SONATA

Key information:

Project title: Optimality program in graph homomorphism problems
Duration: 13.06.2019 - 12.06.2023
Funding: National Science Centre (NCN), SONATA14, 2018/31/D/ST6/00062

Team:

  1. Paweł Rzążewski, principal investigator
  2. Michał Dębski, investigator
  3. Marta Piecyk, investigator

Main objectives:

The high-level research objective of the project is to investigate variants of graph homomorphism problems from the complexity point of view, considering the restrictions imposed on input instances. We are especially interested in obtaining tight upper and lower bounds and dichotomy results, which give a full understanding of "easy" and "hard" cases. The particular meaning of "easy" and "hard" may be different, depending on the context. For example, we might want to distinguish problems that:

  • are solvable in polynomial time from ones that are NP-complete,
  • can be solved in subexponential time, i.e., 2o(n), from ones that do not have such algorithms,
  • are fixed-parameter-tractable (FPT) for some parameter k, i.e., can be solved in time f(k) poly(n), from ones that do not have such algorithms, under standard complexity assumptions.

Selected papers (published only):

  1. K. Okrasa, P. Rzążewski, Subexponential algorithms for variants of homomorphism problem in string graphs, Journal of Computer and System Sciences 109, pp. 126-144, 2020
  2. K. Dabrowski, C. Feghali, M. Johnson, G. Paesani, D. Paulusma, P. Rzążewski, On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest, Algorithmica, 2020
  3. Journal version: J. Novotna, K. Okrasa, Mi. Pilipczuk, P. Rzążewski, E.J. van Leeuwen, B. Walczak, Subexponential-time algorithms for finding large induced sparse subgraphs, Algorithmica, 2020
    Conference version:     J. Novotna, K. Okrasa, Mi. Pilipczuk, P. Rzążewski, E.J. van Leeuwen, B. Walczak, Subexponential-time algorithms for finding large induced sparse subgraphs, IPEC 2019 Proc., 23:1 -- 23:11, 2019  (DOI: 10.4230/LIPIcs.IPEC.2019.23)
  4. Journal version: K. Okrasa, P. Rzążewski, Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs, SIAM Journal on Computing 50(2), pp. 487-508, 2021
    Conference version: K. Okrasa, P. Rzążewski, Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs, SODA 2020 Proc., pp. 1578--1590, 2020
  5. Journal version: P. Dvořák, A.E. Feldmann, A. Rai, P. Rzążewski, Parameterized Inapproximability of Independent Sets in H-Free  Graphs, Algorithmica (available online), 2022
    Conference version: P. Dvořák, A.E. Feldmann, A. Rai, P. Rzążewski, Parameterized Inapproximability of Independent Sets in H-Free Graphs, WG 2020 Proc., LNCS 12301, pp. 40-53, 2020
  6. K.K. Dabrowski, T. Masařík, J. Novotná, D. Paulusma, P. Rzążewski, Clique-Width: Harnessing the Power of Atoms, WG 2020 Proc., LNCS 12301, pp. 119-133, 2020
  7. K. Okrasa, M. Piecyk, P. Rzążewski, Full complexity classification of the list homomorphism problem for bounded-treewidth graphs, ESA 2020 Proc., 74:1 -- 74:24, 2020 (DOI: 10.4230/LIPIcs.ESA.2020.74)
  8. Journal version: M. Chudnovsky, J. King, Mi. Pilipczuk, P. Rzążewski, S. Spirkl, Finding large H-colorable subgraphs in hereditary graph classes, SIAM J. Discrete Math. 35(4), 2357-2386, 2021
    Conference version: M. Chudnovsky, J. King, Mi. Pilipczuk, P. Rzążewski, S. Spirkl, Finding large H-colorable subgraphs in hereditary graph classes, ESA 2020 Proc., 35:1 -- 35:17, 2020 (DOI: 10.4230/LIPIcs.ESA.2020.35)
  9. H. Chen, B.M.P. Jansen, K. Okrasa, A. Pieterse, P. Rzążewski, Sparsification Lower Bounds for List-H-Coloring, ISAAC 2020 Proc., 58:1 -- 58:17, 2020 (DOI: 10.4230/LIPIcs.ISAAC.2020.58)
  10. T. Abrishami, M. Chudnovsky, Ma. Pilipczuk, P. Rzążewski, P. Seymour, Induced subgraphs of bounded treewidth and the container method, SODA 2021 Proc., pp. 1948-1964, 2021
  11. Mi. Pilipczuk, Ma. Pilipczuk, P. Rzążewski, Quasi-polynomial-time algorithm for Independent Set in P_t-free graphs via shrinking the space of induced paths, SOSA 2021 Proc., pp. 204-209, 2021
  12. M. Piecyk, P. Rzążewski, Fine-grained complexity of the list homomorphism problem: feedback vertex set and cutwidth, STACS 2021 Proc., 56:1 -- 56:17, 2021
  13. K. Okrasa, P. Rzążewski, Complexity of the list homomorphism problem in hereditary graph classes, STACS 2021 Proc., 54:1 -- 54.17, 2021
  14. P. Gartland, D. Lokshtanov, Ma. Pilipczuk, Mi. Pilipczuk, P. Rzążewski, Finding large induced sparse subgraphs in C_>t-free graphs in quasipolynomial time, STOC 2021 Proc.,  p. 330-341, 2021
  15. Journal version: M. Dębski, M. Piecyk, P. Rzążewski, Faster 3-coloring of small-diameter graph, SIAM J. Discrete Math. 36, pp. 2205-2224, 2022
    Conference version: M. Dębski, M. Piecyk, P. Rzążewski, Faster 3-coloring of small-diameter graphs, ESA 2021 Proc., pp. 37:1 -- 37:15, 2021
  16. Journal version: G. Paesani, D. Paulusma, P. Rzążewski, Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs, SIAM J. Discrete Math. 36, pp. 2453-2472, 2022
    Conference version:     G. Paesani, D. Paulusma, P. Rzążewski, Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs, MFCS 2021 Proc., 82:1 -- 82:14, 2021
  17. J. Focke, D. Marx, P. Rzążewski, Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds, SODA 2022 Proc.,  pp. 431-458, 2022
  18. T. Abrishami, M. Chudnovsky, C. Dibek, P. Rzążewski, Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws, SODA 2022 Proc.,  pp. 1448-1470, 2022
  19. M. Bonamy, N. Bousquet, M. Pilipczuk, P. Rzążewski, S. Thomasse, B. Walczak, Degeneracy of P_t-free and C_{>= t}-free graphs with no large complete bipartite subgraphs, Journal of Combinatorial Theory, Series B 152, pp. 353-379, 2022
  20. J. Bok, J. Fiala, N. Jedličková, J. Kratochvíl, P. Rzążewski, List covering of regular multigraphs, IWOCA 2022 Proc., LNCS 13270, pp. 228-242
  21. K. Majewski, T. Masařík, J. Novotna, K. Okrasa, M. Pilipczuk, P. Rzążewski, M. Sokołowski, Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument, ICALP 2022 Proc., pp. 93:1--93:19, 2022
  22. G. Paesani, D. Paulusma, P. Rzążewski, Classifying Subset Feedback Vertex Set for H-free graphs, WG 2022 Proc., LNCS 13453, pp. 412-424, 2022
  23. S. Kisfaludi-Bak, K. Okrasa, P. Rzążewski, Computing list homomorphisms in geometric intersection graphs, WG 2022 Proc., LNCS 13453, pp. 313-327, 2022
  24. P. Dvořák, M. Krawczyk, T. Masařík, J. Novotná, P. Rzążewski, and A. Żuk, List Locally Surjective Homomorphisms in Hereditary Graph Classes, ISAAC 2022 Proc., pp. 30:1 - 30:15, 2022
  25. M. Dębski, Z. Lonc, K. Okrasa, M. Piecyk, P. Rzążewski, Computing homomorphisms in hereditary graph classes: the peculiar case of the 5-wheel and graphs with no long claws, ISAAC 2022 Proc., pp. 14:1-14:16, 2022
  26. M. Chudnovsky, S. Huang, P. Rzążewski, S. Spirkl, M. Zhong, Complexity of Ck-coloring in hereditary classes of graphs, Information and Computation 292, 105015, 2023
Powered by CMSimple