research
∙
07/14/2023
Sparse induced subgraphs in P_6-free graphs
We prove that a number of computational problems that ask for the larges...
share
research
∙
05/25/2023
Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
We show that the Maximum Weight Independent Set problem (MWIS) can be so...
research
∙
05/23/2023
Parameterized Complexity Classification for Interval Constraints
Constraint satisfaction problems form a nicely behaved class of problems...
research
∙
04/14/2023
Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1
We prove that there is a randomized polynomial-time algorithm that given...
research
∙
02/06/2023
Tight bound on treedepth in terms of pathwidth and longest path
We show that every graph with pathwidth strictly less than a that contai...
research
∙
10/26/2022
Fixed-parameter tractability of Graph Isomorphism in graphs with an excluded minor
We prove that Graph Isomorphism and Canonization in graphs excluding a f...
research
∙
10/26/2022
Highly unbreakable graph with a fixed excluded minor are almost rigid
A set X ⊆ V(G) in a graph G is (q,k)-unbreakable if every separation (A,...
research
∙
09/13/2022
Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of P_4
An oriented graph is a digraph that does not contain a directed cycle of...
research
∙
08/31/2022
On weighted graph separation problems and flow-augmentation
One of the first application of the recently introduced technique of flo...
research
∙
07/15/2022
A tight quasi-polynomial bound for Global Label Min-Cut
We study a generalization of the classic Global Min-Cut problem, called ...
research
∙
07/15/2022
Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
We show fixed-parameter tractability of the Directed Multicut problem wi...
research
∙
07/15/2022
Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
We study the parameterized problem of satisfying “almost all” constraint...
research
∙
06/23/2022
On the Complexity of Problems on Tree-structured Graphs
In this paper, we introduce a new class of parameterized problems, which...
research
∙
05/16/2022
The Influence of Dimensions on the Complexity of Computing Decision Trees
A decision tree recursively splits a feature space ℝ^d and then assigns ...
research
∙
05/02/2022
Taming graphs with no large creatures and skinny ladders
We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: i...
research
∙
03/09/2022
Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
We revisit recent developments for the Maximum Weight Independent Set pr...
research
∙
01/24/2022
Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs
Twin-width is a newly introduced graph width parameter that aims at gene...
research
∙
11/05/2021
Directed flow-augmentation
We show a flow-augmentation algorithm in directed graphs: There exists a...
research
∙
06/30/2021
Close relatives (of Feedback Vertex Set), revisited
At IPEC 2020, Bergougnoux, Bonnet, Brettell, and Kwon showed that a numb...
research
∙
03/15/2021
Constant congestion brambles in directed graphs
The Directed Grid Theorem, stating that there is a function f such that ...
research
∙
02/19/2021
Hardness of Metric Dimension in Graphs of Constant Treewidth
The Metric Dimension problem asks for a minimum-sized resolving set in a...
research
∙
09/28/2020
Quasi-polynomial-time algorithm for Independent Set in P_t-free graphs via shrinking the space of induced paths
In a recent breakthrough work, Gartland and Lokshtanov [FOCS 2020] showe...
research
∙
09/27/2020
The Complexity of Connectivity Problems in Forbidden-Transition Graphs and Edge-Colored Graphs
The notion of forbidden-transition graphs allows for a robust generaliza...
research
∙
08/05/2020
Constant Congestion Brambles
A bramble in an undirected graph G is a family of connected subgraphs of...
research
∙
07/17/2020
Solving hard cut problems via flow-augmentation
We present a new technique for designing FPT algorithms for graph cut pr...
research
∙
06/07/2020
Two lower bounds for p-centered colorings
Given a graph G and an integer p, a coloring f : V(G) →ℕ is p-centered i...
research
∙
05/31/2020
Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
We present a data structure that in a dynamic graph of treedepth at most...
research
∙
03/27/2020
Covering minimal separators and potential maximal cliques in P_t-free graphs
A graph is called P_t-free if it does not contain a t-vertex path as an ...
research
∙
03/11/2020
Induced subgraphs of bounded treewidth and the container method
A hole in a graph is an induced cycle of length at least 4. A hole is lo...
research
∙
03/05/2020
Optimal Discretization is Fixed-parameter Tractable
Given two disjoint sets W_1 and W_2 of points in the plane, the Optimal ...
research
∙
02/04/2020
A Double Exponential Lower Bound for the Distinct Vectors Problem
In the (binary) Distinct Vectors problem we are given a binary matrix A ...
research
∙
12/03/2019
Jones' Conjecture in subcubic graphs
We confirm Jones' Conjecture for subcubic graphs. Namely, if a subcubic ...
research
∙
10/18/2019
Cluster Editing parameterized above the size of a modification-disjoint P_3 packing is para-NP-hard
Given a graph G=(V,E) and an integer k, the Cluster Editing problem asks...
research
∙
07/10/2019
Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
In the Maximum Independent Set problem we are asked to find a set of pai...
research
∙
07/04/2019
Packing directed circuits quarter-integrally
The celebrated Erdős-Pósa theorem states that every undirected graph tha...
research
∙
05/02/2019
Efficient approximation schemes for uniform-cost clustering problems in planar graphs
We consider the k-Median problem on planar graphs: given an edge-weighte...
research
∙
04/30/2019
Improved bounds for the excluded-minor approximation of treedepth
Treedepth, a more restrictive graph width parameter than treewidth and p...
research
∙
04/24/2019
A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs
We consider the classic Facility Location problem on planar graphs (non-...
research
∙
03/12/2019
On the Maximum Weight Independent Set Problem in graphs without induced cycles of length at least five
A hole in a graph is an induced cycle of length at least 4, and an antih...
research
∙
11/19/2018
Experimental Evaluation of Parameterized Algorithms for Graph Separation Problems: Half-Integral Relaxations and Matroid-based Kernelization
In the recent years we have witnessed a rapid development of new algorit...
research
∙
10/16/2018
Randomized contractions meet lean decompositions
The randomized contractions technique, introduced by Chitnis et al. in 2...
research
∙
10/16/2018
Multi-budgeted directed cuts
We study multi-budgeted variants of the classic minimum cut problem and ...
research
∙
10/02/2018
A deterministic polynomial kernel for Odd Cycle Transversal and Vertex Multiway Cut in planar graphs
We show that Odd Cycle Transversal and Vertex Multiway Cut admit determi...
research
∙
10/01/2018
Caterpillars in Erdős-Hajnal
Let T be a tree such that all its vertices of degree more than two lie o...
research
∙
04/11/2018
Subexponential-time Algorithms for Maximum Independent Set in P_t-free and Broom-free Graphs
In algorithmic graph theory, a classic open question is to determine the...
research
∙
03/02/2018
An improved FPT algorithm for Independent Feedback Vertex Set
We study the Independent Feedback Vertex Set problem - a variant of the ...
research
∙
03/02/2018
Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation
The notion of treewidth, introduced by Robertson and Seymour in their se...
research
∙
03/02/2018
Experimental Evaluation of Parameterized Algorithms for Feedback Vertex Set
Feedback Vertex Set is a classic combinatorial optimization problem that...
research
∙
02/27/2018
Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness
The notions of bounded expansion and nowhere denseness not only offer ro...
research
∙
10/24/2017