research
∙
05/23/2023
Parameterized Complexity Classification for Interval Constraints
Constraint satisfaction problems form a nicely behaved class of problems...
share
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
∙
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
∙
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
∙
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
∙
08/05/2020
Constant Congestion Brambles
A bramble in an undirected graph G is a family of connected subgraphs of...
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
∙
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
∙
10/16/2018
Multi-budgeted directed cuts
We study multi-budgeted variants of the classic minimum cut problem and ...
research
∙
04/11/2018
