Marcin Pilipczuk

ACM Trans. Algorithms, 2022

Constant Congestion Brambles in Directed Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2022

A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs.

[BibT_eX]

[DOI]

Dániel Marx

SIAM J. Comput., 2022

Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering.

[BibT_eX]

[DOI]

SIAM J. Comput., 2022

Constant Congestion Brambles.

[BibT_eX]

[DOI]

Discret. Math. Theor. Comput. Sci., 2022

Highly unbreakable graph with a fixed excluded minor are almost rigid.

[BibT_eX]

[DOI]

CoRR, 2022

Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of P4.

[BibT_eX]

[DOI]

CoRR, 2022

On weighted graph separation problems and flow-augmentation.

[BibT_eX]

[DOI]

CoRR, 2022

Hardness of Metric Dimension in Graphs of Constant Treewidth.

[BibT_eX]

[DOI]

Algorithmica, 2022

Preface to the Special Issue on Parameterized and Exact Computation.

[BibT_eX]

[DOI]

Yixin Cao

Algorithmica, 2022

Bounding Twin-Width for Bounded-Treewidth Graphs, Planar Graphs, and Bipartite Graphs.

[BibT_eX]

[DOI]

Hugo Jacob

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2022

Fixed-parameter tractability of graph isomorphism in graphs with an excluded minor.

[BibT_eX]

[DOI]

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

Directed flow-augmentation.

[BibT_eX]

[DOI]

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

On the Complexity of Problems on Tree-Structured Graphs.

[BibT_eX]

[DOI]

Proceedings of the 17th International Symposium on Parameterized and Exact Computation, 2022

Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Taming Graphs with No Large Creatures and Skinny Ladders.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021

Randomized Contractions Meet Lean Decompositions.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2021

A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs.

[BibT_eX]

[DOI]

Erik Jan van Leeuwen

SIAM J. Discret. Math., 2021

Improved Bounds for the Excluded-Minor Approximation of Treedepth.

[BibT_eX]

[DOI]

Wojciech Czerwinski

Wojciech Nadara

SIAM J. Discret. Math., 2021

(Theta, triangle)-free and (even hole, K4)-free graphs. Part 2: Bounds on treewidth.

[BibT_eX]

[DOI]

J. Graph Theory, 2021

Covering Minimal Separators and Potential Maximal Cliques in $P_t$-Free Graphs.

[BibT_eX]

[DOI]

Electron. J. Comb., 2021

Jones' Conjecture in Subcubic Graphs.

[BibT_eX]

[DOI]

Electron. J. Comb., 2021

Polynomial Treedepth Bounds in Linear Colorings.

[BibT_eX]

[DOI]

Algorithmica, 2021

Finding large induced sparse subgraphs in c>t -free graphs in quasipolynomial time.

[BibT_eX]

[DOI]

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

Cluster Editing Parameterized Above Modification-Disjoint P₃-Packings.

[BibT_eX]

[DOI]

Manuel Sorge

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

Quasi-polynomial-time algorithm for Independent Set in Pt-free graphs via shrinking the space of induced paths.

[BibT_eX]

[DOI]

Pawel Rzazewski

Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

Optimal Discretization is Fixed-parameter Tractable.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Solving hard cut problems via flow-augmentation.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Efficient fully dynamic elimination forests with applications to detecting long paths and cycles.

[BibT_eX]

[DOI]

Jiehua Chen

Wojciech Czerwinski

Yann Disser

Andreas Emil Feldmann

Bartlomiej Wróblewski

Anna Zych-Pawlewicz

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Induced subgraphs of bounded treewidth and the container method.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Close Relatives (Of Feedback Vertex Set), Revisited.

[BibT_eX]

[DOI]

Proceedings of the 16th International Symposium on Parameterized and Exact Computation, 2021

2020

Introduction to the Special Issue on SODA'18.

[BibT_eX]

[DOI]

Yin Tat Lee

David P. Woodruff

ACM Trans. Algorithms, 2020

On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2020

An Improved FPT Algorithm for Independent Feedback Vertex Set.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2020

A Double Exponential Lower Bound for the Distinct Vectors Problem.

[BibT_eX]

[DOI]

Manuel Sorge

Discret. Math. Theor. Comput. Sci., 2020

Two lower bounds for $p$-centered colorings.

[BibT_eX]

[DOI]

Discret. Math. Theor. Comput. Sci., 2020

Quasi-polynomial-time algorithm for Independent Set in Pt-free and C>t-free graphs via shrinking the space of connecting subgraphs.

[BibT_eX]

[DOI]

Pawel Rzazewski

CoRR, 2020

On Dynamic Parameterized k-Path.

[BibT_eX]

[DOI]

Jiehua Chen

Wojciech Czerwinski

Yann Disser

Andreas Emil Feldmann

Bartlomiej Wróblewski

Anna Zych-Pawlewicz

CoRR, 2020

Covering minimal separators and potential maximal cliques in Pt-free graphs.

[BibT_eX]

[DOI]

CoRR, 2020

Multi-budgeted Directed Cuts.

[BibT_eX]

[DOI]

Algorithmica, 2020

Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth.

[BibT_eX]

[DOI]

Proceedings of the 15th International Symposium on Parameterized and Exact Computation, 2020

The Complexity of Connectivity Problems in Forbidden-Transition Graphs And Edge-Colored Graphs.

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Algorithms and Computation, 2020

Surprising Applications of Treewidth Bounds for Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the Treewidth, Kernels, and Algorithms, 2020

2019

Minimum Bisection Is Fixed-Parameter Tractable.

[BibT_eX]

[DOI]

SIAM J. Comput., 2019

Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation.

[BibT_eX]

[DOI]

Michal Ziobro

ACM J. Exp. Algorithmics, 2019

Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness.

[BibT_eX]

[DOI]

ACM J. Exp. Algorithmics, 2019

Caterpillars in Erdős-Hajnal.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. B, 2019

Jones' Conjecture in subcubic graphs.

[BibT_eX]

[DOI]

CoRR, 2019

Cluster Editing parameterized above the size of a modification-disjoint P3 packing is para-NP-hard.

[BibT_eX]

[DOI]

Manuel Sorge

CoRR, 2019

Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs.

[BibT_eX]

[DOI]

CoRR, 2019

Edge Bipartization Faster than $$2^k$$ 2 k.

[BibT_eX]

[DOI]

Algorithmica, 2019

Deleting Vertices to Graphs of Bounded Genus.

[BibT_eX]

[DOI]

Tomasz Kociumaka

Algorithmica, 2019

An Exponential Lower Bound for Cut Sparsifiers in Planar Graphs.

[BibT_eX]

[DOI]

Nikolai Karpov

Anna Zych-Pawlewicz

Algorithmica, 2019

Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor.

[BibT_eX]

[DOI]

Algorithmica, 2019

Subexponential-Time Algorithms for Maximum Independent Set in $$P_t$$ P t -Free and Broom-Free Graphs.

[BibT_eX]

[DOI]

Algorithmica, 2019

Polynomial-time algorithm for Maximum Weight Independent Set on P6-free graphs.

[BibT_eX]

[DOI]

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

A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs.

[BibT_eX]

[DOI]

Vincent Cohen-Addad

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Packing Directed Circuits Quarter-Integrally.

[BibT_eX]

[DOI]

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

Efficient Approximation Schemes for Uniform-Cost Clustering Problems in Planar Graphs.

[BibT_eX]

[DOI]

Vincent Cohen-Addad

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

2018

Directed Multicut is W[1]-hard, Even for Four Terminal Pairs.

[BibT_eX]

[DOI]

Magnus Wahlström

ACM Trans. Comput. Theory, 2018

Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2018

Independence and Efficient Domination on P6-free Graphs.

[BibT_eX]

[DOI]

Daniel Lokshtanov

Erik Jan van Leeuwen

ACM Trans. Algorithms, 2018

Subexponential Parameterized Algorithm for Interval Completion.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2018

Approximation and Kernelization for Chordal Vertex Deletion.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2018

Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs.

[BibT_eX]

[DOI]

Chandra Chekuri

Alina Ene

SIAM J. Discret. Math., 2018

Experimental Evaluation of Parameterized Algorithms for Graph Separation Problems: Half-Integral Relaxations and Matroid-based Kernelization.

[BibT_eX]

[DOI]

Michal Ziobro

CoRR, 2018

Randomized contractions meet lean decompositions.

