Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Optimality program in graph homomorphism problems

2018/31/D/ST6/00062

Keywords:

graph homomorphism computational complexity algorithms

Descriptors:

  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory
  • ST6_4: Formal methods, foundations of computer science, including theoretical computer science, quantum algorithms
  • ST1_14: Discrete mathematics and combinatorics

Panel:

ST6 - Computer science and informatics: informatics and information systems, computer science, scientific computing, intelligent systems

Host institution :

Politechnika Warszawska, Wydział Matematyki i Nauk Informacyjnych

woj. mazowieckie

Other projects carried out by the institution 

Principal investigator (from the host institution):

dr Paweł Rzążewski 

Number of co-investigators in the project: 4

Call: SONATA 14 - announced on 2018-09-14

Amount awarded: 306 680 PLN

Project start date (Y-m-d): 2019-06-13

Project end date (Y-m-d): 2023-06-12

Project duration:: 48 months (the same as in the proposal)

Project status: Project settled

Project description

Download the project description in a pdf file

Note - project descriptions were prepared by the authors of the applications themselves and placed in the system in an unchanged form.

Equipment purchased [PL]

  1. Laptop (7 500 PLN)

Information in the final report

  • Publication in academic press/journals (14)
  • Articles in post-conference publications (22)
  1. Clique‐width: Harnessing the power of atoms
    Authors:
    Konrad K. Dabrowski, Tomáš Masařík, Jana Novotná, Daniël Paulusma, Paweł Rzążewski
    Academic press:
    Journal of Graph Theory (rok: 2023, tom: (online), strony: n/a), Wydawca: Wiley
    Status:
    Published
    DOI:
    10.1002/jgt.23000 - link to the publication
  2. Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
    Authors:
    Jacob Focke, Daniel Marx, Paweł Rzążewski
    Academic press:
    ACM Transactions on Algorithms (rok: 2023, tom: online, strony: b/d), Wydawca: ACM
    Status:
    Published
    DOI:
    10.1145/3640814 - link to the publication
  3. Faster 3-coloring of small-diameter graphs
    Authors:
    Michał Dębski, Marta Piecyk, Paweł Rzążewski
    Academic press:
    SIAM Journal on Discrete Mathematics (rok: 2022, tom: 36, strony: 2205-2224), Wydawca: SIAM
    Status:
    Published
    DOI:
    10.1137/21M1447714 - link to the publication
  4. Finding Large H-Colorable Subgraphs in Hereditary Graph Classes
    Authors:
    Maria Chudnovsky, Jason King, Michał Pilipczuk, Paweł Rzaͅżewski, Sophie Spirkl
    Academic press:
    SIAM Journal on Discrete Mathematics (rok: 2021, tom: 35, strony: 2357-2386), Wydawca: SIAM
    Status:
    Published
    DOI:
    10.1137/20M1367660 - link to the publication
  5. Complexity of Ck-coloring in hereditary classes of graphs
    Authors:
    Maria Chudnovsky, Shenwei Huang, Paweł Rzążewski, Sophie Spirkl, Mingxian Zhong
    Academic press:
    Information and Computation (rok: 2023, tom: 292, strony: 105015), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ic.2023.105015 - link to the publication
  6. Feedback Vertex Set and Even Cycle Transversal for H -Free Graphs: Finding Large Block Graphs
    Authors:
    Giacomo Paesani, Daniel Paulusma, Paweł Rzążewski
    Academic press:
    SIAM Journal on Discrete Mathematics (rok: 2022, tom: 36, strony: 2453-2472), Wydawca: SIAM
    Status:
    Published
    DOI:
    10.1137/22M1468864 - link to the publication
  7. On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest
    Authors:
    Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, Paweł Rzążewski
    Academic press:
    Algorithmica (rok: 2020, tom: 82, strony: 2841–2866), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-020-00706-6 - link to the publication
  8. Sparsification Lower Bounds for List H-Coloring
    Authors:
    Hubie Chen, Bart M.P. Jansen, Karolina Okrasa, Astrid Pieterse, Paweł Rzążewski
    Academic press:
    ACM Transactions on Computation Theory (rok: 2023, tom: 15, strony: 45314), Wydawca: ACM
    Status:
    Published
    DOI:
    10.1145/3612938 - link to the publication
  9. Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs
    Authors:
    Karolina Okrasa, Paweł Rzaͅżewski
    Academic press:
    SIAM Journal on Computing (rok: 2021, tom: 50, strony: 487-508), Wydawca: SIAM
    Status:
    Published
    DOI:
    10.1137/20M1320146 - link to the publication
  10. Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument
    Authors:
    Konrad Majewski, Tomáš Masařík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, Marek Sokołowski
    Academic press:
    ACM Transactions on Computation Theory (rok: 2023, tom: online, strony: b/d), Wydawca: ACM
    Status:
    Published
    DOI:
    10.1145/3636422 - link to the publication
  11. Towards the Chen-Raspaud conjecture
    Authors:
    Katarzyna Łyczek, Maria Nazarczuk, Paweł Rzążewski
    Academic press:
    Discrete Mathematics (rok: 2024, tom: 347, strony: n/a), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.disc.2023.113798 - link to the publication
  12. Subexponential algorithms for variants of homomorphism problem in string graphs
    Authors:
    Karolina Okrasa, Paweł Rzążewski
    Academic press:
    Journal of Computer and System Sciences (rok: 2020, tom: 109, strony: 126-144), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.jcss.2019.12.004 - link to the publication
  13. List covering of regular multigraphs with semi-edges
    Authors:
    Jan Bok, Jiří Fiala, Nikola Jedličková, Jan Kratochvíl, Paweł Rzążewski
    Academic press:
    Algorithmica (rok: 2023, tom: online, strony: b/d), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-023-01163-7 - link to the publication
  14. Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs
    Authors:
    Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, Erik Jan van Leeuwen, Bartosz Walczak
    Academic press:
    Algorithmica (rok: 2020, tom: n/a, strony: n/a), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-020-00745-z - link to the publication
  1. Computing list homomorphisms in geometric intersection graphs
    Authors:
    Sandor Kisfaludi-Bak, Karolina Okrasa, Paweł Rzążewski,
    Conference:
    International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2022) (rok: 2022, ), Wydawca: Springer
    Data:
    konferencja 22-24.06.2022
    Status:
    Published
  2. Faster 3-Coloring of Small-Diameter Graphs
    Authors:
    Michał Dębski, Marta Piecyk, Paweł Rzążewski
    Conference:
    European Symposium on Algorithms (ESA 2021) (rok: 2021, ), Wydawca: LIPIcs
    Data:
    konferencja 2021.09.6-8
    Status:
    Published
  3. Full Complexity Classification of the List Homomorphism Problem for Bounded-Treewidth Graphs
    Authors:
    Karolina Okrasa, Marta Piecyk, Paweł Rzążewski
    Conference:
    28th Annual European Symposium on Algorithms (ESA 2020) (rok: 2020, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 7-9.09.2020
    Status:
    Published
  4. Induced subgraphs of bounded treewidth and the container method
    Authors:
    Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Paweł Rzążewski, Paul Seymour
    Conference:
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2021) (rok: 2021, ), Wydawca: SIAM
    Data:
    konferencja 2021.01.10-13
    Status:
    Published
  5. Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument
    Authors:
    Konrad Majewski, Tomáš Masařík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, Marek Sokołowski
    Conference:
    49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) (rok: 2022, ), Wydawca: LIPIcs
    Data:
    konferencja 4-8.07.2022
    Status:
    Published
  6. Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws
    Authors:
    Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Paweł Rzążewski
    Conference:
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2022) (rok: 2022, ), Wydawca: SIAM
    Data:
    konferencja 9-12.01.2022
    Status:
    Published
  7. Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs
    Authors:
    Giacomo Paesani, Daniel Paulusma, Paweł Rzążewski
    Conference:
    International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) (rok: 2021, ), Wydawca: LIPIcs
    Data:
    konferencja 2021.08.23-27
    Status:
    Published
  8. Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs
    Authors:
    Karolina Okrasa, Paweł Rzążewski
    Conference:
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2020) (rok: 2020, ), Wydawca: SIAM
    Data:
    konferencja 5-8.01.2020
    Status:
    Published
  9. Sparsification Lower Bounds for List H-Coloring
    Authors:
    Hubie chen, Bart M.P. Jansen, Karolina Okrasa, Astrid Pieterse, Paweł Rzążewski
    Conference:
    31st International Symposium on Algorithms and Computation (ISAAC 2020) (rok: 2020, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 14-18.12.2020
    Status:
    Published
  10. Clique-Width: Harnessing the Power of Atoms
    Authors:
    Konrad K. Dabrowski, Tomáš Masařík, Jana Novotná, Daniël Paulusma, Paweł Rzążewski
    Conference:
    WG 2020: Graph-Theoretic Concepts in Computer Science (rok: 2020, ), Wydawca: Springer
    Data:
    konferencja 24-26.06.2020
    Status:
    Published
  11. Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
    Authors:
    Jacob Focke, Daniel Marx, Paweł Rzążewski
    Conference:
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2022) (rok: 2022, ), Wydawca: SIAM
    Data:
    konferencja 9-12.01.2022
    Status:
    Published
  12. Finding Large H-Colorable Subgraphs in Hereditary Graph Classes
    Authors:
    Maria Chudnovsky, Jason King, Michał Pilipczuk, Paweł Rzążewski, Sophie Spirkl
    Conference:
    28th Annual European Symposium on Algorithms (ESA 2020) (rok: 2020, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 7-9.09.2020
    Status:
    Published
  13. List Covering of Regular Multigraphs
    Authors:
    Jan Bok, Jiří Fiala, Nikola Jedličková, Jan Kratochvíl, Paweł Rzążewski
    Conference:
    International Workshop on Combinatorial Algorithms (IWOCA 2022) (rok: 2022, ), Wydawca: Springer
    Data:
    konferencja 7-9.06.2022
    Status:
    Published
  14. Quasi-polynomial-time algorithm for Independent Set in Pt-free graphs via shrinking the space of induced paths
    Authors:
    Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski
    Conference:
    Symposium on Simplicity in Algorithms (SOSA 2021) (rok: 2021, ), Wydawca: SIAM
    Data:
    konferencja 2021.01.11-12
    Status:
    Published
  15. Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs
    Authors:
    Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, Erik Jan van Leeuwen, Bartosz Walczak
    Conference:
    14th International Symposium on Parameterized and Exact Computation (IPEC 2019) (rok: 2019, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 9-13.09.2019
    Status:
    Published
  16. Classifying Subset Feedback Vertex Set for H-Free Graphs
    Authors:
    Giacomo Paesani, Daniel Paulusma, Paweł Rzążewski
    Conference:
    International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2022) (rok: 2022, ), Wydawca: Springer
    Data:
    konferencja 22-24.06.2022
    Status:
    Published
  17. 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
    Conference:
    33rd International Symposium on Algorithms and Computation (ISAAC 2022) (rok: 2022, ), Wydawca: LIPIcs
    Data:
    konferencja 19-21.12.2022
    Status:
    Published
  18. Finding large induced sparse subgraphs in C_{>t} -free graphs in quasipolynomial time
    Authors:
    Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski
    Conference:
    Symposium on Theory of Computing (STOC 2021) (rok: 2021, ), Wydawca: ACM
    Data:
    konferencja 2021.06.21-25
    Status:
    Published
  19. Fine-Grained Complexity of the List Homomorphism Problem: Feedback Vertex Set and Cutwidth
    Authors:
    Maria Piecyk, Paweł Rzążewski
    Conference:
    International Symposium on Theoretical Aspects of Computer Science (STACS 2021) (rok: 2021, ), Wydawca: LIPIcs
    Data:
    konferencja 2021.03.16-19
    Status:
    Published
  20. Complexity of the List Homomorphism Problem in Hereditary Graph Classes
    Authors:
    Karolina Okrasa, Paweł Rzążewski
    Conference:
    International Symposium on Theoretical Aspects of Computer Science (STACS 2021) (rok: 2021, ), Wydawca: LIPIcs
    Data:
    konferencja 2021.03.16-19
    Status:
    Published
  21. List Locally Surjective Homomorphisms in Hereditary Graph Classes
    Authors:
    Pavel Dvořák, Monika Krawczyk, Tomáš Masařík, Jana Novotná, Paweł Rzążewski, Aneta Żuk
    Conference:
    33rd International Symposium on Algorithms and Computation (ISAAC 2022) (rok: 2022, ), Wydawca: LIPIcs
    Data:
    konferencja 19-21.12.2022
    Status:
    Published
  22. Parameterized Inapproximability of Independent Set in H-Free Graphs
    Authors:
    Pavel Dvořák, Andreas Emil Feldmann, Ashutosh Rai, Paweł Rzążewski
    Conference:
    WG 2020: Graph-Theoretic Concepts in Computer Science (rok: 2020, ), Wydawca: Springer
    Data:
    konferencja 24-26.06.2020
    Status:
    Published

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy