Fedor V. Fomin

Packing Diverse Shortest Cycles

Akanksha Agrawal, Fedor V. Fomin, Petr A. Golovach +3

Bentert, Fomin, Golovach, Korhonen, Lochet, Panolan, Ramanujan, Saurabh, and Simonov (SODA 2025) initiated the parameterized study of Edge-Disjoint Shortest Cycle Packing: given a…

Ultrametric Violation Distance: Polynomial Kernel and FPT Algorithm

Fedor V. Fomin, Petr A. Golovach, Yash Hiren More

In the Ultrametric Violation Distance problem, we are given a set of distances between $n$ points, and the goal is to modify the minimum number of distances so that the resulting s…

An FPT Algorithm for Diverse Minimum s-t Cuts

Krishnan Dehaleesan, Pål Grønås Drange, Fedor V. Fomin +2

We study the problem of finding a family of diverse minimum edge s-t cuts in a directed weighted graph G. Given integers k and d, the task is to decide whether G contains k minimum…

Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study

Tian Bai, Fedor V. Fomin, Petr A. Golovach +2

Rank aggregation seeks a representative permutation for a collection of rankings and plays a central role in areas such as social choice, information retrieval, and computational b…

A Framework for Parameterized Subexponential-Subcubic-Time Algorithms for Weighted Problems in Planar Graphs

Matthias Bentert, Fedor V. Fomin, Petr A. Golovach

Many problems are known to be solvable in subexponential parameterized time when the input graph is planar. The bidimensionality framework of Demaine, Fomin, Hajiaghay, and Thiliko…

Algorithms for Euclidean Distance Matrix Completion: Exploiting Proximity to Triviality

Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan +1

In the d-Euclidean Distance Matrix Completion (d-EDMC) problem, one aims to determine whether a given partial matrix of pairwise distances can be extended to a full Euclidean dista…

cs.CG2025

Line Cover and Related Problems

Matthias Bentert, Fedor v. Fomin, Petr A. Golovach +4

We study extensions of the classic \emph{Line Cover} problem, which asks whether a set of $n$ points in the plane can be covered using $k$ lines. Line Cover is known to be NP-hard,…

Discounted Cuts: A Stackelberg Approach to Network Disruption

Pål Grønås Drange, Fedor V. Fomin, Petr Golovach +1

We study a Stackelberg variant of the classical Most Vital Links problem, modeled as a one-round adversarial game between an attacker and a defender. The attacker strategically rem…

Tight Parameterized (In)tractability of Layered Crossing Minimization: Subexponential Algorithms and Kernelization

Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar +2

The starting point of our work is a decade-old open question concerning the subexponential parameterized complexity of \textsc{2-Layer Crossing Minimization}. In this problem, the…

H-Planarity and Parametric Extensions: when Modulators Act Globally

Fedor V. Fomin, Petr A. Golovach, Laure Morelle +1

We introduce a series of graph decompositions based on the modulator/target scheme of modification problems that enable several algorithmic applications that parametrically extend…

Fault-Tolerant Matroid Bases

Matthias Bentert, Fedor V. Fomin, Petr A. Golovach +1

We investigate the problem of constructing fault-tolerant bases in matroids. Given a matroid M and a redundancy parameter k, a k-fault-tolerant basis is a minimum-size set of eleme…

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…

When does FTP become FPT?

Matthias Bentert, Fedor V. Fomin, Petr A. Golovach +1

In the problem Fault-Tolerant Path (FTP), we are given an edge-weighted directed graph G = (V, E), a subset U \subseteq E of vulnerable edges, two vertices s, t \in V, and integers…

cs.CG2025

When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations

Matthias Bentert, Fedor V. Fomin, Petr A. Golovach +2

Distance geometry explores the properties of distance spaces that can be exactly represented as the pairwise Euclidean distances between points in $R^{d}$ ( $d \geq 1$ ), or e…

Planar Network Diversion

Matthias Bentert, Pål Grønås Drange, Fedor V. Fomin +1

Network Diversion is a graph problem that has been extensively studied in both the network-analysis and operations-research communities as a measure of how robust a network is agai…

Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems

Matthias Bentert, Fedor V. Fomin, Tanmay Inamdar +1

In this paper, we begin the exploration of vertex-ordering problems through the lens of exponential-time approximation algorithms. In particular, we ask the following question: Can…

cs.DM2025

Multivariate Exploration of Metric Dilation

Aritra Banik, Fedor V. Fomin, Petr A. Golovach +3

Let $G$ be a weighted graph embedded in a metric space $(M, d_{M})$ . The vertices of $G$ correspond to the points in $M$ , with the weight of each edge $uv$ being the distance $d_M…

cs.CG2024

Parameterized Geometric Graph Modification with Disk Scaling

Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar +2

The parameterized analysis of graph modification problems represents the most extensively studied area within Parameterized Complexity. Given a graph $G$ and an integer $k\in\mathb…

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…

Fixed-Parameter Tractability of Hedge Cut

Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen +2

In the Hedge Cut problem, the edges of a graph are partitioned into groups called hedges, and the question is what is the minimum number of hedges to delete to disconnect the graph…

cs.GT2024

How to guide a present-biased agent through prescribed tasks?

Tatiana Belova, Yuriy Dementiev, Fedor V. Fomin +2

The present bias is a well-documented behavioral trait that significantly influences human decision-making, with present-biased agents often prioritizing immediate rewards over lon…

The Parameterized Complexity Landscape of Two-Sets Cut-Uncut

Matthias Bentert, Fedor V. Fomin, Fanny Hauser +1

In Two-Sets Cut-Uncut, we are given an undirected graph $G = (V, E)$ and two terminal sets $S$ and $T$ . The task is to find a minimum cut $C$ in $G$ (if there is any) separating $S$ f…