research
∙
08/29/2023
Parameterized and Approximation Algorithms for the Maximum Bimodal Subgraph Problem
A vertex of a plane digraph is bimodal if all its incoming edges (and he...
share
research
∙
08/29/2023
FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges
We study the α-Fixed Cardinality Graph Partitioning (α-FCGP) problem, th...
research
∙
08/14/2023
Kernelization for Spreading Points
We consider the following problem about dispersing points. Given a set o...
research
∙
07/14/2023
Turán's Theorem Through Algorithmic Lens
The fundamental theorem of Turán from Extremal Graph Theory determines t...
research
∙
07/01/2023
Kernelization for Finding Lineal Topologies (Depth-First Spanning Trees) with Many or Few Leaves
For a given graph G, a depth-first search (DFS) tree T of G is an r-root...
research
∙
06/02/2023
Parameterized Complexity of Broadcasting in Graphs
The task of the broadcast problem is, given a graph G and a source verte...
research
∙
05/03/2023
Approximating Long Cycle Above Dirac's Guarantee
Parameterization above (or below) a guarantee is a successful concept in...
research
∙
05/03/2023
Computing paths of large rank in planar frameworks deterministically
A framework consists of an undirected graph G and a matroid M whose elem...
research
∙
05/02/2023
Two-sets cut-uncut on planar graphs
We study the following Two-Sets Cut-Uncut problem on planar graphs. Ther...
research
∙
11/17/2022
(Re)packing Equal Disks into Rectangle
The problem of packing of equal disks (or circles) into a rectangle is a...
research
∙
11/09/2022
Shortest Cycles With Monotone Submodular Costs
We introduce the following submodular generalization of the Shortest Cyc...
research
∙
11/03/2022
Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
The disjoint paths logic, FOL+DP, is an extension of First-Order Logic (...
research
∙
08/14/2022
Exact Exponential Algorithms for Clustering Problems
In this paper we initiate a systematic study of exact algorithms for wel...
research
∙
07/20/2022
Computing Tree Decompositions with Small Independence Number
The independence number of a tree decomposition is the maximum of the in...
research
∙
07/15/2022
Fixed-Parameter Tractability of Maximum Colored Path and Beyond
We introduce a general method for obtaining fixed-parameter algorithms f...
research
∙
02/07/2022
Longest Cycle above Erdős-Gallai Bound
In 1959, Erdős and Gallai proved that every graph G with average vertex ...
research
∙
01/10/2022
Detours in Directed Graphs
We study two "above guarantee" versions of the classical Longest Path pr...
research
∙
12/13/2021
How to Find a Good Explanation for Clustering?
k-means and k-median clustering are powerful unsupervised machine learni...
research
∙
11/04/2021
A Compound Logic for Modification Problems: Big Kingdoms Fall from Within
We introduce a novel model-theoretic framework inspired from graph modif...
research
∙
07/20/2021
FPT Approximation for Fair Minimum-Load Clustering
In this paper, we consider the Minimum-Load k-Clustering/Facility Locati...
research
∙
07/15/2021
Lossy Kernelization of Same-Size Clustering
In this work, we study the k-median clustering problem with an additiona...
research
∙
07/14/2021
ETH Tight Algorithms for Geometric Intersection Graphs: Now in Polynomial Space
De Berg et al. in [SICOMP 2020] gave an algorithmic framework for subexp...
research
∙
06/07/2021
An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL
In general, a graph modification problem is defined by a graph modificat...
research
∙
05/08/2021
Parameterized Complexity of Feature Selection for Categorical Data Clustering
We develop new algorithmic methods with provable guarantees for feature ...
research
∙
04/16/2021
Parameterized Complexity of Categorical Clustering with Size Constraints
In the Categorical Clustering problem, we are given a set of vectors (ma...
research
∙
04/07/2021
Parameterized Complexity of Elimination Distance to First-Order Logic Properties
The elimination distance to some target graph property P is a general gr...
research
∙
02/26/2021
Can Romeo and Juliet Meet? Or Rendezvous Games with Adversaries on Graphs
We introduce the rendezvous game with adversaries. In this game, two pla...
research
∙
01/12/2021
Diverse Collections in Matroids and Graphs
We investigate the parameterized complexity of finding diverse sets of s...
research
∙
01/11/2021
Refined Notions of Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration
An enumeration kernel as defined by Creignou et al. [Theory Comput. Syst...
research
∙
12/29/2020
Present-Biased Optimization
This paper explores the behavior of present-biased agents, that is, agen...
research
∙
12/17/2020
Induced Disjoint Paths in AT-free Graphs
Paths P_1,…,P_k in a graph G=(V,E) are mutually induced if any two disti...
research
∙
11/23/2020
Recognizing Proper Tree-Graphs
We investigate the parameterized complexity of the recognition problem f...
research
∙
11/06/2020
Algorithmic Extensions of Dirac's Theorem
In 1952, Dirac proved the following theorem about long cycles in graphs ...
research
∙
10/19/2020
EPTAS for k-means Clustering of Affine Subspaces
We consider a generalization of the fundamental k-means clustering for d...
research
∙
10/12/2020
Graph Square Roots of Small Distance from Degree One Graphs
Given a graph class ℋ, the task of the ℋ-Square Root problem is to decid...
research
∙
09/09/2020
Diverse Pairs of Matchings
We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matching...
research
∙
06/24/2020
Kernelization of Whitney Switches
A fundamental theorem of Whitney from 1933 asserts that 2-connected grap...
research
∙
02/19/2020
Subexponential parameterized algorithms and kernelization on almost chordal graphs
We study the algorithmic properties of the graph class Chordal-ke, that ...
research
∙
01/19/2020
A survey of parameterized algorithms and the complexity of edge modification
The survey provides an overview of the developing area of parameterized ...
research
∙
07/12/2019
Planar Disjoint Paths in Linear Time
The Disjoint Paths problem asks whether a fixed number of pairs of termi...
research
∙
07/05/2019
Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
For a finite collection of graphs F, the F-TM-Deletion problem has as ...
research
∙
05/10/2019
Refined Complexity of PCA with Outliers
Principal component analysis (PCA) is one of the most fundamental proced...
research
∙
04/12/2019
Low-rank binary matrix approximation in column-sum norm
We consider ℓ_1-Rank-r Approximation over GF(2), where for a binary m× n...
research
∙
02/22/2019
Parameterized k-Clustering: The distance matters!
We consider the k-Clustering problem, which is for a given multiset of n...
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
∙
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/11/2018
On the Parameterized Complexity of Graph Modification to First-Order Logic Properties
We consider the problems of deciding whether an input graph can be modif...
research
∙
04/29/2018
Partial complementation of graphs
A partial complement of the graph G is a graph obtained from G by comple...
research
∙
03/26/2018