| Publication | Date of Publication | Type |
|---|
Upward and rectilinear planarity are W[1]-hard parameterized by treewidth
SIAM Journal on Discrete Mathematics | 2026-06-03 | Paper |
| Preprocessing to reduce the search space for odd cycle transversal | 2026-05-29 | Paper |
| Steiner tree parameterized by multiway cut and even less | 2026-05-26 | Paper |
Kernelization for counting problems on graphs: preserving the number of minimum solutions
Journal of Graph Algorithms and Applications | 2026-04-22 | Paper |
| Bridge-depth characterizes which structural parameterizations of vertex cover admit a polynomial kernel | 2026-03-18 | Paper |
| Kernelization dichotomies for hitting subgraphs under structural parameterizations | 2026-01-14 | Paper |
Search-space reduction via essential vertices revisited: vertex multicut and cograph deletion
Journal of Computer and System Sciences | 2025-12-11 | Paper |
| Search-space reduction via essential vertices revisited: vertex multicut and cograph deletion | 2025-12-02 | Paper |
| Fixed-parameter tractable certified algorithms for covering and dominating in planar graphs and beyond | 2025-12-02 | Paper |
| Sunflowers meet sparsity: a linear-vertex kernel for weighted clique-packing on sparse graphs | 2025-09-24 | Paper |
| On the parameterized complexity of multiway near-separator | 2025-09-24 | Paper |
| Kernelization for counting problems on graphs: preserving the number of minimum solutions | 2025-09-24 | Paper |
| Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes | 2025-07-24 | Paper |
| Search-space reduction via essential vertices | 2025-06-19 | Paper |
Optimal polynomial-time compression for Boolean Max CSP
ACM Transactions on Computation Theory | 2025-02-25 | Paper |
Sparsification lower bounds for list H-coloring
ACM Transactions on Computation Theory | 2025-02-24 | Paper |
Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
SIAM Journal on Computing | 2025-01-23 | Paper |
| 5-approximation for \(\mathcal{H}\)-treewidth essentially as fast as \(\mathcal{H}\)-deletion parameterized by solution size | 2025-01-06 | Paper |
Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes
Journal of Computer and System Sciences | 2024-12-27 | Paper |
| Upward and orthogonal planarity are W[1]-hard parameterized by treewidth | 2024-10-14 | Paper |
Search-space reduction via essential vertices
SIAM Journal on Discrete Mathematics | 2024-09-17 | Paper |
Preprocessing to reduce the search space: antler structures for feedback vertex set
Journal of Computer and System Sciences | 2024-07-01 | Paper |
Kernelization for feedback vertex set via elimination distance to a forest
Discrete Applied Mathematics | 2024-02-14 | Paper |
| Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size | 2024-02-12 | Paper |
Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Sparsification lower bounds for list \(H\)-coloring
(available as arXiv preprint) | 2023-11-14 | Paper |
Vertex deletion parameterized by elimination distance and even less
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
| scientific article; zbMATH DE number 7759295 (Why is no real title available?) | 2023-11-02 | Paper |
Finding \(k\)-secluded trees faster
Journal of Computer and System Sciences | 2023-08-21 | Paper |
On the Hardness of Compressing Weights
(available as arXiv preprint) | 2023-08-08 | Paper |
Finding k-secluded trees faster
Graph-Theoretic Concepts in Computer Science | 2023-05-05 | Paper |
Kernelization for feedback vertex set via elimination distance to a forest
Graph-Theoretic Concepts in Computer Science | 2023-05-05 | Paper |
scientific article; zbMATH DE number 7651202 (Why is no real title available?)
(available as arXiv preprint) | 2023-02-07 | Paper |
Fine-grained parameterized complexity analysis of graph coloring problems
Discrete Applied Mathematics | 2023-01-11 | Paper |
\(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms
Journal of Computer and System Sciences | 2023-01-06 | Paper |
Bridge-depth characterizes which minor-closed structural parameterizations of vertex cover admit a polynomial kernel
SIAM Journal on Discrete Mathematics | 2022-11-15 | Paper |
Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size
Algorithmica | 2022-10-27 | Paper |
Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds
Treewidth, Kernels, and Algorithms | 2022-10-19 | Paper |
| A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs | 2022-07-18 | Paper |
FPT algorithms to compute the elimination distance to bipartite graphs and more
(available as arXiv preprint) | 2022-06-08 | Paper |
Preprocessing to reduce the search space: antler structures for feedback vertex set
(available as arXiv preprint) | 2022-06-08 | Paper |
Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP
(available as arXiv preprint) | 2022-05-11 | Paper |
Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
Journal of Computer and System Sciences | 2022-03-29 | Paper |
Fine-grained Complexity Analysis of Two Classic TSP Variants
ACM Transactions on Algorithms | 2022-02-08 | Paper |
A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
SIAM Journal on Discrete Mathematics | 2021-11-04 | Paper |
Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
(available as arXiv preprint) | 2021-08-04 | Paper |
Best-case and worst-case sparsifiability of Boolean CSPs
(available as arXiv preprint) | 2021-08-04 | Paper |
Lower bounds for dynamic programming on planar graphs of bounded cutwidth
(available as arXiv preprint) | 2021-08-04 | Paper |
| Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations. | 2021-08-04 | Paper |
A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
Journal of Computer and System Sciences | 2021-04-14 | Paper |
Lower bounds for dynamic programming on planar graphs of bounded cutwidth
Journal of Graph Algorithms and Applications | 2020-11-05 | Paper |
Polynomial kernels for hitting forbidden minors under structural parameterizations
Theoretical Computer Science | 2020-09-17 | Paper |
Polynomial kernels for hitting forbidden minors under structural parameterizations
Theoretical Computer Science | 2020-09-17 | Paper |
The evolutionary language game: an orthogonal approach
Journal of Theoretical Biology | 2020-09-03 | Paper |
Best-case and worst-case sparsifiability of Boolean CSPs
Algorithmica | 2020-08-12 | Paper |
| Optimal data reduction for graph coloring using low-degree polynomials | 2020-05-27 | Paper |
| Turing kernelization for finding long paths in graphs excluding a topological minor | 2020-05-27 | Paper |
Lower bounds for protrusion replacement by counting equivalence classes
Discrete Applied Mathematics | 2020-04-21 | Paper |
Hamiltonicity below Dirac's condition
(available as arXiv preprint) | 2020-02-24 | Paper |
A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F}\)-minor-free deletion
(available as arXiv preprint) | 2020-02-24 | Paper |
Optimal sparsification for some binary CSPs using low-degree polynomials
ACM Transactions on Computation Theory | 2019-12-16 | Paper |
Computing the chromatic number using graph decompositions via matrix rank
Theoretical Computer Science | 2019-10-18 | Paper |
Optimal data reduction for graph coloring using low-degree polynomials
Algorithmica | 2019-09-10 | Paper |
Turing kernelization for finding long paths in graph classes excluding a topological minor
Algorithmica | 2019-09-10 | Paper |
A near-optimal planarization algorithm
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Hamiltonicity below Dirac's condition
(available as arXiv preprint) | 2019-02-05 | Paper |
Uniform kernelization complexity of hitting forbidden minors
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Independent-set reconfiguration thresholds of hereditary graph classes
Discrete Applied Mathematics | 2018-10-26 | Paper |
Independent-set reconfiguration thresholds of hereditary graph classes
Discrete Applied Mathematics | 2018-10-26 | Paper |
Approximation and kernelization for chordal vertex deletion
SIAM Journal on Discrete Mathematics | 2018-09-12 | Paper |
Approximation and kernelization for chordal vertex deletion
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
| Independent-set reconfiguration thresholds of hereditary graph classes | 2018-04-19 | Paper |
Lower bounds for protrusion replacement by counting equivalence classes
(available as arXiv preprint) | 2018-04-10 | Paper |
Optimal sparsification for some binary CSPs using low-degree polynomials
(available as arXiv preprint) | 2018-03-21 | Paper |
| Constrained bipartite vertex cover: the easy kernel is essentially tight | 2018-01-24 | Paper |
Fine-grained complexity analysis of two classic TSP variants
(available as arXiv preprint) | 2017-12-19 | Paper |
A Locally Adaptive System for the Fusion of Objective Quality Measures
IEEE Transactions on Image Processing | 2017-11-20 | Paper |
Sparsification upper and lower bounds for graph problems and not-all-equal SAT
Algorithmica | 2017-10-10 | Paper |
Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
Sparsification upper and lower bounds for graphs problems and not-all-equal SAT
(available as arXiv preprint) | 2017-09-29 | Paper |
Fine-grained parameterized complexity analysis of graph coloring problems
Lecture Notes in Computer Science | 2017-07-21 | Paper |
On structural parameterizations of Hitting Set: hitting paths in graphs using 2-SAT
Journal of Graph Algorithms and Applications | 2017-04-05 | Paper |
Turing kernelization for finding long paths and cycles in restricted graph classes
Journal of Computer and System Sciences | 2016-12-28 | Paper |
FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders
ACM Transactions on Computation Theory | 2016-10-24 | Paper |
On structural parameterizations of \textsc{Hitting Set}: hitting paths in graphs using 2-SAT
Graph-Theoretic Concepts in Computer Science | 2016-10-21 | Paper |
A structural approach to kernels for ILPs: treewidth and total unimodularity
Algorithms - ESA 2015 | 2015-11-19 | Paper |
Uniform kernelization complexity of hitting forbidden minors
Lecture Notes in Computer Science | 2015-10-27 | Paper |
On sparsification for computing treewidth
Algorithmica | 2015-05-04 | Paper |
Turing kernelization for finding long paths and cycles in restricted graph classes
Lecture Notes in Computer Science | 2014-10-08 | Paper |
Kernelization Lower Bounds by Cross-Composition
SIAM Journal on Discrete Mathematics | 2014-06-19 | Paper |
Preprocessing for treewidth: a combinatorial analysis through kernelization
SIAM Journal on Discrete Mathematics | 2014-04-10 | Paper |
Data reduction for graph coloring problems
Information and Computation | 2014-01-16 | Paper |
Kernel bounds for path and cycle problems
Theoretical Computer Science | 2014-01-13 | Paper |
Parameterized complexity of vertex deletion into perfect graph classes
Theoretical Computer Science | 2014-01-13 | Paper |
Preprocessing subgraph and minor problems: when does a small vertex cover help?
Journal of Computer and System Sciences | 2013-12-13 | Paper |
On sparsification for computing treewidth
Lecture Notes in Computer Science | 2013-12-10 | Paper |
FPT is characterized by useful obstruction sets
Graph-Theoretic Concepts in Computer Science | 2013-12-06 | Paper |
Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
Theory of Computing Systems | 2013-10-21 | Paper |
Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
European Journal of Combinatorics | 2013-01-24 | Paper |
Preprocessing subgraph and minor problems: When does a small vertex cover help?
Parameterized and Exact Computation | 2013-01-07 | Paper |
Kernelization for maximum leaf spanning tree with positive vertex weights
Journal of Graph Algorithms and Applications | 2012-12-07 | Paper |
| Determining the winner of a Dodgson election is hard | 2012-08-29 | Paper |
Kernel bounds for structural parameterizations of pathwidth
Algorithm Theory – SWAT 2012 | 2012-08-14 | Paper |
Kernel bounds for path and cycle problems
Parameterized and Exact Computation | 2012-06-15 | Paper |
On polynomial kernels for structural parameterizations of odd cycle transversal
Parameterized and Exact Computation | 2012-06-15 | Paper |
| Cross-composition: a new technique for kernelization lower bounds | 2012-01-23 | Paper |
Cross-composition: a new technique for kernelization lower bounds
(available as arXiv preprint) | 2012-01-23 | Paper |
| Vertex cover kernelization revisited: upper and lower bounds for a refined parameter | 2012-01-23 | Paper |
Vertex cover kernelization revisited: upper and lower bounds for a refined parameter
(available as arXiv preprint) | 2012-01-23 | Paper |
Data reduction for graph coloring problems
Fundamentals of Computation Theory | 2011-08-19 | Paper |
Parameterized complexity of vertex deletion into perfect graph classes
Fundamentals of Computation Theory | 2011-08-19 | Paper |
Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
Automata, Languages and Programming | 2011-07-06 | Paper |
Polynomial kernels for hard problems on disk graphs
Lecture Notes in Computer Science | 2010-06-22 | Paper |
Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights
Lecture Notes in Computer Science | 2010-05-28 | Paper |
Kernelization Dichotomies for Hitting Subgraphs under Structural Parameterizations
(available as arXiv preprint) | N/A | Paper |
