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
∙
03/14/2023
Coloring and Recognizing Directed Interval Graphs
A mixed interval graph is an interval graph that has, for every pair of ...
research
∙
10/19/2022
List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
The goal of this paper is to investigate a family of optimization proble...
research
∙
10/12/2022
Exact and approximation algorithms for sensor placement against DDoS attacks
In a DDoS attack (Distributed Denial of Service), an attacker gains cont...
research
∙
09/25/2022
Tree decompositions with bounded independence number: beyond independent sets
We continue the study of graph classes in which the treewidth can only b...
research
∙
05/26/2022
Computing homomorphisms in hereditary graph classes: the peculiar case of the 5-wheel and graphs with no long claws
For graphs G and H, an H-coloring of G is an edge-preserving mapping fro...
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
∙
04/08/2022
List covering of regular multigraphs
A graph covering projection, also known as a locally bijective homomorph...
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
∙
02/25/2022
List Locally Surjective Homomorphisms in Hereditary Graph Classes
A locally surjective homomorphism from a graph G to a graph H is an edge...
research
∙
02/17/2022
Computing list homomorphisms in geometric intersection graphs
A homomorphism from a graph G to a graph H is an edge-preserving mapping...
research
∙
01/02/2022
Classifying Subset Feedback Vertex Set for H-Free Graphs
In the Feedback Vertex Set problem, we aim to find a small set S of vert...
research
∙
10/28/2021
EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
A (unit) disk graph is the intersection graph of closed (unit) disks in ...
research
∙
07/14/2021
Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
The goal of this work is to give precise bounds on the counting complexi...
research
∙
07/12/2021
Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws
For graphs G and H, we say that G is H-free if it does not contain H as ...
research
∙
05/06/2021
Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs
We prove new complexity results for Feedback Vertex Set and Even Cycle T...
research
∙
04/28/2021
Faster 3-coloring of small-diameter graphs
We study the 3-Coloring problem in graphs with small diameter. In 2013, ...
research
∙
03/15/2021
Constant congestion brambles in directed graphs
The Directed Grid Theorem, stating that there is a function f such that ...
research
∙
10/07/2020
Complexity of the list homomorphism problem in hereditary graph classes
A homomorphism from a graph G to a graph H is an edge-preserving mapping...
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/24/2020
Fine-grained complexity of the list homomorphism problem: feedback vertex set and cutwidth
For graphs G,H, a homomorphism from G to H is an edge-preserving mapping...
research
∙
09/17/2020
Sparsification Lower Bounds for List H-Coloring
We investigate the List H-Coloring problem, the generalization of graph ...
research
∙
06/19/2020
Full complexity classification of the list homomorphism problem for bounded-treewidth graphs
A homomorphism from a graph G to a graph H is an edge-preserving mapping...
research
∙
06/18/2020
Parameterized Inapproximability of Independent Set in H-Free Graphs
We study the Independent Set (IS) problem in H-free graphs, i.e., graphs...
research
∙
06/05/2020
Clique-Width: Harnessing the Power of Atoms
Many NP-complete graph problems are polynomially solvable on graph class...
research
∙
05/04/2020
Complexity of C_k-coloring in hereditary classes of graphs
For a graph F, a graph G is F-free if it does not contain an induced sub...
research
∙
04/20/2020
Finding large H-colorable subgraphs in hereditary graph classes
We study the Max Partial H-Coloring problem: given a graph G, find the l...
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
∙
10/02/2019
Subexponential-time algorithms for finding large induced sparse subgraphs
Let C and D be hereditary graph classes. Consider the following problem:...
research
∙
08/22/2019
Representing Graphs and Hypergraphs by Touching Polygons in 3D
Contact representations of graphs have a long history. Most research h...
research
∙
08/01/2019
On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest
A graph is H-free if it contains no induced subgraph isomorphic to H. We...
research
∙
07/04/2019
Packing directed circuits quarter-integrally
The celebrated Erdős-Pósa theorem states that every undirected graph tha...
research
∙
06/19/2019
Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs
For graphs G and H, a homomorphism from G to H is an edge-preserving map...
research
∙
09/25/2018
Subexponential algorithms for variants of homomorphism problem in string graphs
We consider the complexity of finding weighted homomorphisms from inters...
research
∙
04/27/2018
Intersecting edge distinguishing colorings of hypergraphs
An edge labeling of a graph distinguishes neighbors by sets (multisets, ...
research
∙
02/15/2018
Finding small-width connected path decompositions in polynomial time
A connected path decomposition of a simple graph G is a path decompositi...
research
∙
12/24/2017
Optimality Program in Segment and String Graphs
Planar graphs are known to allow subexponential algorithms running in ti...
research
∙
12/14/2017
∀∃R-completeness and area-universality
In the study of geometric problems, the complexity class ∃R turned out t...
research
∙
12/13/2017
QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs
A (unit) disk graph is the intersection graph of closed (unit) disks in ...
research
∙
11/14/2017
On edge intersection graphs of paths with 2 bends
An EPG-representation of a graph G is a collection of paths in a plane s...
research
∙
11/14/2017
Sequences of radius k for complete bipartite graphs
A k-radius sequence for a graph G is a sequence of vertices of G (typica...
research
∙
10/31/2017