Fedor V. Fomin

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

0 Walter Didimo, et al. ∙

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

0 Fedor V. Fomin, et al. ∙

research

∙ 08/14/2023

Kernelization for Spreading Points

We consider the following problem about dispersing points. Given a set o...

0 Fedor V. Fomin, et al. ∙

research

∙ 08/11/2023

Lossy Kernelization for (Implicit) Hitting Set Problems

We re-visit the complexity of kernelization for the d-Hitting Set proble...

0 Fedor V. Fomin, et al. ∙

research

∙ 07/14/2023

Turán's Theorem Through Algorithmic Lens

The fundamental theorem of Turán from Extremal Graph Theory determines t...

0 Fedor V. Fomin, et al. ∙

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

0 Fedor V. 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

∙ 03/02/2023

Coresets for Clustering in Geometric Intersection Graphs

Designing coresets–small-space sketches of the data preserving cost of t...

0 Sayan Bandyapadhyay, et al. ∙

research

∙ 02/20/2023

Kernelizing Temporal Exploration Problems

We study the kernelization of exploration problems on temporal graphs. A...

0 Emmanuel Arrighi, et al. ∙

research

∙ 01/10/2023

Proportionally Fair Matching with Multiple Groups

The study of fair algorithms has become mainstream in machine learning a...

0 Sayan Bandyapadhyay, 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

∙ 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

∙ 12/06/2021

Inconsistent Planning: When in doubt, toss a coin!

One of the most widespread human behavioral biases is the present bias –...

0 Yuriy Dementiev, et al. ∙

research

∙ 11/05/2021

Fast FPT-Approximation of Branchwidth

Branchwidth determines how graphs, and more generally, arbitrary connect...

0 Fedor V. Fomin, 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

∙ 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

∙ 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

∙ 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

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

0 Sayan Bandyapadhyay, 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

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

0 Fedor V. Fomin, et al. ∙

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

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

∙ 02/18/2020

Building large k-cores from sparse graphs

A popular model to measure network stability is the k-core, that is the ...

0 Fedor V. Fomin, et al. ∙

research

∙ 02/18/2020

Manipulating Districts to Win Elections: Fine-Grained Complexity

Gerrymandering is a practice of manipulating district boundaries and loc...

0 Eduard Eiben, 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

∙ 11/18/2019

Time-inconsistent Planning: Simple Motivation Is Hard to Find

With the introduction of the graph-theoretic time-inconsistent planning ...

0 Fedor V. Fomin, 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

∙ 04/05/2019

Knot Diagrams of Treewidth Two

In this paper, we study knot diagrams for which the underlying graph has...

0 Hans L. Bodlaender, et al. ∙

research

∙ 04/05/2019

Reducing Topological Minor Containment to the Unique Linkage Theorem

In the Topological Minor Containment problem (TMC) problem two undirecte...

0 Fedor V. Fomin, et al. ∙

research

∙ 03/04/2019

Decomposition of Map Graphs with Applications

Bidimensionality is the most common technique to design subexponential-t...

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

Fedor V. Fomin

Featured Co-authors