Aktualności / News > SONATA
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:
- Paweł Rzążewski, principal investigator
- Michał Dębski, investigator
- 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):
- 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
- 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
-
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) -
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 - 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 - 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
- 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)
- 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) - 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)
- 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
- 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
- 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
- K. Okrasa, P. Rzążewski, Complexity of the list homomorphism problem in hereditary graph classes, STACS 2021 Proc., 54:1 -- 54.17, 2021
- 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
- Journal version: