Daniel Lokshtanov

Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science, 2025

Parameterized Saga of First-Fit and Last-Fit Coloring.

[BibT_eX]

[DOI]

Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science, 2025

Parameterized Approximation for Capacitated d-Hitting Set with Hard Capacities.

[BibT_eX]

[DOI]

Abhishek Sahu

Jie Xue

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

Crossing Number in Slightly Superexponential Time (Extended Abstract).

[BibT_eX]

[DOI]

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

Fixed-Parameter Tractability of Hedge Cut.

[BibT_eX]

[DOI]

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

Tree Independence Number IV. Even-hole-free graphs.

[BibT_eX]

[DOI]

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

PTASes for Euclidean TSP with Unit Disk and Unit Square Neighborhoods.

[BibT_eX]

[DOI]

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

2024

Lower Bound for Independence Covering in C4-free Graphs.

[BibT_eX]

[DOI]

Michael Kuhn

Zachary Miller

ACM Trans. Comput. Theory, September, 2024

b-Coloring Parameterized by Clique-Width.

[BibT_eX]

[DOI]

Lars Jaffke

Paloma T. Lima

Theory Comput. Syst., August, 2024

True Contraction Decomposition and Almost ETH-Tight Bipartization for Unit-Disk Graphs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, July, 2024

The Parameterized Complexity of Guarding Almost Convex Polygons.

[BibT_eX]

[DOI]

Akanksha Agrawal

Kristine V. K. Knudsen

Meirav Zehavi

Discret. Comput. Geom., March, 2024

Shortest Cycles with Monotone Submodular Costs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, January, 2024

A Parameterized Approximation Scheme for Min $k$-Cut.

[BibT_eX]

[DOI]

SIAM J. Comput., 2024

Query Planning for Robust and Scalable Hybrid Network Telemetry Systems.

[BibT_eX]

[DOI]

Proc. ACM Netw., 2024

Robust Contraction Decomposition for Minor-Free Graphs and its Applications.

[BibT_eX]

[DOI]

CoRR, 2024

Maximum Partial List H-Coloring on P5-free graphs in polynomial time.

[BibT_eX]

[DOI]

CoRR, 2024

Subexponential Parameterized Algorithms for Hitting Subgraphs.

[BibT_eX]

[DOI]

CoRR, 2024

Odd Cycle Transversal on P5-free Graphs in Polynomial Time.

[BibT_eX]

[DOI]

CoRR, 2024

Degreewidth on Semi-complete Digraphs.

[BibT_eX]

[DOI]

Ryan Keeney

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

Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Meta-theorems for Parameterized Streaming Algorithms‡.

[BibT_eX]

[DOI]

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

Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition.

[BibT_eX]

[DOI]

Tuukka Korhonen

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

Euclidean Bottleneck Steiner Tree is Fixed-Parameter Tractable.

[BibT_eX]

[DOI]

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

Odd Cycle Transversal on P5-free Graphs in Quasi-polynomial Time.

[BibT_eX]

[DOI]

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

Kernelization of Counting Problems.

[BibT_eX]

[DOI]

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Parameterized Complexity of Kidney Exchange Revisited.

[BibT_eX]

[DOI]

Chinmay Sonar

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, 2024

Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints.

[BibT_eX]

[DOI]

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

When Far Is Better: The Chamberlin-Courant Approach to Obnoxious Committee Selection.

[BibT_eX]

[DOI]

Proceedings of the 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2024

Efficient Approximation of Fractional Hypertree Width.

[BibT_eX]

[DOI]

Viktoriia Korchemna

Jie Xue

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

A 1.9999-Approximation Algorithm for Vertex Cover on String Graphs.

[BibT_eX]

[DOI]

Proceedings of the 40th International Symposium on Computational Geometry, 2024

Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2024

2023

Polynomial Kernel for Interval Vertex Deletion.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, April, 2023

Erdős-Pósa property of obstructions to interval graphs.

[BibT_eX]

[DOI]

J. Graph Theory, April, 2023

On Induced Versions of Menger's Theorem on Sparse Graphs.

[BibT_eX]

[DOI]

Tuukka Korhonen

CoRR, 2023

Lower Bound for Independence Covering in C4-Free Graphs.

[BibT_eX]

[DOI]

Michael Kuhn

Zachary Miller

CoRR, 2023

Hitting Subgraphs in Sparse Graphs and Geometric Intersection Graphs.

[BibT_eX]

[DOI]

CoRR, 2023

An ETH-Tight Algorithm for Bidirected Steiner Connectivity.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 18th International Symposium, 2023

An Improved Parameterized Algorithm for Treewidth.

[BibT_eX]

[DOI]

Tuukka Korhonen

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

A Framework for Approximation Schemes on Disk Graphs.

[BibT_eX]

[DOI]

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

Graph Classes with Few Minimal Separators. II. A Dichotomy.

[BibT_eX]

[DOI]

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

Graph Classes with Few Minimal Separators. I. Finite Forbidden Induced Subgraphs.

[BibT_eX]

[DOI]

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

Parameterized Approximation Scheme for Feedback Vertex Set.

[BibT_eX]

[DOI]

Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science, 2023

Min-max coverage problems on tree-like metrics.

[BibT_eX]

[DOI]

Eric Aaron

Danny Krizanc

Proceedings of the XII Latin-American Algorithms, Graphs and Optimization Symposium, 2023

Breaking the All Subsets Barrier for Min k-Cut.

[BibT_eX]

[DOI]

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

Counting and Sampling Labeled Chordal Graphs in Polynomial Time.

[BibT_eX]

[DOI]

Eric Vigoda

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

Lossy Kernelization for (Implicit) Hitting Set Problems.

[BibT_eX]

[DOI]

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

Parameterized Complexity of Fair Bisection: (FPT-Approximation meets Unbreakability).

[BibT_eX]

[DOI]

Tanmay Inamdar

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

2022

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

[BibT_eX]

[DOI]

SIAM J. Comput., 2022

On the threshold of intractability.

[BibT_eX]

[DOI]

Pål Grønås Drange

Markus Fanebust Dregi

Blair D. Sullivan

J. Comput. Syst. Sci., 2022

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

[BibT_eX]

[DOI]

CoRR, 2022

Syotti: scalable bait design for DNA enrichment.

[BibT_eX]

[DOI]

Bioinform., 2022

On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets.

[BibT_eX]

[DOI]

Algorithmica, 2022

On the Maximum Number of Edges in Chordal Graphs of Bounded Degree and Matching Number.

[BibT_eX]

[DOI]

Algorithmica, 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

Subexponential Parameterized Algorithms on Disk Graphs (Extended Abstract).

[BibT_eX]

[DOI]

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

Subexponential Parameterized Algorithms for Cut and Cycle Hitting Problems on H<-Minor-Free Graphs.

[BibT_eX]

[DOI]

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

Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPT-Equivalent.

[BibT_eX]

[DOI]

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

Gehrlein Stable Committee with Multi-modal Preferences.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Game Theory - 15th International Symposium, 2022

Backdoor Sets on Nowhere Dense SAT.

[BibT_eX]

[DOI]

Fahad Panolan

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

Wordle Is NP-Hard.

[BibT_eX]

[DOI]

Bernardo Subercaseaux

Proceedings of the 11th International Conference on Fun with Algorithms, 2022

Point Separation and Obstacle Removal by Finding and Hitting Odd Cycles.

[BibT_eX]

[DOI]

Proceedings of the 38th International Symposium on Computational Geometry, 2022

2021

On the Parameterized Approximability of Contraction to Classes of Chordal Graphs.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2021

Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2021

Multiplicative Parameterization Above a Guarantee.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2021

2-Approximating Feedback Vertex Set in Tournaments.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2021

Approximate Counting of k-Paths: Simpler, Deterministic, and in Polynomial Space.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2021

