Zmiana języka

Projects search

Optimality program in graph homomorphism problems

2018/31/D/ST6/00062

Keywords

Descriptors

  • ST6_6: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier
  • ST6_4: Metody formalne, teoretyczne podstawy informatyki w tym informatyka teoretyczna
  • ST1_14: Kombinatoryka

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

Voivodeship: 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
2019-06-13
Project end date
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. Cost: 7 500 PLN

Information in the final report

Publication in academic press/journals (14)

  1. 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 (year: 2023, volume: 15, pages: 46045), Publisher: ACM
    Status:
    Published
    DOI:
    10.1145/3612938 – link to the publication

  2. Faster 3-coloring of small-diameter graphs

    Authors:
    Michał Dębski, Marta Piecyk, Paweł Rzążewski
    Academic press:
    SIAM Journal on Discrete Mathematics (year: 2022, volume: 36, pages: 2205-2224), Publisher: SIAM
    Status:
    Published
    DOI:
    10.1137/21M1447714 – link to the publication

  3. 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 (year: 2022, volume: 36, pages: 2453-2472), Publisher: SIAM
    Status:
    Published
    DOI:
    10.1137/22M1468864 – 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 (year: 2021, volume: 35, pages: 2357-2386), Publisher: SIAM
    Status:
    Published
    DOI:
    10.1137/20M1367660 – link to the publication

  5. 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 (year: 2023, volume: (online), pages: n/a), Publisher: Wiley
    Status:
    Published
    DOI:
    10.1002/jgt.23000 – link to the publication

  6. 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 (year: 2023, volume: 292, pages: 105015), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ic.2023.105015 – 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 (year: 2020, volume: 82, pages: 2841–2866), Publisher: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-020-00706-6 – link to the publication

  8. Subexponential algorithms for variants of homomorphism problem in string graphs

    Authors:
    Karolina Okrasa, Paweł Rzążewski
    Academic press:
    Journal of Computer and System Sciences (year: 2020, volume: 109, pages: 126-144), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.jcss.2019.12.004 – 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 (year: 2021, volume: 50, pages: 487-508), Publisher: SIAM
    Status:
    Published
    DOI:
    10.1137/20M1320146 – link to the publication

  10. 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 (year: 2020, volume: n/a, pages: n/a), Publisher: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-020-00745-z – link to the publication

  11. 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 (year: 2023, volume: online, pages: b/d), Publisher: ACM
    Status:
    Published
    DOI:
    10.1145/3636422 – link to the publication

  12. 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 (year: 2023, volume: online, pages: b/d), Publisher: ACM
    Status:
    Published
    DOI:
    10.1145/3640814 – link to the publication

  13. Towards the Chen-Raspaud conjecture

    Authors:
    Katarzyna Łyczek, Maria Nazarczuk, Paweł Rzążewski
    Academic press:
    Discrete Mathematics (year: 2024, volume: 347, pages: n/a), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.disc.2023.113798 – link to the publication

  14. 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 (year: 2023, volume: online, pages: b/d), Publisher: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-023-01163-7 – link to the publication

Articles in post-conference publications (22)

  1. 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) (year: 2022, pages: 431-458), Publisher: SIAM
    Date:
    conference 9-12.01.2022
    Status:
    Published

  2. 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) (year: 2022, pages: 228-242), Publisher: Springer
    Date:
    conference 7-9.06.2022
    Status:
    Published

  3. 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) (year: 2022, pages: 1448-1470), Publisher: SIAM
    Date:
    conference 9-12.01.2022
    Status:
    Published

  4. Faster 3-Coloring of Small-Diameter Graphs

    Authors:
    Michał Dębski, Marta Piecyk, Paweł Rzążewski
    Conference:
    European Symposium on Algorithms (ESA 2021) (year: 2021, pages: 37:1-37:15), Publisher: LIPIcs
    Date:
    conference 2021.09.6-8
    Status:
    Published

  5. 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) (year: 2021, pages: 82:1-82:14), Publisher: LIPIcs
    Date:
    conference 2021.08.23-27
    Status:
    Published

  6. 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) (year: 2021, pages: 54:1-54:17), Publisher: LIPIcs
    Date:
    conference 2021.03.16-19
    Status:
    Published

  7. 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) (year: 2021, pages: 330-341), Publisher: ACM
    Date:
    conference 2021.06.21-25
    Status:
    Published

  8. 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) (year: 2021, pages: 1948-1964), Publisher: SIAM
    Date:
    conference 2021.01.10-13
    Status:
    Published

  9. 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 (year: 2020, pages: 40-53), Publisher: Springer
    Date:
    conference 24-26.06.2020
    Status:
    Published

  10. 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) (year: 2020, pages: 1578-1590), Publisher: SIAM
    Date:
    conference 5-8.01.2020
    Status:
    Published

  11. 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) (year: 2020, pages: 58:1-58:17), Publisher: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Date:
    conference 14-18.12.2020
    Status:
    Published

  12. 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) (year: 2019, pages: 23:1-23:11), Publisher: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Date:
    conference 9-13.09.2019
    Status:
    Published

  13. 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) (year: 2022, pages: 313-327), Publisher: Springer
    Date:
    conference 22-24.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) (year: 2021, pages: 204-209), Publisher: SIAM
    Date:
    conference 2021.01.11-12
    Status:
    Published

  15. 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) (year: 2022, pages: 412-424), Publisher: Springer
    Date:
    conference 22-24.06.2022
    Status:
    Published

  16. 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) (year: 2022, pages: 93:1-03:19), Publisher: LIPIcs
    Date:
    conference 4-8.07.2022
    Status:
    Published

  17. 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) (year: 2021, pages: 56:1-56:17), Publisher: LIPIcs
    Date:
    conference 2021.03.16-19
    Status:
    Published

  18. 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) (year: 2020, pages: 74:1-74:24), Publisher: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Date:
    conference 7-9.09.2020
    Status:
    Published

  19. 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) (year: 2020, pages: 35:1-35:17), Publisher: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Date:
    conference 7-9.09.2020
    Status:
    Published

  20. 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 (year: 2020, pages: 119-133), Publisher: Springer
    Date:
    conference 24-26.06.2020
    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) (year: 2022, pages: 30:1-30:15), Publisher: LIPIcs
    Date:
    conference 19-21.12.2022
    Status:
    Published

  22. 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) (year: 2022, pages: 14:1-14:16), Publisher: LIPIcs
    Date:
    conference 19-21.12.2022
    Status:
    Published

« New search

Graphic design and implementation: Jakub Piotrowski