6 citations · 12 across the 18 of their papers we have counts for
25 papers · 1 filter
Edge Clique Partition and Cover Beyond Independence
Fedor V. Fomin, Petr A. Golovach, Danil Sagunov +1
Covering and partitioning the edges of a graph into cliques are classical problems at the intersection of combinatorial optimization and graph theory, having been studied through a…
Packing Short Cycles
Matthias Bentert, Fedor V. Fomin, Petr A. Golovach +6
Cycle packing is a fundamental problem in optimization, graph theory, and algorithms. Motivated by recent advancements in finding vertex-disjoint paths between a specified set of v…
Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball Graphs
Tomohiro Koana, Nidhi Purohit, Kirill Simonov
In Clique Cover, given a graph and an integer , the task is to partition the vertices of into cliques. Clique Cover on unit ball graphs has a natural interpretation…
Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
Fedor V. Fomin, Petr A. Golovach, Nikola Jedličková +3
The classic theorem of Gallai and Milgram (1960) generalizes several fundamental results in Graph Theory, such as Dilworth's theorem on posets and Kőnig's theorem on matchings in b…
Tree Containment Above Minimum Degree is FPT
Fedor V. Fomin, Petr A. Golovach, Danil Sagunov +1
According to the classic Chv{á}tal's Lemma from 1977, a graph of minimum degree contains every tree on vertices. Our main result is the following algorithmic "exten…
Consistency-Checking Problems: A Gateway to Parameterized Sample Complexity
Robert Ganian, Liana Khazaliya, Kirill Simonov
Recently, Brand, Ganian and Simonov introduced a parameterized refinement of the classical PAC-learning sample complexity framework. A crucial outcome of their investigation is tha…
Turán's Theorem Through Algorithmic Lens
Fedor V. Fomin, Petr A. Golovach, Danil Sagunov +1
The fundamental theorem of Turán from Extremal Graph Theory determines the exact bound on the number of edges in an -vertex graph that does not contain a clique of size…
Approximating Long Cycle Above Dirac's Guarantee
Fedor F. Fomin, Petr A. Golovach, Danil Sagunov +1
Parameterization above (or below) a guarantee is a successful concept in parameterized algorithms. The idea is that many computational problems admit ``natural'' guarantees bringin…
Proportionally Fair Matching with Multiple Groups
Sayan Bandyapadhyay, Fedor V. Fomin, Tanmay Inamdar +1
The study of fair algorithms has become mainstream in machine learning and artificial intelligence due to its increasing demand in dealing with biases and discrimination. Along thi…
Testing Upward Planarity of Partial -Trees
Steven Chaplick, Emilio Di Giacomo, Fabrizio Frati +3
We present an -time algorithm to test whether an -vertex directed partial -tree is upward planar. This result improves upon the previously best known algorithm, which…
Fixed-Parameter Tractability of Maximum Colored Path and Beyond
Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen +2
We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the…
Weighted Model Counting with Twin-Width
Robert Ganian, Filip Pokrývka, André Schidler +2
Bonnet et al. (FOCS 2020) introduced the graph invariant twin-width and showed that many NP-hard problems are tractable for graphs of bounded twin-width, generalizing similar resul…
Longest Cycle above Erdős-Gallai Bound
Fedor V. Fomin, Petr A. Golovach, Danil Sagunov +1
In 1959, Erdős and Gallai proved that every graph G with average vertex degree ad(G)\geq 2 contains a cycle of length at least ad(G). We provide an algorithm that for k\geq 0 in ti…
Detours in Directed Graphs
Fedor V. Fomin, Petr A. Golovach, William Lochet +3
We study two "above guarantee" versions of the classical Longest Path problem on undirected and directed graphs and obtain the following results. In the first variant of Longest Pa…
How to Find a Good Explanation for Clustering?
Sayan Bandyapadhyay, Fedor V. Fomin, Petr A. Golovach +3
-means and -median clustering are powerful unsupervised machine learning techniques. However, due to complicated dependences on all the features, it is challenging to interpr…
Lossy Kernelization of Same-Size Clustering
Sayan Bandyapadhyay, Fedor V. Fomin, Petr A. Golovach +2
In this work, we study the -median clustering problem with an additional equal-size constraint on the clusters, from the perspective of parameterized preprocessing. Our main res…
Parameterized Complexity of Feature Selection for Categorical Data Clustering
Sayan Bandyapadhyay, Fedor V. Fomin, Petr A. Golovach +1
We develop new algorithmic methods with provable guarantees for feature selection in regard to categorical data clustering. While feature selection is one of the most common approa…
Algorithmic Extensions of Dirac's Theorem
Fedor V. Fomin, Petr A. Golovach, Danil Sagunov +1
In 1952, Dirac proved the following theorem about long cycles in graphs with large minimum vertex degrees: Every -vertex -connected graph with minimum vertex degree $δ\ge…
EPTAS for -means Clustering of Affine Subspaces
Eduard Eiben, Fedor V. Fomin, Petr A. Golovach +3
We consider a generalization of the fundamental -means clustering for data with incomplete or corrupted entries. When data objects are represented by points in , a…
On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications
Sayan Bandyapadhyay, Fedor V. Fomin, Kirill Simonov
Fair clustering is a constrained variant of clustering where the goal is to partition a set of colored points, such that the fraction of points of any color in every cluster is mor…
Manipulating Districts to Win Elections: Fine-Grained Complexity
Eduard Eiben, Fedor V. Fomin, Fahad Panolan +1
Gerrymandering is a practice of manipulating district boundaries and locations in order to achieve a political advantage for a particular party. Lewenberg, Lev, and Rosenschein [AA…
Building large k-cores from sparse graphs
Fedor V. Fomin, Danil Sagunov, Kirill Simonov
A popular model to measure network stability is the -core, that is the maximal induced subgraph in which every vertex has degree at least . For example, -cores are commonl…
Refined Complexity of PCA with Outliers
Fedor V. Fomin, Petr A. Golovach, Fahad Panolan +1
Principal component analysis (PCA) is one of the most fundamental procedures in exploratory data analysis and is the basic step in applications ranging from quantitative finance an…
Low-rank binary matrix approximation in column-sum norm
Fedor V. Fomin, Petr A. Golovach, Fahad Panolan +1
We consider -Rank- Approximation over GF(2), where for a binary matrix and a positive integer , one seeks a binary matrix of rank at m…