Randomized Contractions Meet Lean Decompositions.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2021

ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs.

[BibT_eX]

[DOI]

J. Comput. Geom., 2021

Bisection of bounded treewidth graphs by convolutions.

[BibT_eX]

[DOI]

Eduard Eiben

Amer E. Mouawad

J. Comput. Syst. Sci., 2021

Faster and enhanced inclusion-minimal cograph completion.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2021

DynamiQ: Planning for Dynamics in Network Streaming Analytics Systems.

[BibT_eX]

[DOI]

CoRR, 2021

Elimination Distance to Topological-minor-free Graphs is FPT.

[BibT_eX]

[DOI]

CoRR, 2021

Computing the Largest Bond and the Maximum Connected Cut of a Graph.

[BibT_eX]

[DOI]

Lehilton L. C. Pedrosa

Rafael C. S. Schouery

Uéverton S. Souza

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

Exploiting Dense Structures in Parameterized Complexity.

[BibT_eX]

[DOI]

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

Efficient Computation of Representative Weight Functions with Applications to Parameterized Counting (Extended Version).

[BibT_eX]

[DOI]

Meirav Zehavi

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

FPT-approximation for FPT Problems.

[BibT_eX]

[DOI]

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

A Constant Factor Approximation for Navigating Through Connected Obstacles in the Plane.

[BibT_eX]

[DOI]

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

Diversity in Kemeny Rank Aggregation: A Parameterized Approach.

[BibT_eX]

[DOI]

Emmanuel Arrighi

Henning Fernau

Mateus de Oliveira Oliveira

Petra Wolf

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, 2021

Dominating Set in Weakly Closed Graphs is Fixed Parameter Tractable.

[BibT_eX]

[DOI]

Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2021

An ETH-Tight Algorithm for Multi-Team Formation.

[BibT_eX]

[DOI]

Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2021

Efficient Algorithms for Least Square Piecewise Polynomial Regression.

[BibT_eX]

[DOI]

Subhash Suri

Jie Xue

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

2020

A New Perspective on FO Model Checking of Dense Graph Classes.

[BibT_eX]

[DOI]

ACM Trans. Comput. Log., 2020

Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

Approximation Schemes for Low-rank Binary Matrix Approximation Problems.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

Polylogarithmic Approximation Algorithms for Weighted-ℱ-deletion Problems.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

Going Far from Degeneracy.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2020

Path Contraction Faster than 2n.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2020

Bidimensionality and Kernels.

[BibT_eX]

[DOI]

SIAM J. Comput., 2020

Independent Set on C≥-Free Graphs in Quasi-Polynomial Time.

[BibT_eX]

[DOI]

CoRR, 2020

Dominated Minimal Separators are Tame (Nearly All Others are Feral).

[BibT_eX]

[DOI]

CoRR, 2020

Independent Set on Pk-Free Graphs in Quasi-Polynomial Time.

[BibT_eX]

[DOI]

CoRR, 2020

A Polynomial Sized Kernel for Tracking Paths Problem.

[BibT_eX]

[DOI]

Algorithmica, 2020

An exponential time parameterized algorithm for planar disjoint paths.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Hitting topological minors is FPT.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Parameterized Complexity and Approximability of Directed Odd Cycle Transversal.

[BibT_eX]

[DOI]

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

Approximation Schemes via Width/Weight Trade-offs on Minor-free Graphs.

[BibT_eX]

[DOI]

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

Fault Tolerant Subgraphs with Applications in Kernelization.

[BibT_eX]

[DOI]

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Parameterization Above a Multiplicative Guarantee.

[BibT_eX]

[DOI]

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

A (2 + ε)-Factor Approximation Algorithm for Split Vertex Deletion.

[BibT_eX]

[DOI]

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

Parameterized Complexity of Feedback Vertex Sets on Hypergraphs.

[BibT_eX]

[DOI]

Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

