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
∙
08/11/2023
Lossy Kernelization for (Implicit) Hitting Set Problems
We re-visit the complexity of kernelization for the d-Hitting Set proble...
research
∙
07/14/2023
Turán's Theorem Through Algorithmic Lens
The fundamental theorem of Turán from Extremal Graph Theory determines t...
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
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
∙
03/02/2023
Coresets for Clustering in Geometric Intersection Graphs
Designing coresets–small-space sketches of the data preserving cost of t...
research
∙
02/20/2023
Kernelizing Temporal Exploration Problems
We study the kernelization of exploration problems on temporal graphs. A...
research
∙
01/10/2023
Proportionally Fair Matching with Multiple Groups
The study of fair algorithms has become mainstream in machine learning a...
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
∙
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
∙
12/06/2021
Inconsistent Planning: When in doubt, toss a coin!
One of the most widespread human behavioral biases is the present bias –...
research
∙
11/05/2021
Fast FPT-Approximation of Branchwidth
Branchwidth determines how graphs, and more generally, arbitrary connect...
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
∙
12/29/2020
Present-Biased Optimization
This paper explores the behavior of present-biased agents, that is, agen...
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
∙
09/09/2020
Diverse Pairs of Matchings
We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matching...
research
∙
07/20/2020
On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications
Fair clustering is a constrained variant of clustering where the goal is...
research
∙
06/24/2020
Kernelization of Whitney Switches
A fundamental theorem of Whitney from 1933 asserts that 2-connected grap...
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/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/19/2020
Subexponential parameterized algorithms and kernelization on almost chordal graphs
We study the algorithmic properties of the graph class Chordal-ke, that ...
research
∙
02/18/2020
Building large k-cores from sparse graphs
A popular model to measure network stability is the k-core, that is the ...
research
∙
02/18/2020
Manipulating Districts to Win Elections: Fine-Grained Complexity
Gerrymandering is a practice of manipulating district boundaries and loc...
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
∙
11/18/2019
Time-inconsistent Planning: Simple Motivation Is Hard to Find
With the introduction of the graph-theoretic time-inconsistent planning ...
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
∙
04/05/2019
Knot Diagrams of Treewidth Two
In this paper, we study knot diagrams for which the underlying graph has...
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/22/2019