research
∙
09/15/2023
On Induced Versions of Menger's Theorem on Sparse Graphs
Let A and B be sets of vertices in a graph G. Menger's theorem states th...
share
research
∙
08/29/2023
Lower Bound for Independence Covering in C_4-Free Graphs
An independent set in a graph G is a set S of pairwise non-adjacent vert...
research
∙
08/21/2023
Parameterized Complexity of Fair Bisection: FPT-Approximation meets Unbreakability
In the Minimum Bisection problem, input is a graph G and the goal is to ...
research
∙
08/18/2023
Counting and Sampling Labeled Chordal Graphs in Polynomial Time
We present the first polynomial-time algorithm to exactly compute the nu...
research
∙
08/11/2023
Lossy Kernelization for (Implicit) Hitting Set Problems
We re-visit the complexity of kernelization for the d-Hitting Set proble...
research
∙
08/09/2023
Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition
A graph G contains a graph H as an induced minor if H can be obtained fr...
research
∙
08/04/2023
Kernelization of Counting Problems
We introduce a new framework for the analysis of preprocessing routines ...
research
∙
08/03/2023
Meta-theorems for Parameterized Streaming Algorithms
The streaming model was introduced to parameterized complexity independe...
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
∙
04/26/2023
Hitting Subgraphs in Sparse Graphs and Geometric Intersection Graphs
We investigate a fundamental vertex-deletion problem called (Induced) Su...
research
∙
11/14/2022
An Improved Parameterized Algorithm for Treewidth
We give an algorithm that takes as input an n-vertex graph G and an inte...
research
∙
11/09/2022
Shortest Cycles With Monotone Submodular Costs
We introduce the following submodular generalization of the Shortest Cyc...
research
∙
11/04/2022
A Framework for Approximation Schemes on Disk Graphs
We initiate a systematic study of approximation schemes for fundamental ...
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
∙
03/30/2022
Wordle is NP-hard
Wordle is a single-player word-guessing game where the goal is to discov...
research
∙
03/15/2022
Point Separation and Obstacle Removal by Finding and Hitting Odd Cycles
Suppose we are given a pair of points s, t and a set S of n geometric ob...
research
∙
11/28/2021
Subexponential Parameterized Algorithms for Cut and Cycle Hitting Problems on H-Minor-Free Graphs
We design the first subexponential-time (parameterized) algorithms for s...
research
∙
06/09/2021
DynamiQ: Planning for Dynamics in Network Streaming Analytics Systems
The emergence of programmable data-plane targets has motivated a new hyb...
research
∙
05/19/2021
Diversity in Kemeny Rank Aggregation: A Parameterized Approach
In its most traditional setting, the main concern of optimization theory...
research
∙
04/20/2021
Elimination Distance to Topological-minor-free Graphs is FPT
In the literature on parameterized graph problems, there has been an inc...
research
∙
03/31/2021
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths
In the Disjoint Paths problem, the input is an undirected graph G on n v...
research
∙
11/29/2020
A Constant Factor Approximation for Navigating Through Connected Obstacles in the Plane
Given two points s and t in the plane and a set of obstacles defined by ...
research
∙
08/19/2020
Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
In the Disjoint Paths problem, the input consists of an n-vertex graph G...
research
∙
07/21/2020
Independent Set on C_≥ k-Free Graphs in Quasi-Polynomial Time
We give an algorithm that takes as input a graph G with weights on the v...
research
∙
07/17/2020
Dominated Minimal Separators are Tame (Nearly All Others are Feral)
A class F of graphs is called tame if there exists a constant k so that ...
research
∙
07/09/2020
Computing the Largest Bond and the Maximum Connected Cut of a Graph
The cut-set ∂(S) of a graph G=(V,E) is the set of edges that have one en...
research
∙
06/18/2020
On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
A graph operation that contracts edges is one of the fundamental operati...
research
∙
05/02/2020
Independent Set on P_k-Free Graphs in Quasi-Polynomial Time
We present an algorithm that takes as input a graph G with weights on th...
research
∙
04/30/2020
A Parameterized Approximation Scheme for Min k-Cut
In the Min k-Cut problem, input is an edge weighted graph G and an integ...
research
∙
04/24/2020
Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds
We prove that the Hadwiger number of an n-vertex graph G (the maximum si...
research
∙
03/17/2020
The Parameterized Complexity of Guarding Almost Convex Polygons
Art Gallery is a fundamental visibility problem in Computational Geometr...
research
∙
03/09/2020
b-Coloring Parameterized by Clique-Width
We provide a polynomial-time algorithm for b-Coloring on graphs of const...
research
∙
03/02/2020
ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs
We present an algorithm for the extensively studied Long Path and Long C...
research
∙
02/04/2020
Removing Connected Obstacles in the Plane is FPT
Given two points in the plane, a set of obstacles defined by closed curv...
research
∙
01/21/2020
Faster and Enhanced Inclusion-Minimal Cograph Completion
We design two incremental algorithms for computing an inclusion-minimal ...
research
∙
10/02/2019
Computing the largest bond of a graph
A bond of a graph G is an inclusion-wise minimal disconnecting set of G,...
research
∙
10/01/2019
On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets
In a reconfiguration version of an optimization problem Q the input is a...
research
∙
04/17/2019
A Brief Note on Single Source Fault Tolerant Reachability
Let G be a directed graph with n vertices and m edges, and let s ∈ V(G) ...
research
∙
04/05/2019
Reducing Topological Minor Containment to the Unique Linkage Theorem
In the Topological Minor Containment problem (TMC) problem two undirecte...
research
∙
03/04/2019
Decomposition of Map Graphs with Applications
Bidimensionality is the most common technique to design subexponential-t...
research
∙
02/23/2019
Slightly Superexponential Parameterized Problems
A central problem in parameterized algorithms is to obtain algorithms ...
research
∙
02/19/2019
Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals
Perturbed graphic matroids are binary matroids that can be obtained from...
research
∙
02/07/2019
Going Far From Degeneracy
An undirected graph G is d-degenerate if every subgraph of G has a verte...
research
∙
10/16/2018
Randomized contractions meet lean decompositions
The randomized contractions technique, introduced by Chitnis et al. in 2...
research
∙
09/22/2018
A 2-Approximation Algorithm for Feedback Vertex Set in Tournaments
A tournament is a directed graph T such that every pair of vertices is ...
research
∙
08/07/2018
The Parameterized Complexity of Finding Point Sets with Hereditary Properties
We consider problems where the input is a set of points in the plane and...
research
∙
07/18/2018
Approximation Schemes for Low-Rank Binary Matrix Approximation Problems
We provide a randomized linear time approximation scheme for a generic p...
research
∙
05/04/2018
A New Perspective on FO Model Checking of Dense Graph Classes
We study the first-order (FO) model checking problem of dense graphs, na...
research
∙
04/11/2018