Independent Set on $\mathrm{P}_{k}$-Free Graphs in Quasi-Polynomial Time.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Removing Connected Obstacles in the Plane Is FPT.

[BibT_eX]

[DOI]

Eduard Eiben

Proceedings of the 36th International Symposium on Computational Geometry, 2020

Fair Covering of Points by Balls.

[BibT_eX]

Proceedings of the 32nd Canadian Conference on Computational Geometry, 2020

Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths.

[BibT_eX]

[DOI]

Meirav Zehavi

Proceedings of the Treewidth, Kernels, and Algorithms, 2020

Parameterized Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Beyond the Worst-Case Analysis of Algorithms, 2020

2019

Split Contraction: The Untold Story.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2019

The Complexity of Independent Set Reconfiguration on Bipartite Graphs.

[BibT_eX]

[DOI]

Amer E. Mouawad

ACM Trans. Algorithms, 2019

Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2019

Clique-width III: Hamiltonian Cycle and the Odd Case of Graph Coloring.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2019

Spanning Circuits in Regular Matroids.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2019

Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2019

Balanced Judicious Bipartition is Fixed-Parameter Tractable.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2019

Packing Cycles Faster Than Erdos-Posa.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2019

Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2019

Minimum Bisection Is Fixed-Parameter Tractable.

[BibT_eX]

[DOI]

SIAM J. Comput., 2019

Exact Algorithms via Monotone Local Search.

[BibT_eX]

[DOI]

J. ACM, 2019

Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2019

A Brief Note on Single Source Fault Tolerant Reachability.

[BibT_eX]

[DOI]

CoRR, 2019

Reducing Topological Minor Containment to the Unique Linkage Theorem.

[BibT_eX]

[DOI]

CoRR, 2019

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

[BibT_eX]

[DOI]

Algorithmica, 2019

Wannabe Bounded Treewidth Graphs Admit a Polynomial Kernel for DFVS.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 16th International Symposium, 2019