[BibT_eX]

[DOI]

CoRR, 2018

Subexponential-time Algorithms for Maximum Independent Set in Pt-free and Broom-free Graphs.

[BibT_eX]

[DOI]

CoRR, 2018

Excluding Hooks and their Complements.

[BibT_eX]

[DOI]

Krzysztof Choromanski

Electron. J. Comb., 2018

Experimental Evaluation of Parameterized Algorithms for Feedback Vertex Set.

[BibT_eX]

[DOI]

Krzysztof Kiljan

Proceedings of the 17th International Symposium on Experimental Algorithms, 2018

On Subexponential Parameterized Algorithms for Steiner Tree and Directed Subset TSP on Planar Graphs.

[BibT_eX]

[DOI]

Dániel Marx

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

Planar Digraphs.

[BibT_eX]

[DOI]

Proceedings of the Classes of Directed Graphs., 2018

2017

Hardness of Approximation for Strip Packing.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2017

Editorial.

[BibT_eX]

[DOI]

Alexandr Andoni

Debmalya Panigrahi

ACM Trans. Algorithms, 2017

Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

Polynomial Kernelization for Removing Induced Claws and Diamonds.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2017

Hitting forbidden subgraphs in graphs of bounded treewidth.

[BibT_eX]

[DOI]

Inf. Comput., 2017

A tight lower bound for Vertex Planarization on graphs of bounded treewidth.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2017

The Erdős-Hajnal conjecture for caterpillars and their complements.

[BibT_eX]

[DOI]

Anita Liebenau

CoRR, 2017

Polynomial-time algorithm for Maximum Weight Independent Set on $P_6$-free graphs.

[BibT_eX]

[DOI]

CoRR, 2017

Turing Kernelization for Finding Long Paths in Graphs Excluding a Topological Minor.

[BibT_eX]

[DOI]

Proceedings of the 12th International Symposium on Parameterized and Exact Computation, 2017

Subexponential Parameterized Algorithms for Graphs of Polynomial Growth.

[BibT_eX]

[DOI]

Dániel Marx

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016

Planar Directed k-Vertex-Disjoint Paths Problem.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Exact Algorithms on Graphs of Bounded Average Degree.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Known Algorithms for Edge Clique Cover are Probably Optimal.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

Designing FPT Algorithms for Cut Problems Using Randomized Contractions.

[BibT_eX]

[DOI]

Rajesh Chitnis

MohammadTaghi Hajiaghayi

SIAM J. Comput., 2016

A Fast Branching Algorithm for Cluster Vertex Deletion.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2016

On Group Feedback Vertex Set Parameterized by the Size of the Cutset.

[BibT_eX]

[DOI]

Fernando Sánchez Villaamil

Algorithmica, 2016

On Routing Disjoint Paths in Bounded Treewidth Graphs.

[BibT_eX]

[DOI]

Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

Lower Bounds for Approximation Schemes for Closest String.

[BibT_eX]

[DOI]

Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

Kernelization and Sparseness: the Case of Dominating Set.

[BibT_eX]

[DOI]

Pål Grønås Drange

Markus Sortland Dregi

Saket Saurabh

Sebastian Siebertz

Somnath Sikdar

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Directed multicut is W[1]-hard, even for four terminal pairs.

[BibT_eX]

[DOI]

Magnus Wahlström

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Edge Bipartization Faster Than 2^k.

[BibT_eX]

[DOI]

Proceedings of the 11th International Symposium on Parameterized and Exact Computation, 2016

2015

Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2015

A Subexponential Parameterized Algorithm for Proper Interval Completion.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2015

Sitting Closer to Friends than Enemies, Revisited.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2015

Faster exponential-time algorithms in graphs of bounded average degree.

[BibT_eX]

[DOI]

Inf. Comput., 2015

Edge Bipartization faster than 2k.

[BibT_eX]

[DOI]

CoRR, 2015

Independence and Efficient Domination on P6-free Graph.

[BibT_eX]

[DOI]

Daniel Lokshtanov

Erik Jan van Leeuwen

CoRR, 2015

The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Parameterized Algorithms

[BibT_eX]

[DOI]

Springer, ISBN: 978-3-319-21275-3, 2015

2014

Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2014

