Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Venkatesan Guruswami, Xuandi Ren, and Sai Sandeep. Baby PIH: Parameterized Inapproximability of Min CSP. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{guruswami_et_al:LIPIcs.CCC.2024.27, author = {Guruswami, Venkatesan and Ren, Xuandi and Sandeep, Sai}, title = {{Baby PIH: Parameterized Inapproximability of Min CSP}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {27:1--27:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.27}, URN = {urn:nbn:de:0030-drops-204237}, doi = {10.4230/LIPIcs.CCC.2024.27}, annote = {Keywords: Parameterized Inapproximability Hypothesis, Constraint Satisfaction Problems} }
Published in: LIPIcs, Volume 299, 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)
Mateus de Oliveira Oliveira and Farhad Vadiee. State Canonization and Early Pruning in Width-Based Automated Theorem Proving. In 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 299, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{deoliveiraoliveira_et_al:LIPIcs.FSCD.2024.33, author = {de Oliveira Oliveira, Mateus and Vadiee, Farhad}, title = {{State Canonization and Early Pruning in Width-Based Automated Theorem Proving}}, booktitle = {9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)}, pages = {33:1--33:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-323-2}, ISSN = {1868-8969}, year = {2024}, volume = {299}, editor = {Rehof, Jakob}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2024.33}, URN = {urn:nbn:de:0030-drops-203622}, doi = {10.4230/LIPIcs.FSCD.2024.33}, annote = {Keywords: Width-Based Automated Theorem Proving, Dynamic Programming, Parameterized Complexity} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Shyan Akmal, Virginia Vassilevska Williams, and Nicole Wein. Detecting Disjoint Shortest Paths in Linear Time and More. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{akmal_et_al:LIPIcs.ICALP.2024.9, author = {Akmal, Shyan and Vassilevska Williams, Virginia and Wein, Nicole}, title = {{Detecting Disjoint Shortest Paths in Linear Time and More}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {9:1--9:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.9}, URN = {urn:nbn:de:0030-drops-201529}, doi = {10.4230/LIPIcs.ICALP.2024.9}, annote = {Keywords: disjoint shortest paths, algebraic graph algorithms, disjoint paths, fine-grained complexity, clique} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos, and Sebastian Wiederrecht. Delineating Half-Integrality of the Erdős-Pósa Property for Minors: The Case of Surfaces. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 114:1-114:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{paul_et_al:LIPIcs.ICALP.2024.114, author = {Paul, Christophe and Protopapas, Evangelos and Thilikos, Dimitrios M. and Wiederrecht, Sebastian}, title = {{Delineating Half-Integrality of the Erd\H{o}s-P\'{o}sa Property for Minors: The Case of Surfaces}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {114:1--114:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.114}, URN = {urn:nbn:de:0030-drops-202576}, doi = {10.4230/LIPIcs.ICALP.2024.114}, annote = {Keywords: Erd\H{o}s-P\'{o}sa property, Erd\H{o}s-P\'{o}sa pair, Graph parameters, Graph minors, Universal obstruction, Surface containment} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Jakub Gajarský and Rose McCarty. On Classes of Bounded Tree Rank, Their Interpretations, and Efficient Sparsification. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 137:1-137:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{gajarsky_et_al:LIPIcs.ICALP.2024.137, author = {Gajarsk\'{y}, Jakub and McCarty, Rose}, title = {{On Classes of Bounded Tree Rank, Their Interpretations, and Efficient Sparsification}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {137:1--137:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.137}, URN = {urn:nbn:de:0030-drops-202802}, doi = {10.4230/LIPIcs.ICALP.2024.137}, annote = {Keywords: First-order model checking, structural graph theory, structural sparsity} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Louis Esperet and Sergey Norin. Testability and Local Certification of Monotone Properties in Minor-Closed Classes. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 58:1-58:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{esperet_et_al:LIPIcs.ICALP.2022.58, author = {Esperet, Louis and Norin, Sergey}, title = {{Testability and Local Certification of Monotone Properties in Minor-Closed Classes}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {58:1--58:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.58}, URN = {urn:nbn:de:0030-drops-163997}, doi = {10.4230/LIPIcs.ICALP.2022.58}, annote = {Keywords: Property testing, sparse model, local certification, minor-closed classes} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Ken-ichi Kawarabayashi, Bojan Mohar, Roman Nedela, and Peter Zeman. Automorphisms and Isomorphisms of Maps in Linear Time. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 86:1-86:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{kawarabayashi_et_al:LIPIcs.ICALP.2021.86, author = {Kawarabayashi, Ken-ichi and Mohar, Bojan and Nedela, Roman and Zeman, Peter}, title = {{Automorphisms and Isomorphisms of Maps in Linear Time}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {86:1--86:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.86}, URN = {urn:nbn:de:0030-drops-141558}, doi = {10.4230/LIPIcs.ICALP.2021.86}, annote = {Keywords: maps on surfaces, automorphisms, isomorphisms, algorithm} }
Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)
Ken-ichi Kawarabayashi, Seri Khoury, Aaron Schild, and Gregory Schwartzman. Improved Distributed Approximations for Maximum Independent Set. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kawarabayashi_et_al:LIPIcs.DISC.2020.35, author = {Kawarabayashi, Ken-ichi and Khoury, Seri and Schild, Aaron and Schwartzman, Gregory}, title = {{Improved Distributed Approximations for Maximum Independent Set}}, booktitle = {34th International Symposium on Distributed Computing (DISC 2020)}, pages = {35:1--35:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-168-9}, ISSN = {1868-8969}, year = {2020}, volume = {179}, editor = {Attiya, Hagit}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.35}, URN = {urn:nbn:de:0030-drops-131135}, doi = {10.4230/LIPIcs.DISC.2020.35}, annote = {Keywords: Distributed graph algorithms, Approximation algorithms, Lower bounds} }
Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)
Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi, and Gregory Schwartzman. Optimal Distributed Covering Algorithms. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{benbasat_et_al:LIPIcs.DISC.2019.5, author = {Ben-Basat, Ran and Even, Guy and Kawarabayashi, Ken-ichi and Schwartzman, Gregory}, title = {{Optimal Distributed Covering Algorithms}}, booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)}, pages = {5:1--5:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-126-9}, ISSN = {1868-8969}, year = {2019}, volume = {146}, editor = {Suomela, Jukka}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.5}, URN = {urn:nbn:de:0030-drops-113129}, doi = {10.4230/LIPIcs.DISC.2019.5}, annote = {Keywords: Distributed Algorithms, Approximation Algorithms, Vertex Cover, Set Cover} }
Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)
Ran Ben-Basat, Ken-ichi Kawarabayashi, and Gregory Schwartzman. Parameterized Distributed Algorithms. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{benbasat_et_al:LIPIcs.DISC.2019.6, author = {Ben-Basat, Ran and Kawarabayashi, Ken-ichi and Schwartzman, Gregory}, title = {{Parameterized Distributed Algorithms}}, booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)}, pages = {6:1--6:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-126-9}, ISSN = {1868-8969}, year = {2019}, volume = {146}, editor = {Suomela, Jukka}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.6}, URN = {urn:nbn:de:0030-drops-113135}, doi = {10.4230/LIPIcs.DISC.2019.6}, annote = {Keywords: Distributed Algorithms, Approximation Algorithms, Parameterized Algorithms} }
Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)
Ken-ichi Kawarabayashi and Gregory Schwartzman. Adapting Local Sequential Algorithms to the Distributed Setting. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 35:1-35:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{kawarabayashi_et_al:LIPIcs.DISC.2018.35, author = {Kawarabayashi, Ken-ichi and Schwartzman, Gregory}, title = {{Adapting Local Sequential Algorithms to the Distributed Setting}}, booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)}, pages = {35:1--35:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-092-7}, ISSN = {1868-8969}, year = {2018}, volume = {121}, editor = {Schmid, Ulrich and Widder, Josef}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.35}, URN = {urn:nbn:de:0030-drops-98245}, doi = {10.4230/LIPIcs.DISC.2018.35}, annote = {Keywords: Distributed, Approximation Algorithms, Derandomization, Max-Cut} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Zdenek Dvorák and Ken-ichi Kawarabayashi. Additive Non-Approximability of Chromatic Number in Proper Minor-Closed Classes. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 47:1-47:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{dvorak_et_al:LIPIcs.ICALP.2018.47, author = {Dvor\'{a}k, Zdenek and Kawarabayashi, Ken-ichi}, title = {{Additive Non-Approximability of Chromatic Number in Proper Minor-Closed Classes}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {47:1--47:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.47}, URN = {urn:nbn:de:0030-drops-90510}, doi = {10.4230/LIPIcs.ICALP.2018.47}, annote = {Keywords: non-approximability, chromatic number, minor-closed classes} }
Published in: LIPIcs, Volume 62, 25th EACSL Annual Conference on Computer Science Logic (CSL 2016)
Kord Eickmeyer and Ken-ichi Kawarabayashi. Successor-Invariant First-Order Logic on Graphs with Excluded Topological Subgraphs. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 62, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{eickmeyer_et_al:LIPIcs.CSL.2016.18, author = {Eickmeyer, Kord and Kawarabayashi, Ken-ichi}, title = {{Successor-Invariant First-Order Logic on Graphs with Excluded Topological Subgraphs}}, booktitle = {25th EACSL Annual Conference on Computer Science Logic (CSL 2016)}, pages = {18:1--18:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-022-4}, ISSN = {1868-8969}, year = {2016}, volume = {62}, editor = {Talbot, Jean-Marc and Regnier, Laurent}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2016.18}, URN = {urn:nbn:de:0030-drops-65583}, doi = {10.4230/LIPIcs.CSL.2016.18}, annote = {Keywords: model-checking, algorithmic meta-theorem, successor-invariant, first-order logic, topological subgraphs, parameterised complexity} }
Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Ken-ichi Kawarabayashi and Mikkel Thorup. Coloring 3-colorable graphs with o(n^{1/5}) colors. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 458-469, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{kawarabayashi_et_al:LIPIcs.STACS.2014.458, author = {Kawarabayashi, Ken-ichi and Thorup, Mikkel}, title = {{Coloring 3-colorable graphs with o(n^\{1/5\}) colors}}, booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)}, pages = {458--469}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-65-1}, ISSN = {1868-8969}, year = {2014}, volume = {25}, editor = {Mayr, Ernst W. and Portier, Natacha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.458}, URN = {urn:nbn:de:0030-drops-44797}, doi = {10.4230/LIPIcs.STACS.2014.458}, annote = {Keywords: Approximation Algorithms, Graph Coloring} }
Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Ken-ichi Kawarabayashi and Yusuke Kobayashi. Edge-disjoint Odd Cycles in 4-edge-connected Graphs. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 206-217, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@InProceedings{kawarabayashi_et_al:LIPIcs.STACS.2012.206, author = {Kawarabayashi, Ken-ichi and Kobayashi, Yusuke}, title = {{Edge-disjoint Odd Cycles in 4-edge-connected Graphs}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {206--217}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.206}, URN = {urn:nbn:de:0030-drops-34173}, doi = {10.4230/LIPIcs.STACS.2012.206}, annote = {Keywords: odd-cycles, disjoint paths problem, Erd\"{o}s-Posa property, packing algorithm, 4-edge-connectivity} }