Picking Random Vertices (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

Computing the Largest Bond of a Graph.

[BibT_eX]

[DOI]

Gabriel L. Duarte

Lehilton L. C. Pedrosa

Rafael C. S. Schouery

Uéverton S. Souza

Proceedings of the 14th International Symposium on Parameterized and Exact Computation, 2019

Decomposition of Map Graphs with Applications.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Approximate Counting of k-Paths: Deterministic and in Polynomial Space.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

Simultaneous Feedback Vertex Set: A Parameterized Perspective.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2018

Linear Time Parameterized Algorithms for Subset Feedback Vertex Set.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2018

Independence and Efficient Domination on P6-free Graphs.

[BibT_eX]

[DOI]

Marcin Pilipczuk

Erik Jan van Leeuwen

ACM Trans. Algorithms, 2018

Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2018

Deterministic Truncation of Linear Matroids.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2018

Kernels for (Connected) Dominating Set on Graphs with Excluded Topological Minors.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2018

Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2018

Below All Subsets for Minimal Connected Dominating Set.

[BibT_eX]

[DOI]

Michal Pilipczuk

SIAM J. Discret. Math., 2018

Matrix Rigidity from the Viewpoint of Parameterized Complexity.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2018

Covering Vectors by Spaces: Regular Matroids.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2018

Kernelization of Cycle Packing with Relaxed Disjointness Constraints.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2018

Slightly Superexponential Parameterized Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2018

Reconfiguration on sparse graphs.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2018

Excluded Grid Minors and Efficient Polynomial-Time Approximation Schemes.

[BibT_eX]

[DOI]

J. ACM, 2018

Long directed (s, t)-path: FPT algorithm.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2018

Randomized contractions meet lean decompositions.

[BibT_eX]

[DOI]

CoRR, 2018

A 2-Approximation Algorithm for Feedback Vertex Set in Tournaments.

[BibT_eX]

[DOI]

CoRR, 2018

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

[BibT_eX]

[DOI]

CoRR, 2018

When Recursion is Better than Iteration: A Linear-Time Algorithm for Acyclicity with Few Error Vertices.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Beating Brute Force for (Quantified) Satisfiability of Circuits of Bounded Treewidth.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Cliquewidth III: The Odd Case of Graph Coloring Parameterized by Cliquewidth.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Conflict Free Feedback Vertex Set: A Parameterized Dichotomy.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

A Strongly-Uniform Slicewise Polynomial-Time Algorithm for the Embedded Planar Diameter Improvement Problem.

[BibT_eX]

[DOI]

Mateus de Oliveira Oliveira

Proceedings of the 13th International Symposium on Parameterized and Exact Computation, 2018

The Parameterized Complexity of Finding Point Sets with Hereditary Properties.

[BibT_eX]

[DOI]

David Eppstein

Archontia C. Giannopoulou

Proceedings of the 13th International Symposium on Parameterized and Exact Computation, 2018

Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity.

[BibT_eX]

[DOI]

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Reducing CMSO Model Checking to Highly Connected Graphs.

[BibT_eX]

[DOI]

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Brief Announcement: Treewidth Modulator: Emergency Exit for DFVS.

[BibT_eX]

[DOI]

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Algorithms for Low-Distortion Embeddings into Arbitrary 1-Dimensional Spaces.

[BibT_eX]

[DOI]

Anastasios Sidiropoulos

Proceedings of the 34th International Symposium on Computational Geometry, 2018

2017

Uniform Kernelization Complexity of Hitting Forbidden Minors.

[BibT_eX]

[DOI]

Bart M. P. Jansen

ACM Trans. Algorithms, 2017

Representative Families of Product Families.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2017

Hitting Selected (Odd) Cycles.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2017

Parameterized Complexity of Directed Steiner Tree on Sparse Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2017

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

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

Irrelevant vertices for the planar Disjoint Paths Problem.

[BibT_eX]

[DOI]

Isolde Adler

Stavros G. Kolliopoulos

Philipp Klaus Krause

J. Comb. Theory B, 2017

Faster exact algorithms for some terminal set problems.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2017

Balanced Judicious Partition is Fixed-Parameter Tractable.

[BibT_eX]

[DOI]

CoRR, 2017

The Half-integral Erdös-Pósa Property for Non-null Cycles.

[BibT_eX]

[DOI]

CoRR, 2017

Polylogarithmic Approximation Algorithms for Weighted-$\mathcal{F}$-Deletion Problems.

[BibT_eX]

[DOI]

CoRR, 2017

Quick but Odd Growth of Cacti.

[BibT_eX]

[DOI]

Algorithmica, 2017

Critical Node Cut Parameterized by Treewidth and Solution Size is W[1]-Hard.

[BibT_eX]

[DOI]

Akanksha Agrawal

Amer E. Mouawad

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

Lossy kernelization.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Beating Brute Force for Systems of Polynomial Equations over Finite Fields.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

On the Parameterized Complexity of Simultaneous Deletion Problems.

[BibT_eX]

[DOI]

Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017

A Linear-Time Parameterized Algorithm for Node Unique Label Cover.

[BibT_eX]

[DOI]

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

2016

Kernelization, Bidimensionality and Kernels.

[BibT_eX]

[DOI]

Archontia C. Giannopoulou

Encyclopedia of Algorithms, 2016

On Problems as Hard as CNF-SAT.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

Tree Deletion Set Has a Polynomial Kernel but No OPTO(1) Approximation.

[BibT_eX]

[DOI]

Ondrej Suchý

SIAM J. Discret. Math., 2016

Hitting Forbidden Minors: Approximation and Kernelization.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2016

A ck n 5-Approximation Algorithm for Treewidth.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms.

[BibT_eX]

[DOI]

J. ACM, 2016

(Meta) Kernelization.

[BibT_eX]

[DOI]

J. ACM, 2016

A Linear Time Parameterized Algorithm for Directed Feedback Vertex Set.

[BibT_eX]

[DOI]

CoRR, 2016

On the Ordered List Subgraph Embedding Problems.

[BibT_eX]

[DOI]

Algorithmica, 2016

Lower Bounds for Approximation Schemes for Closest String.

[BibT_eX]

[DOI]

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

Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Tournaments.

[BibT_eX]

[DOI]

Mithilesh Kumar

Fernando Sánchez Villaamil

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

Kernelization and Sparseness: the Case of Dominating Set.

[BibT_eX]

[DOI]

Pål Grønås Drange

Markus Sortland Dregi

Sebastian Siebertz

Somnath Sikdar

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

A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2016: Theoretical Informatics, 2016

A 2lk Kernel for l-Component Order Connectivity.

[BibT_eX]

[DOI]

Mithilesh Kumar

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

Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments.

[BibT_eX]

[DOI]

Mithilesh Kumar

Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2016

2015

Independence and Efficient Domination on P6-free Graph.

[BibT_eX]

[DOI]

Marcin Pilipczuk

Erik Jan van Leeuwen

CoRR, 2015

Parameterized Integer Quadratic Programming: Variables and Coefficients.

[BibT_eX]

[DOI]

CoRR, 2015

Solving d-SAT via Backdoors to Small Treewidth.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

FO Model Checking on Posets of Bounded Width.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints.

[BibT_eX]

[DOI]

Ariel Gabizon

Michal Pilipczuk

Proceedings of the Algorithms - ESA 2015, 2015

Consensus Patterns (Probably) Has no EPTAS.

[BibT_eX]

[DOI]

Christina Boucher

Christine Lo

Proceedings of the Algorithms - ESA 2015, 2015

Parameterized Algorithms

[BibT_eX]

[DOI]

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

2014

SeeSite: Characterizing Relationships between Splice Junctions and Splicing Enhancers.

[BibT_eX]

[DOI]

IEEE ACM Trans. Comput. Biol. Bioinform., 2014

Faster Parameterized Algorithms Using Linear Programming.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2014

Kernelization Lower Bounds Through Colors and IDs.

[BibT_eX]

[DOI]

Michael Dom

ACM Trans. Algorithms, 2014

Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

On the Hardness of Losing Width.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2014

Optimality and tight results in parameterized complexity (Dagstuhl Seminar 14451).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2014

Graph Modification Problems (Dagstuhl Seminar 14071).

[BibT_eX]

[DOI]

Hans L. Bodlaender

Pinar Heggernes

Dagstuhl Reports, 2014

Representative sets for multisets.

[BibT_eX]

[DOI]

Ariel Gabizon

Fernando Sánchez Villaamil

Michal Pilipczuk

CoRR, 2014

Kernelization and Sparseness: the case of Dominating Set.

[BibT_eX]

[DOI]

Somnath Sikdar

CoRR, 2014

Contracting Graphs to Paths and Trees.

[BibT_eX]

[DOI]

Algorithmica, 2014

On Cutwidth Parameterized by Vertex Cover.

[BibT_eX]

[DOI]

Algorithmica, 2014

Independent Set in P5-Free Graphs in Polynomial Time.

[BibT_eX]

[DOI]

Martin Vatshelle

Yngve Villanger

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

A Near-Optimal Planarization Algorithm.

[BibT_eX]

[DOI]

Bart M. P. Jansen

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Parameterized Complexity of Bandwidth on Trees.

[BibT_eX]

[DOI]

Markus Sortland Dregi

Archontia C. Giannopoulou

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Tree Deletion Set Has a Polynomial Kernel (but no OPT^O(1) Approximation).

[BibT_eX]

[DOI]

Ondrej Suchý

Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, 2014

Solving Multicut Faster Than 2 n.

[BibT_eX]

[DOI]

Ondrej Suchý

Proceedings of the Algorithms - ESA 2014, 2014

Representative Sets of Product Families.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2014, 2014

2013

Distortion is Fixed Parameter Tractable.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2013

Obtaining a Bipartite Graph by Contracting Few Edges.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2013

Quadratic Upper Bounds on the Erdős-Pósa Property for a Generalization of Packing and Covering Cycles.

[BibT_eX]

[DOI]

J. Graph Theory, 2013

Imbalance is fixed parameter tractable.

[BibT_eX]

[DOI]

Neeldhara Misra

Inf. Process. Lett., 2013

Clustering with local restrictions.

[BibT_eX]

[DOI]

Inf. Comput., 2013

Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing via iterative localization.

[BibT_eX]

[DOI]

Inf. Comput., 2013

Beyond bidimensionality: Parameterized subexponential algorithms on directed graphs.

[BibT_eX]

[DOI]

Inf. Comput., 2013

A O(c^k n) 5-Approximation Algorithm for Treewidth

[BibT_eX]

[DOI]

CoRR, 2013

Computing Optimal Steiner Trees in Polynomial Space.

[BibT_eX]

[DOI]

Algorithmica, 2013

Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs.

[BibT_eX]

[DOI]

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

On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges.

[BibT_eX]

[DOI]

Neeldhara Misra

Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

Hardness of r-dominating set on Graphs of Diameter (r + 1).

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

The Fine Details of Fast Dynamic Programming over Tree Decompositions.

[BibT_eX]

[DOI]

Hans L. Bodlaender

Paul S. Bonsma

Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

Near-Optimal Bounds for Cross-Validation via Loss Stability.

[BibT_eX]

[DOI]

Proceedings of the 30th International Conference on Machine Learning, 2013

An O(c^k n) 5-Approximation Algorithm for Treewidth.

[BibT_eX]

[DOI]

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

2012

Kernel(s) for problems with no kernel: On out-trees with many leaves.

[BibT_eX]

[DOI]

Daniel Binkele-Raible

ACM Trans. Algorithms, 2012

Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2012

Cops and Robber Game Without Recharging.

[BibT_eX]

[DOI]

Petr A. Golovach

Theory Comput. Syst., 2012

Faster algorithms for finding and counting subgraphs.

[BibT_eX]

[DOI]

B. V. Raghavendra Rao

J. Comput. Syst. Sci., 2012

Local search: Is brute-force avoidable?

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2012

Planar F-Deletion: Approximation and Optimal FPT Algorithms

[BibT_eX]

[DOI]

CoRR, 2012

Sharp Separation and Applications to Exact and Parameterized Algorithms.

[BibT_eX]

[DOI]

Algorithmica, 2012

Linear kernels for (connected) dominating set on H-minor-free graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Bidimensionality and geometric graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Parameterized Tractability of Multiway Cut with Parity Constraints.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Subexponential Parameterized Odd Cycle Transversal on Planar Graphs.

[BibT_eX]

[DOI]

Magnus Wahlström

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

Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Kernelization - Preprocessing with a Guarantee.

[BibT_eX]

[DOI]

Neeldhara Misra

Proceedings of the Multivariate Algorithmic Revolution and Beyond, 2012

2011

A linear kernel for planar connected dominating set.

[BibT_eX]

[DOI]

Matthias Mnich

Theor. Comput. Sci., 2011

Bandwidth on AT-free graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

An exact algorithm for minimum distortion embedding.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

Guard games on graphs: Keep the intruder out!

[BibT_eX]

[DOI]

Petr A. Golovach

Theor. Comput. Sci., 2011

Cutwidth of Split Graphs and Threshold Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2011

On the complexity of reconstructing H-free graphs from their Star Systems.

[BibT_eX]

[DOI]

J. Graph Theory, 2011

Subexponential algorithms for partial cover problems.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2011

On the complexity of some colorful problems parameterized by treewidth.

[BibT_eX]

[DOI]

Inf. Comput., 2011

Lower bounds based on the Exponential Time Hypothesis.

[BibT_eX]

[DOI]

Bull. EATCS, 2011

On the directed Full Degree Spanning Tree problem.

[BibT_eX]

[DOI]

Discret. Optim., 2011

Treewidth governs the complexity of target set selection.

[BibT_eX]

[DOI]

Discret. Optim., 2011

On Problems as Hard as CNFSAT

[BibT_eX]

[DOI]

CoRR, 2011

Outlier Detection for DNA Fragment Assembly

[BibT_eX]

[DOI]

Christina Boucher

Christine Lo

CoRR, 2011

Planar k-Path in Subexponential Time and Polynomial Space.

[BibT_eX]

[DOI]

Matthias Mnich

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

Feedback Vertex Set in Mixed Graphs.

[BibT_eX]

[DOI]

Paul S. Bonsma

Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

Bidimensionality and EPTAS.

[BibT_eX]

[DOI]

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

Tight Bounds for Linkages in Planar Graphs.

[BibT_eX]

[DOI]

Isolde Adler

Stavros G. Kolliopoulos

Philipp Klaus Krause

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Kernelization: An Overview.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory - 18th International Symposium, 2011

2010

Intractability of Clique-Width Parameterizations.

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

Characterizing and computing minimal cograph completions.

[BibT_eX]

[DOI]

Federico Mancini

Charis Papadopoulos

Discret. Appl. Math., 2010

On the complexity of computing treelength.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2010

Generalized Graph Clustering: Recognizing (p, q)-Cluster Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph Theoretic Concepts in Computer Science, 2010

Fixed-Parameter Algorithms for Cochromatic Number and Disjoint Rectangle Stabbing.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 2010

Saving space by algebraization.

[BibT_eX]

[DOI]

Jesper Nederlof

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Algorithmic Lower Bounds for Problems Parameterized with Clique-Width.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Algorithmic Lower Bounds for Problems on Decomposable Graphs.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

Ranking and Drawing in Subexponential Time.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 21st International Workshop, 2010

Determining the Winner of a Dodgson Election is Hard.

[BibT_eX]

[DOI]

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

Fast Local Search Algorithm for Weighted Feedback Arc Set in Tournaments.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, 2010

2009

The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2009

Finding the longest isometric cycle in a graph.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2009

Clique-width: on the price of generality.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

An exact almost optimal algorithm for target set selection in social networks.

[BibT_eX]

[DOI]

Proceedings of the Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), 2009

