18 papers
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 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…
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 points in the plane can be covered using lines. Line Cover is known to be NP-hard,…
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…