Michal Wlodarczyk

J. Comput. Syst. Sci., 2025

2024

Optimal Polynomial-Time Compression for Boolean Max CSP.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, March, 2024

Long directed detours: Reduction to 2-Disjoint Paths.

[BibT_eX]

[DOI]

Ashwin Jacob

Inf. Process. Lett., 2024

Losing Treewidth In The Presence Of Weights.

[BibT_eX]

[DOI]

CoRR, 2024

Does Subset Sum Admit Short Proofs?

[BibT_eX]

[DOI]

Proceedings of the 35th International Symposium on Algorithms and Computation, 2024

Constant Approximating Disjoint Paths on Acyclic Digraphs Is W[1]-Hard.

[BibT_eX]

[DOI]

Proceedings of the 35th International Symposium on Algorithms and Computation, 2024

2023

5-Approximation for $\mathcal{H}$-Treewidth Essentially as Fast as $\mathcal{H}$-Deletion Parameterized by Solution Size.

[BibT_eX]

[DOI]

CoRR, 2023

Sidestepping Barriers for Dominating Set in Parameterized Complexity.

[BibT_eX]

[DOI]

Ioannis Koutis

Proceedings of the 18th International Symposium on Parameterized and Exact Computation, 2023

Kernels for the Disjoint Paths Problem on Subclasses of Chordal Graphs.

[BibT_eX]

[DOI]

Proceedings of the 18th International Symposium on Parameterized and Exact Computation, 2023

Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Planar Disjoint Paths, Treewidth, and Kernels.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

5-Approximation for ℋ-Treewidth Essentially as Fast as ℋ-Deletion Parameterized by Solution Size.

[BibT_eX]

[DOI]

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

Finding Long Directed Cycles Is Hard Even When DFVS Is Small or Girth Is Large.

[BibT_eX]

[DOI]

Ashwin Jacob

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

Preprocessing for Outerplanar Vertex Deletion: An Elementary Kernel of Quartic Size.

[BibT_eX]

[DOI]

Huib Donkers

Algorithmica, 2022

Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

2021

Vertex deletion parameterized by elimination distance and even less.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

On the Hardness of Compressing Weights.

[BibT_eX]

[DOI]

Shivesh Kumar Roy

Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021

2020

To Close Is Easier Than To Open: Dual Parameterization To k-Median.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 18th International Workshop, 2020

Parameterized Inapproximability for Steiner Orientation by Gap Amplification.

[BibT_eX]

[DOI]

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019

On Problems Equivalent to (min, +)-Convolution.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2019

Multi-dimensional mechanism design via random order contention resolution schemes.

[BibT_eX]

[DOI]

Marek Adamczyk

SIGecom Exch., 2019

Inapproximability within W[1]: the case of Steiner Orientation.

[BibT_eX]

[DOI]

CoRR, 2019

Clifford Algebras Meet Tree Decompositions.

[BibT_eX]

[DOI]

Algorithmica, 2019

A Subquadratic Approximation Scheme for Partition.

[BibT_eX]

[DOI]

Marcin Mucha

Karol Wegrzycki

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Losing Treewidth by Separating Subsets.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Constant-Factor FPT Approximation for Capacitated k-Median.

[BibT_eX]

[DOI]

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018

Connected Components at Scale via Local Contractions.

[BibT_eX]

[DOI]

Jakub Lacki

Vahab S. Mirrokni

CoRR, 2018

Random Order Contention Resolution Schemes.

[BibT_eX]

[DOI]

Marek Adamczyk

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Evacuation from a Disc in the Presence of a Faulty Robot.

[BibT_eX]

[DOI]

Jurek Czyzowicz

Konstantinos Georgiou

Proceedings of the Structural Information and Communication Complexity, 2017

When the Optimum is also Blind: a New Perspective on Universal Optimization.

[BibT_eX]

[DOI]

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2015

An LP-rounding 2√2-approximation for restricted maximum acyclic subgraph.

[BibT_eX]

[DOI]

Fabrizio Grandoni

Tomasz Kociumaka

Inf. Process. Lett., 2015

Clustering reveals limits of parameter identifiability in multi-parameter models of biochemical dynamics.

[BibT_eX]

[DOI]

BMC Syst. Biol., 2015

2014

An LP-Rounding $2\sqrt{2}$ Approximation for Restricted Maximum Acyclic Subgraph.

[BibT_eX]

[DOI]

Fabrizio Grandoni

Tomasz Kociumaka