Even Faster Algorithm for Set Splitting!

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009

On the Directed Degree-Preserving Spanning Tree Problem.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009

Planar Capacitated Dominating Set Is W[1]-Hard.

[BibT_eX]

[DOI]

Hans L. Bodlaender

Eelko Penninkx

Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009

Simpler Parameterized Algorithm for OCT.

[BibT_eX]

[DOI]

Somnath Sikdar

Proceedings of the Combinatorial Algorithms, 20th International Workshop, 2009

Incompressibility through Colors and IDs.

[BibT_eX]

[DOI]

Michael Dom

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Fast FAST.

[BibT_eX]

[DOI]

Noga Alon

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

2008

Parameterized Low-distortion Embeddings - Graph metrics into lines and trees

[BibT_eX]

[DOI]

CoRR, 2008

Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs.

[BibT_eX]

[DOI]

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

On the Complexity of Reconstructing H -free Graphs from Their Star Systems.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2008: Theoretical Informatics, 2008

Wheel-Free Deletion Is W[2]-Hard.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation, Third International Workshop, 2008

Capacitated Domination and Covering: A Parameterized Perspective.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation, Third International Workshop, 2008

Graph Layout Problems Parameterized by Vertex Cover.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

2006

Optimal broadcast domination in polynomial time.

[BibT_eX]

[DOI]

Pinar Heggernes

Discret. Math., 2006

2005

Optimal Broadcast Domination of Arbitrary Graphs in Polynomial Time.

[BibT_eX]

[DOI]

Pinar Heggernes

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

Fixed Parameter Set Splitting, Linear Kernel and Improved Running Time.

[BibT_eX]