Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep. Conditional Dichotomy of Boolean Ordered Promise CSPs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 37:1-37:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{brakensiek_et_al:LIPIcs.ICALP.2021.37, author = {Brakensiek, Joshua and Guruswami, Venkatesan and Sandeep, Sai}, title = {{Conditional Dichotomy of Boolean Ordered Promise CSPs}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {37:1--37: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.37}, URN = {urn:nbn:de:0030-drops-141060}, doi = {10.4230/LIPIcs.ICALP.2021.37}, annote = {Keywords: promise constraint satisfaction, Boolean ordered PCSP, Shapley value, rich 2-to-1 conjecture, random minor} }
Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Marcin Wrochna. PACE Solver Description: Sallow: A Heuristic Algorithm for Treedepth Decompositions. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 36:1-36:4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{wrochna:LIPIcs.IPEC.2020.36, author = {Wrochna, Marcin}, title = {{PACE Solver Description: Sallow: A Heuristic Algorithm for Treedepth Decompositions}}, booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)}, pages = {36:1--36:4}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-172-6}, ISSN = {1868-8969}, year = {2020}, volume = {180}, editor = {Cao, Yixin and Pilipczuk, Marcin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.36}, URN = {urn:nbn:de:0030-drops-133391}, doi = {10.4230/LIPIcs.IPEC.2020.36}, annote = {Keywords: treedepth, decomposition, heuristic, weak colouring numbers} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Alex Brandts, Marcin Wrochna, and Stanislav Živný. The Complexity of Promise SAT on Non-Boolean Domains. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 17:1-17:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{brandts_et_al:LIPIcs.ICALP.2020.17, author = {Brandts, Alex and Wrochna, Marcin and \v{Z}ivn\'{y}, Stanislav}, title = {{The Complexity of Promise SAT on Non-Boolean Domains}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {17:1--17:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.17}, URN = {urn:nbn:de:0030-drops-124241}, doi = {10.4230/LIPIcs.ICALP.2020.17}, annote = {Keywords: promise constraint satisfaction, PCSP, polymorphisms, algebraic approach, label cover} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Marthe Bonamy, Nicolas Bousquet, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Arnaud Mary, Moritz Mühlenthaler, and Kunihiro Wasa. The Perfect Matching Reconfiguration Problem. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 80:1-80:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bonamy_et_al:LIPIcs.MFCS.2019.80, author = {Bonamy, Marthe and Bousquet, Nicolas and Heinrich, Marc and Ito, Takehiro and Kobayashi, Yusuke and Mary, Arnaud and M\"{u}hlenthaler, Moritz and Wasa, Kunihiro}, title = {{The Perfect Matching Reconfiguration Problem}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {80:1--80:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.80}, URN = {urn:nbn:de:0030-drops-110248}, doi = {10.4230/LIPIcs.MFCS.2019.80}, annote = {Keywords: Combinatorial Reconfiguration, Graph Algorithms, Perfect Matching} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Archontia C. Giannopoulou, O-joung Kwon, Jean-Florent Raymond, and Dimitrios M. Thilikos. Lean Tree-Cut Decompositions: Obstructions and Algorithms. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 32:1-32:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{giannopoulou_et_al:LIPIcs.STACS.2019.32, author = {Giannopoulou, Archontia C. and Kwon, O-joung and Raymond, Jean-Florent and Thilikos, Dimitrios M.}, title = {{Lean Tree-Cut Decompositions: Obstructions and Algorithms}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {32:1--32:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.32}, URN = {urn:nbn:de:0030-drops-102716}, doi = {10.4230/LIPIcs.STACS.2019.32}, annote = {Keywords: tree-cut width, lean decompositions, immersions, obstructions, parameterized algorithms} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Dušan Knop, Michał Pilipczuk, and Marcin Wrochna. Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 44:1-44:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{knop_et_al:LIPIcs.STACS.2019.44, author = {Knop, Du\v{s}an and Pilipczuk, Micha{\l} and Wrochna, Marcin}, title = {{Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {44:1--44:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.44}, URN = {urn:nbn:de:0030-drops-102831}, doi = {10.4230/LIPIcs.STACS.2019.44}, annote = {Keywords: integer linear programming, fixed-parameter tractability, ETH} }
Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Bart M. P. Jansen, Marcin Pilipczuk, and Marcin Wrochna. Turing Kernelization for Finding Long Paths in Graphs Excluding a Topological Minor. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 23:1-23:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{jansen_et_al:LIPIcs.IPEC.2017.23, author = {Jansen, Bart M. P. and Pilipczuk, Marcin and Wrochna, Marcin}, title = {{Turing Kernelization for Finding Long Paths in Graphs Excluding a Topological Minor}}, booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)}, pages = {23:1--23:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-051-4}, ISSN = {1868-8969}, year = {2018}, volume = {89}, editor = {Lokshtanov, Daniel and Nishimura, Naomi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.23}, URN = {urn:nbn:de:0030-drops-85576}, doi = {10.4230/LIPIcs.IPEC.2017.23}, annote = {Keywords: Turing kernel, long path, k-path, excluded topological minor, modulator} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Marthe Bonamy, Lukasz Kowalik, Michal Pilipczuk, Arkadiusz Socala, and Marcin Wrochna. Tight Lower Bounds for the Complexity of Multicoloring. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 18:1-18:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{bonamy_et_al:LIPIcs.ESA.2017.18, author = {Bonamy, Marthe and Kowalik, Lukasz and Pilipczuk, Michal and Socala, Arkadiusz and Wrochna, Marcin}, title = {{Tight Lower Bounds for the Complexity of Multicoloring}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {18:1--18:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.18}, URN = {urn:nbn:de:0030-drops-78527}, doi = {10.4230/LIPIcs.ESA.2017.18}, annote = {Keywords: multicoloring, Kneser graph homomorphism, ETH lower bound} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Archontia C. Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, and Marcin Wrochna. Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 57:1-57:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{giannopoulou_et_al:LIPIcs.ICALP.2017.57, author = {Giannopoulou, Archontia C. and Pilipczuk, Michal and Raymond, Jean-Florent and Thilikos, Dimitrios M. and Wrochna, Marcin}, title = {{Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {57:1--57:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.57}, URN = {urn:nbn:de:0030-drops-73891}, doi = {10.4230/LIPIcs.ICALP.2017.57}, annote = {Keywords: Kernelization, Approximation, Immersion, Protrusion, Tree-cut width} }
Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Archontia C. Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, and Marcin Wrochna. Cutwidth: Obstructions and Algorithmic Aspects. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 15:1-15:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{giannopoulou_et_al:LIPIcs.IPEC.2016.15, author = {Giannopoulou, Archontia C. and Pilipczuk, Michal and Raymond, Jean-Florent and Thilikos, Dimitrios M. and Wrochna, Marcin}, title = {{Cutwidth: Obstructions and Algorithmic Aspects}}, booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, pages = {15:1--15:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-023-1}, ISSN = {1868-8969}, year = {2017}, volume = {63}, editor = {Guo, Jiong and Hermelin, Danny}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.15}, URN = {urn:nbn:de:0030-drops-69306}, doi = {10.4230/LIPIcs.IPEC.2016.15}, annote = {Keywords: cutwidth, obstructions, immersions, fixed-parameter tractability} }
Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Marcin Pilipczuk, Michal Pilipczuk, and Marcin Wrochna. Edge Bipartization Faster Than 2^k. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 26:1-26:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{pilipczuk_et_al:LIPIcs.IPEC.2016.26, author = {Pilipczuk, Marcin and Pilipczuk, Michal and Wrochna, Marcin}, title = {{Edge Bipartization Faster Than 2^k}}, booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, pages = {26:1--26:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-023-1}, ISSN = {1868-8969}, year = {2017}, volume = {63}, editor = {Guo, Jiong and Hermelin, Danny}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.26}, URN = {urn:nbn:de:0030-drops-69285}, doi = {10.4230/LIPIcs.IPEC.2016.26}, annote = {Keywords: edge bipartization, FPT algorithm} }
Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Michal Pilipczuk and Marcin Wrochna. On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 57:1-57:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{pilipczuk_et_al:LIPIcs.STACS.2016.57, author = {Pilipczuk, Michal and Wrochna, Marcin}, title = {{On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs}}, booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)}, pages = {57:1--57:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-001-9}, ISSN = {1868-8969}, year = {2016}, volume = {47}, editor = {Ollinger, Nicolas and Vollmer, Heribert}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.57}, URN = {urn:nbn:de:0030-drops-57588}, doi = {10.4230/LIPIcs.STACS.2016.57}, annote = {Keywords: tree decomposition, LCS, tree-depth, NAuxSA, Savitch’s theorem} }
Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
R. B. Sandeep and Naveen Sivadasan. Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 365-376, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{sandeep_et_al:LIPIcs.IPEC.2015.365, author = {Sandeep, R. B. and Sivadasan, Naveen}, title = {{Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion}}, booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)}, pages = {365--376}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-92-7}, ISSN = {1868-8969}, year = {2015}, volume = {43}, editor = {Husfeldt, Thore and Kanj, Iyad}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.365}, URN = {urn:nbn:de:0030-drops-55976}, doi = {10.4230/LIPIcs.IPEC.2015.365}, annote = {Keywords: edge deletion problems, polynomial kernelization} }
Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Tom C. van der Zanden. Parameterized Complexity of Graph Constraint Logic. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 282-293, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{vanderzanden:LIPIcs.IPEC.2015.282, author = {van der Zanden, Tom C.}, title = {{Parameterized Complexity of Graph Constraint Logic}}, booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)}, pages = {282--293}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-92-7}, ISSN = {1868-8969}, year = {2015}, volume = {43}, editor = {Husfeldt, Thore and Kanj, Iyad}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.282}, URN = {urn:nbn:de:0030-drops-55906}, doi = {10.4230/LIPIcs.IPEC.2015.282}, annote = {Keywords: Nondeterministic Constraint Logic, Reconfiguration Problems, Parameterized Complexity, Treewidth, Bandwidth} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Marcin Wrochna. Homomorphism Reconfiguration via Homotopy. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 730-742, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)
@InProceedings{wrochna:LIPIcs.STACS.2015.730, author = {Wrochna, Marcin}, title = {{Homomorphism Reconfiguration via Homotopy}}, booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)}, pages = {730--742}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-78-1}, ISSN = {1868-8969}, year = {2015}, volume = {30}, editor = {Mayr, Ernst W. and Ollinger, Nicolas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.730}, URN = {urn:nbn:de:0030-drops-49546}, doi = {10.4230/LIPIcs.STACS.2015.730}, annote = {Keywords: reconfiguration, recoloring, homomorphisms, homotopy, hom complex} }
Feedback for Dagstuhl Publishing