Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Bart M. P. Jansen, Jari J. H. de Kroon, and Michał Włodarczyk. Single-Exponential FPT Algorithms for Enumerating Secluded ℱ-Free Subgraphs and Deleting to Scattered Graph Classes. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 42:1-42:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{jansen_et_al:LIPIcs.ISAAC.2023.42, author = {Jansen, Bart M. P. and de Kroon, Jari J. H. and W{\l}odarczyk, Micha{\l}}, title = {{Single-Exponential FPT Algorithms for Enumerating Secluded ℱ-Free Subgraphs and Deleting to Scattered Graph Classes}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {42:1--42:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.42}, URN = {urn:nbn:de:0030-drops-193440}, doi = {10.4230/LIPIcs.ISAAC.2023.42}, annote = {Keywords: fixed-parameter tractability, important separators, secluded subgraphs} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Ashwin Jacob, Michał Włodarczyk, and Meirav Zehavi. Finding Long Directed Cycles Is Hard Even When DFVS Is Small or Girth Is Large. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 65:1-65:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{jacob_et_al:LIPIcs.ESA.2023.65, author = {Jacob, Ashwin and W{\l}odarczyk, Micha{\l} and Zehavi, Meirav}, title = {{Finding Long Directed Cycles Is Hard Even When DFVS Is Small or Girth Is Large}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {65:1--65:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.65}, URN = {urn:nbn:de:0030-drops-187184}, doi = {10.4230/LIPIcs.ESA.2023.65}, annote = {Keywords: Hamiltonian cycle, longest path, directed feedback vertex set, directed graphs, parameterized complexity} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Bart M. P. Jansen, Jari J. H. de Kroon, and Michał Włodarczyk. 5-Approximation for ℋ-Treewidth Essentially as Fast as ℋ-Deletion Parameterized by Solution Size. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 66:1-66:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{jansen_et_al:LIPIcs.ESA.2023.66, author = {Jansen, Bart M. P. and de Kroon, Jari J. H. and W{\l}odarczyk, Micha{\l}}, title = {{5-Approximation for ℋ-Treewidth Essentially as Fast as ℋ-Deletion Parameterized by Solution Size}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {66:1--66:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.66}, URN = {urn:nbn:de:0030-drops-187195}, doi = {10.4230/LIPIcs.ESA.2023.66}, annote = {Keywords: fixed-parameter tractability, treewidth, graph decompositions} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Michał Włodarczyk. Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 106:1-106:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{wlodarczyk:LIPIcs.ICALP.2023.106, author = {W{\l}odarczyk, Micha{\l}}, title = {{Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {106:1--106:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.106}, URN = {urn:nbn:de:0030-drops-181585}, doi = {10.4230/LIPIcs.ICALP.2023.106}, annote = {Keywords: fixed-parameter tractability, treewidth, chordal graphs, interval graphs, matroids, representative families} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Raghuvansh R. Saxena, Santhoshini Velusamy, and S. Matthew Weinberg. An Improved Lower Bound for Matroid Intersection Prophet Inequalities. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 95:1-95:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{saxena_et_al:LIPIcs.ITCS.2023.95, author = {Saxena, Raghuvansh R. and Velusamy, Santhoshini and Weinberg, S. Matthew}, title = {{An Improved Lower Bound for Matroid Intersection Prophet Inequalities}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {95:1--95:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.95}, URN = {urn:nbn:de:0030-drops-175986}, doi = {10.4230/LIPIcs.ITCS.2023.95}, annote = {Keywords: Prophet Inequalities, Intersection of Matroids} }
Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Huib Donkers, Bart M. P. Jansen, and Michał Włodarczyk. Preprocessing for Outerplanar Vertex Deletion: An Elementary Kernel of Quartic Size. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 14:1-14:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{donkers_et_al:LIPIcs.IPEC.2021.14, author = {Donkers, Huib and Jansen, Bart M. P. and W{\l}odarczyk, Micha{\l}}, title = {{Preprocessing for Outerplanar Vertex Deletion: An Elementary Kernel of Quartic Size}}, booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)}, pages = {14:1--14:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-216-7}, ISSN = {1868-8969}, year = {2021}, volume = {214}, editor = {Golovach, Petr A. and Zehavi, Meirav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.14}, URN = {urn:nbn:de:0030-drops-153979}, doi = {10.4230/LIPIcs.IPEC.2021.14}, annote = {Keywords: fixed-parameter tractability, kernelization, outerplanar graphs} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Bart M. P. Jansen, Shivesh K. Roy, and Michał Włodarczyk. On the Hardness of Compressing Weights. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 64:1-64:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{jansen_et_al:LIPIcs.MFCS.2021.64, author = {Jansen, Bart M. P. and Roy, Shivesh K. and W{\l}odarczyk, Micha{\l}}, title = {{On the Hardness of Compressing Weights}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {64:1--64:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.64}, URN = {urn:nbn:de:0030-drops-145049}, doi = {10.4230/LIPIcs.MFCS.2021.64}, annote = {Keywords: kernelization, compression, edge-weighted clique, constraint satisfaction problems} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Bart M. P. Jansen and Michał Włodarczyk. Optimal Polynomial-Time Compression for Boolean Max CSP. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 63:1-63:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{jansen_et_al:LIPIcs.ESA.2020.63, author = {Jansen, Bart M. P. and W{\l}odarczyk, Micha{\l}}, title = {{Optimal Polynomial-Time Compression for Boolean Max CSP}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {63:1--63:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.63}, URN = {urn:nbn:de:0030-drops-129297}, doi = {10.4230/LIPIcs.ESA.2020.63}, annote = {Keywords: constraint satisfaction problem, kernelization, exponential time algorithms} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Michał Włodarczyk. Parameterized Inapproximability for Steiner Orientation by Gap Amplification. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 104:1-104:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{wlodarczyk:LIPIcs.ICALP.2020.104, author = {W{\l}odarczyk, Micha{\l}}, title = {{Parameterized Inapproximability for Steiner Orientation by Gap Amplification}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {104:1--104:19}, 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.104}, URN = {urn:nbn:de:0030-drops-125110}, doi = {10.4230/LIPIcs.ICALP.2020.104}, annote = {Keywords: approximation algorithms, fixed-parameter tractability, hardness of approximation, gap amplification} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Marek Adamczyk, Jarosław Byrka, Jan Marcinkowski, Syed M. Meesum, and Michał Włodarczyk. Constant-Factor FPT Approximation for Capacitated k-Median. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 1:1-1:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{adamczyk_et_al:LIPIcs.ESA.2019.1, author = {Adamczyk, Marek and Byrka, Jaros{\l}aw and Marcinkowski, Jan and Meesum, Syed M. and W{\l}odarczyk, Micha{\l}}, title = {{Constant-Factor FPT Approximation for Capacitated k-Median}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {1:1--1:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.1}, URN = {urn:nbn:de:0030-drops-111225}, doi = {10.4230/LIPIcs.ESA.2019.1}, annote = {Keywords: K-median, Clustering, Approximation Algorithms, Fixed Parameter Tractability} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Ce Jin. An Improved FPTAS for 0-1 Knapsack. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 76:1-76:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{jin:LIPIcs.ICALP.2019.76, author = {Jin, Ce}, title = {{An Improved FPTAS for 0-1 Knapsack}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {76:1--76:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.76}, URN = {urn:nbn:de:0030-drops-106527}, doi = {10.4230/LIPIcs.ICALP.2019.76}, annote = {Keywords: approximation algorithms, knapsack, subset sum} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Marek Cygan, Marcin Mucha, Karol Wegrzycki, and Michal Wlodarczyk. On Problems Equivalent to (min,+)-Convolution. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 22:1-22:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{cygan_et_al:LIPIcs.ICALP.2017.22, author = {Cygan, Marek and Mucha, Marcin and Wegrzycki, Karol and Wlodarczyk, Michal}, title = {{On Problems Equivalent to (min,+)-Convolution}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {22:1--22: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.22}, URN = {urn:nbn:de:0030-drops-74216}, doi = {10.4230/LIPIcs.ICALP.2017.22}, annote = {Keywords: fine-grained complexity, knapsack, conditional lower bounds, (min,+)-convolution, subquadratic equivalence} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Marek Adamczyk, Fabrizio Grandoni, Stefano Leonardi, and Michal Wlodarczyk. When the Optimum is also Blind: a New Perspective on Universal Optimization. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 35:1-35:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{adamczyk_et_al:LIPIcs.ICALP.2017.35, author = {Adamczyk, Marek and Grandoni, Fabrizio and Leonardi, Stefano and Wlodarczyk, Michal}, title = {{When the Optimum is also Blind: a New Perspective on Universal Optimization}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {35:1--35: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.35}, URN = {urn:nbn:de:0030-drops-74436}, doi = {10.4230/LIPIcs.ICALP.2017.35}, annote = {Keywords: approximation algorithms, stochastic optimization, submodularity} }
Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Michal Wlodarczyk. Clifford Algebras Meet Tree Decompositions. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 29:1-29:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{wlodarczyk:LIPIcs.IPEC.2016.29, author = {Wlodarczyk, Michal}, title = {{Clifford Algebras Meet Tree Decompositions}}, booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, pages = {29:1--29:18}, 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.29}, URN = {urn:nbn:de:0030-drops-69260}, doi = {10.4230/LIPIcs.IPEC.2016.29}, annote = {Keywords: fixed-parameter tractability, treewidth, Clifford algebra, algebra isomorphism} }
Feedback for Dagstuhl Publishing