Clique Cover and Graph Separation: New Incompressibility Results.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2014

On the Hardness of Losing Width.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2014

Tight bounds for parameterized complexity of Cluster Editing with a small number of clusters.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2014

Faster deterministic Feedback Vertex Set.

[BibT_eX]

[DOI]

Tomasz Kociumaka

Fernando Sánchez Villaamil

Inf. Process. Lett., 2014

Kernelization and Sparseness: the case of Dominating Set.

[BibT_eX]

[DOI]

Somnath Sikdar

CoRR, 2014

Solving the 2-Disjoint Connected Subgraphs Problem Faster than 2 n.

[BibT_eX]

[DOI]

Algorithmica, 2014

Scheduling Partially Ordered Jobs Faster than 2 n.

[BibT_eX]

[DOI]

Algorithmica, 2014

Parameterized Complexity of Eulerian Deletion Problems.

[BibT_eX]

[DOI]

Algorithmica, 2014

On Cutwidth Parameterized by Vertex Cover.

[BibT_eX]

[DOI]

Algorithmica, 2014

2013

On multiway cut parameterized above lower bounds.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2013

Subset Feedback Vertex Set Is Fixed-Parameter Tractable.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2013

Split Vertex Deletion meets Vertex Cover: New fixed-parameter and exact exponential-time algorithms.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2013

A bound on the number of perfect matchings in Klee-graphs.

[BibT_eX]

[DOI]

Riste Skrekovski

Discret. Math. Theor. Comput. Sci., 2013

Towards optimal kernel for connected vertex cover in planar graphs.

[BibT_eX]

[DOI]

Lukasz Kowalik

Karol Suchan

Discret. Appl. Math., 2013

Dynamic Steiner Tree in Planar Graphs.

[BibT_eX]

[DOI]

CoRR, 2013

Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Tight bounds for Parameterized Complexity of Cluster Editing.

[BibT_eX]

[DOI]

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

The Planar Directed K-Vertex-Disjoint Paths Problem Is Fixed-Parameter Tractable.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

Even Faster Exact Bandwidth.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2012

A Polynomial Algorithm for 3-Compatible Coloring and the Stubborn List Partition Problem (The Stubborn Problem Is Stubborn No More).

[BibT_eX]

[DOI]

SIAM J. Comput., 2012

Some results on Vizing's conjecture and related problems.

[BibT_eX]

[DOI]

Riste Skrekovski

Discret. Appl. Math., 2012

Kernelization hardness of connectivity problems in d-degenerate graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2012

Bandwidth and distortion revisited.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2012

On fixed-parameter algorithms for Split Vertex Deletion

[BibT_eX]

[DOI]

CoRR, 2012

An Improved FPT Algorithm and a Quadratic Kernel for Pathwidth One Vertex Deletion.

[BibT_eX]

[DOI]

Algorithmica, 2012

Finding a Maximum Induced Degenerate Subgraph Faster Than 2 n.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation - 7th International Symposium, 2012

A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2012, 2012

2011

Dominating set is fixed parameter tractable in claw-free graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

Breaking the 2n-barrier for Irredundance: Two lines of attack.

[BibT_eX]

[DOI]

Daniel Binkele-Raible

J. Discrete Algorithms, 2011

Capacitated domination faster than O(n2).

[BibT_eX]

[DOI]

Inf. Process. Lett., 2011

On the Zagreb index inequality of graphs with prescribed vertex degrees.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2011

Subexponential fixed-parameter tractability of cluster editing

[BibT_eX]

[DOI]

CoRR, 2011

The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem).

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Approximation Algorithms for Union and Intersection Covering Problems.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

2010

Exact and approximate bandwidth.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2010

Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph Theoretic Concepts in Computer Science, 2010

Capacitated Domination Faster Than O(2n).

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 2010

Fast Approximation in Subspaces by Doubling Metric Decomposition.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2010

Irredundant Set Faster Than O(2n).

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity, 7th International Conference, 2010

2009

Beyond O*(2^n) in domination-type problems

[BibT_eX]

[DOI]

CoRR, 2009

2008

Exponential-Time Approximation of Hard Problems

[BibT_eX]

[DOI]

CoRR, 2008

Faster Exact Bandwidth.

[BibT_eX]

[DOI]