Petr A. Golovach

research

∙ 05/03/2023

Approximating Long Cycle Above Dirac's Guarantee

Parameterization above (or below) a guarantee is a successful concept in...

0 Fedor F. Fomin, et al. ∙

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...

0 Fedor V. Fomin, et al. ∙

research

∙ 05/02/2023

Two-sets cut-uncut on planar graphs

We study the following Two-Sets Cut-Uncut problem on planar graphs. Ther...

0 Matthias Bentert, et al. ∙

research

∙ 11/17/2022

(Re)packing Equal Disks into Rectangle

The problem of packing of equal disks (or circles) into a rectangle is a...

0 Fedor V. Fomin, et al. ∙

research

∙ 11/09/2022

Shortest Cycles With Monotone Submodular Costs

We introduce the following submodular generalization of the Shortest Cyc...

0 Fedor V. Fomin, et al. ∙

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 (...

0 Petr A. Golovach, et al. ∙

research

∙ 08/14/2022

Exact Exponential Algorithms for Clustering Problems

In this paper we initiate a systematic study of exact algorithms for wel...

0 Fedor V. Fomin, et al. ∙

research

∙ 07/20/2022

Computing Tree Decompositions with Small Independence Number

The independence number of a tree decomposition is the maximum of the in...

0 Clément Dallard, et al. ∙

research

∙ 07/15/2022

Fixed-Parameter Tractability of Maximum Colored Path and Beyond

We introduce a general method for obtaining fixed-parameter algorithms f...

0 Fedor V. Fomin, et al. ∙

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 ...

0 Fedor V. Fomin, et al. ∙

research

∙ 01/10/2022

Detours in Directed Graphs

We study two "above guarantee" versions of the classical Longest Path pr...

0 Fedor V. Fomin, et al. ∙

research

∙ 12/13/2021

How to Find a Good Explanation for Clustering?

k-means and k-median clustering are powerful unsupervised machine learni...

0 Sayan Bandyapadhyay, et al. ∙

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...

0 Fedor V. Fomin, et al. ∙

research

∙ 07/20/2021

FPT Approximation for Fair Minimum-Load Clustering

In this paper, we consider the Minimum-Load k-Clustering/Facility Locati...

0 Sayan Bandyapadhyay, et al. ∙

research

∙ 07/15/2021

Lossy Kernelization of Same-Size Clustering

In this work, we study the k-median clustering problem with an additiona...

0 Sayan Bandyapadhyay, et al. ∙

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...

0 Fedor V. Fomin, et al. ∙

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...

0 Fedor V. Fomin, et al. ∙

research

∙ 05/08/2021

Parameterized Complexity of Feature Selection for Categorical Data Clustering

We develop new algorithmic methods with provable guarantees for feature ...

0 Sayan Bandyapadhyay, et al. ∙

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...

0 Fedor V. Fomin, et al. ∙

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...

0 Fedor V. Fomin, et al. ∙

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...

0 Fedor V. Fomin, et al. ∙

research

∙ 01/12/2021

Diverse Collections in Matroids and Graphs

We investigate the parameterized complexity of finding diverse sets of s...

0 Fedor V. Fomin, et al. ∙

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...

0 Petr A. Golovach, et al. ∙

research

∙ 12/29/2020

Present-Biased Optimization

This paper explores the behavior of present-biased agents, that is, agen...

0 Fedor V. Fomin, et al. ∙

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...

0 Petr A. Golovach, et al. ∙

research

∙ 11/23/2020

Recognizing Proper Tree-Graphs

We investigate the parameterized complexity of the recognition problem f...

0 Steven Chaplick, et al. ∙

research

∙ 11/06/2020

Algorithmic Extensions of Dirac's Theorem

In 1952, Dirac proved the following theorem about long cycles in graphs ...

0 Fedor V. Fomin, et al. ∙

research

∙ 10/19/2020

EPTAS for k-means Clustering of Affine Subspaces

We consider a generalization of the fundamental k-means clustering for d...

0 Eduard Eiben, et al. ∙

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...

0 Petr A. Golovach, et al. ∙

research

∙ 09/09/2020

Diverse Pairs of Matchings

We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matching...

0 Fedor V. Fomin, et al. ∙

research

∙ 06/24/2020

Kernelization of Whitney Switches

A fundamental theorem of Whitney from 1933 asserts that 2-connected grap...

0 Fedor V. Fomin, et al. ∙

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 ...

0 Fedor V. Fomin, et al. ∙

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 ...

0 Christophe Crespelle, et al. ∙

research

∙ 07/12/2019

Planar Disjoint Paths in Linear Time

The Disjoint Paths problem asks whether a fixed number of pairs of termi...

0 Petr A. Golovach, et al. ∙

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 ...

0 Petr A. Golovach, et al. ∙

research

∙ 05/10/2019

Refined Complexity of PCA with Outliers

Principal component analysis (PCA) is one of the most fundamental proced...

0 Fedor V. Fomin, et al. ∙

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...

0 Fedor V. Fomin, et al. ∙

research

∙ 02/22/2019

Parameterized k-Clustering: The distance matters!

We consider the k-Clustering problem, which is for a given multiset of n...

0 Fedor V. Fomin, et al. ∙

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...

0 Fedor V. Fomin, et al. ∙

research

∙ 02/07/2019

Going Far From Degeneracy

An undirected graph G is d-degenerate if every subgraph of G has a verte...

0 Fedor V. Fomin, et al. ∙

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...

0 Fedor V. Fomin, et al. ∙

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...

0 Fedor V. Fomin, et al. ∙

research

∙ 04/29/2018

Partial complementation of graphs

A partial complement of the graph G is a graph obtained from G by comple...

0 Fedor V. Fomin, et al. ∙

research

∙ 03/26/2018

Clustering to Given Connectivities

We define a general variant of the graph clustering problem where the cr...

0 Petr A. Golovach, et al. ∙

research

∙ 03/16/2018

Parameterized Low-Rank Binary Matrix Approximation

We provide a number of algorithmic results for the following family of p...

0 Fedor V. Fomin, et al. ∙

research

∙ 02/28/2018

Parameterized Aspects of Strong Subgraph Closure

Motivated by the role of triadic closures in social networks, and the im...

0 Petr A. Golovach, et al. ∙

research

∙ 10/30/2017

Finding Connected Secluded Subgraphs

Problems related to finding induced subgraphs satisfying given propertie...

0 Petr A. Golovach, et al. ∙

research

∙ 10/06/2017

Covering vectors by spaces: Regular matroids

Seymour's decomposition theorem for regular matroids is a fundamental re...

0 Fedor V. Fomin, et al. ∙

research

∙ 09/27/2017

On the tractability of optimization problems on H-graphs

For a graph H, a graph G is an H-graph if it is an intersection graph of...

0 Fedor V. Fomin, et al. ∙

Petr A. Golovach

Featured Co-authors