Fedor V. Fomin
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Recognitions
Fedor V. Fomin has a total of 290 co-authors. Here are the top co-authors by number of shared publications:
- Petr A. Golovach
Department of Informatics, University of Bergen
114 shared publications Saket Saurabh
Institute of Mathematical Sciences, Chennai 600 113, India, and Department of Informatics, University of Bergen, N-5020 Bergen, Norway
76 shared publicationsDaniel Lokshtanov
Department of Computer Science, University of California, Santa Barbara, CA 93106-5110 USA
54 shared publications- Saket Saurabh
Institute of Mathematical Sciences
49 shared publications Dimitrios M. Thilikos
LIRMM, Univ Montpellier, CNRS, Montpellier, France
38 shared publications- Michał Pilipczuk
University of Warsaw, Warsaw, Poland
28 shared publications
Latest Publications
- Open Access
- 21 July 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
Multivariate Exploration of Metric Dilation
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 ( u , v ) between their respective points in M . The dilation (or stretch) of G is defined as the minimum factor t such that, for any pair of vertices u , v , the distance between u and v —represented by the weight of a shortest u , v -path—is at most t · d M ( u , v ). We study Dilation t -Augmentation , where the objective is, given a metric M , a graph G , and numerical values k and t , to determine whether G can be transformed into a graph with dilation t by adding at most k edges. Our primary focus is on the scenario where the metric M is the shortest path metric of an unweighted graph Γ . Even in this specific case, Dilation t -Augmentation remains computationally challenging. In particular, the problem is W[2] -hard parameterized by k when Γ is a complete graph, already for t = 2. Our main contribution lies in providing new insights into the impact of combinations of various parameters on the computational complexity of the problem. We establish the following. • The parameterized dichotomy of the problem with respect to dilation t , when the graph G is sparse: Parameterized by k , the problem is FPT for graphs excluding a biclique K d , d as a subgraph for t ≤ 2 and the problem is W[1] -hard for t ≥ 3 even if G is a forest consisting of disjoint stars. • The problem is FPT parameterized by the combined parameter k + t + Δ , where Δ is the maximum degree of the graph G or Γ .
- 21 July 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
Open AccessMultivariate Exploration of Metric Dilation
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 ( u , v ) between their respective points in M . The dilation (or stretch) of G is defined as the minimum factor t such that, for any pair of vertices u , v , the distance between u and v —represented by the weight of a shortest u , v -path—is at most t · d M ( u , v ). We study Dilation t -Augmentation , where the objective is, given a metric M , a graph G , and numerical values k and t , to determine whether G can be transformed into a graph with dilation t by adding at most k edges. Our primary focus is on the scenario where the metric M is the shortest path metric of an unweighted graph Γ . Even in this specific case, Dilation t -Augmentation remains computationally challenging. In particular, the problem is W[2] -hard parameterized by k when Γ is a complete graph, already for t = 2. Our main contribution lies in providing new insights into the impact of combinations of various parameters on the computational complexity of the problem. We establish the following. • The parameterized dichotomy of the problem with respect to dilation t , when the graph G is sparse: Parameterized by k , the problem is FPT for graphs excluding a biclique K d , d as a subgraph for t ≤ 2 and the problem is W[1] -hard for t ≥ 3 even if G is a forest consisting of disjoint stars. • The problem is FPT parameterized by the combined parameter k + t + Δ , where Δ is the maximum degree of the graph G or Γ .
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1397-1408
What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1397-1408
Open AccessWhat Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 276-285
Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 276-285
Open AccessPath Cover, Hamiltonicity, and Independence Number: An FPT Perspective
- 23 March 2026
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 76 (3) , 1-39
Decomposition of Map Graphs with Applications
- 23 March 2026
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 76 (3) , 1-39
Decomposition of Map Graphs with Applications
- Open Access
- 5 February 2026
- Published by Springer Nature in Theory of Computing Systems
- Vol. 70 (1) , 5
Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
We examine the possibility of approximating Maximum Vertex-Disjoint Shortest Paths . In this problem, the input is an edge-weighted (directed or undirected) n -vertex graph G along with k terminal pairs $$(s_1,t_1),(s_2,t_2),\ldots ,(s_k,t_k)$$ . The task is to connect as many terminal pairs as possible by pairwise vertex-disjoint paths such that each path is a shortest path between the respective terminals. Our work is anchored in the recent breakthrough by Lochet [SODA ’21], which demonstrates the polynomial-time solvability of the problem for a fixed value of k . Lochet’s result implies the existence of a polynomial-time ck -approximation for Maximum Vertex-Disjoint Shortest Paths , where $$c \le 1$$ is a constant. (One can guess 1/ c terminal pairs to connect in $$k^{O({1}/{c})}$$ time and then utilize Lochet’s algorithm to compute the solution in $$n^{f({1}/{c})}$$ time.) Our first result suggests that this approximation algorithm is, in a sense, the best we can hope for. More precisely, assuming the gap-ETH, we exclude the existence of an o ( k )-approximation within $$f(k){{\,\textrm{poly}\,}}(n)$$ time for any function f that only depends on k . Our second result demonstrates the infeasibility of achieving an approximation ratio of $$m^{{1}/{2}-\varepsilon }$$ in polynomial time, unless P $$=$$ NP. We also show that this bound is tight by providing a simple $$\sqrt{\ell }$$ -approximation algorithm, where $$\ell $$ is the number of edges in all paths of an optimal solution. Additionally, we establish that Maximum Vertex-Disjoint Shortest Paths can be solved in $$2^{O(\ell )} {{\,\textrm{poly}\,}}(n)$$ time, but does not admit a polynomial kernel in $$\ell $$ . Moreover, it cannot be solved in $$2^{o(\ell )}{{\,\textrm{poly}\,}}(n)$$ time under ETH. Our hardness results hold for undirected graphs with unit weights, while our positive results extend to scenarios where the input graph is directed and features arbitrary (non-negative) edge weights.- 5 February 2026
- Published by Springer Nature in Theory of Computing Systems
- Vol. 70 (1) , 5
Open AccessTight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
We examine the possibility of approximating Maximum Vertex-Disjoint Shortest Paths . In this problem, the input is an edge-weighted (directed or undirected) n -vertex graph G along with k terminal pairs $$(s_1,t_1),(s_2,t_2),\ldots ,(s_k,t_k)$$ . The task is to connect as many terminal pairs as possible by pairwise vertex-disjoint paths such that each path is a shortest path between the respective terminals. Our work is anchored in the recent breakthrough by Lochet [SODA ’21], which demonstrates the polynomial-time solvability of the problem for a fixed value of k . Lochet’s result implies the existence of a polynomial-time ck -approximation for Maximum Vertex-Disjoint Shortest Paths , where $$c \le 1$$ is a constant. (One can guess 1/ c terminal pairs to connect in $$k^{O({1}/{c})}$$ time and then utilize Lochet’s algorithm to compute the solution in $$n^{f({1}/{c})}$$ time.) Our first result suggests that this approximation algorithm is, in a sense, the best we can hope for. More precisely, assuming the gap-ETH, we exclude the existence of an o ( k )-approximation within $$f(k){{\,\textrm{poly}\,}}(n)$$ time for any function f that only depends on k . Our second result demonstrates the infeasibility of achieving an approximation ratio of $$m^{{1}/{2}-\varepsilon }$$ in polynomial time, unless P $$=$$ NP. We also show that this bound is tight by providing a simple $$\sqrt{\ell }$$ -approximation algorithm, where $$\ell $$ is the number of edges in all paths of an optimal solution. Additionally, we establish that Maximum Vertex-Disjoint Shortest Paths can be solved in $$2^{O(\ell )} {{\,\textrm{poly}\,}}(n)$$ time, but does not admit a polynomial kernel in $$\ell $$ . Moreover, it cannot be solved in $$2^{o(\ell )}{{\,\textrm{poly}\,}}(n)$$ time under ETH. Our hardness results hold for undirected graphs with unit weights, while our positive results extend to scenarios where the input graph is directed and features arbitrary (non-negative) edge weights. - 2 January 2026
- Published by Springer Nature
- p. 48-61
When Does FTP Become FPT?
- Open Access
- 30 December 2025
- Published by Elsevier in Theoretical Computer Science
- Vol. 1065
The parameterized complexity landscape of two-sets cut-uncut
- 30 December 2025
- Published by Elsevier in Theoretical Computer Science
- Vol. 1065
Open AccessThe parameterized complexity landscape of two-sets cut-uncut
- Open Access
- 28 November 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 17 (4) , 1-19
Hybrid k-Clustering: Blending k-Median and k-Center
We propose a novel clustering model encompassing two well-known clustering models: k -center clustering and k -median clustering. In the Hybrid k -Clustering problem, given a set P of points in \(\mathbb {R}^d\) , an integer k , and a non-negative real r , our objective is to position k closed balls of radius r to minimize the sum of distances from points not covered by the balls to their closest balls. Equivalently, we seek an optimal L 1 -fitting of a union of k balls of radius r to a set of points in the Euclidean space. When r =0, this corresponds to k -median ; when the minimum sum is zero, indicating complete coverage of all points, it is k -center . Our primary result is a bicriteria approximation algorithm that, for a given ɛ > 0, produces a hybrid k -clustering with balls of radius (1+>) r . This algorithm achieves a cost at most 1+> of the optimum, and it operates in time \(2^{(kd/\varepsilon)^{\mathcal {O}(1)}} \cdot n^{\mathcal {O}(1)}\) . Notably, considering the established lower bounds on k -center and k -median, our bicriteria approximation stands as the best possible result for Hybrid k -Clustering . 1- 28 November 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 17 (4) , 1-19
Open AccessHybrid k-Clustering: Blending k-Median and k-Center
We propose a novel clustering model encompassing two well-known clustering models: k -center clustering and k -median clustering. In the Hybrid k -Clustering problem, given a set P of points in \(\mathbb {R}^d\) , an integer k , and a non-negative real r , our objective is to position k closed balls of radius r to minimize the sum of distances from points not covered by the balls to their closest balls. Equivalently, we seek an optimal L 1 -fitting of a union of k balls of radius r to a set of points in the Euclidean space. When r =0, this corresponds to k -median ; when the minimum sum is zero, indicating complete coverage of all points, it is k -center . Our primary result is a bicriteria approximation algorithm that, for a given ɛ > 0, produces a hybrid k -clustering with balls of radius (1+>) r . This algorithm achieves a cost at most 1+> of the optimum, and it operates in time \(2^{(kd/\varepsilon)^{\mathcal {O}(1)}} \cdot n^{\mathcal {O}(1)}\) . Notably, considering the established lower bounds on k -center and k -median, our bicriteria approximation stands as the best possible result for Hybrid k -Clustering . 1 - Open Access
- 24 November 2025
- Published by Springer Nature in Algorithmica
- Vol. 88 (1) , 10
Distributed Model Checking on Graphs of Bounded Treedepth
We establish that every monadic second-order logic (MSO) formula on graphs with bounded treedepth is decidable in a constant number of rounds within the model. To our knowledge, this marks the first meta-theorem regarding distributed model checking. Various optimization problems on graphs are expressible in MSO. Examples include determining whether a graph G has a clique of size k , whether it admits a coloring with k colors, whether it contains a graph H as a subgraph or minor, or whether terminal vertices in G could be connected via vertex-disjoint paths. Our meta-theorem significantly enhances the work of Bousquet et al. (in: 41st ACM Symposium on Principles of Distributed Computing (PODC), 2022), which was focused on distributed certification of MSO on graphs with bounded treedepth. Moreover, our results can be extended to solving optimization and counting problems expressible in MSO, in graphs of bounded treedepth.
- 24 November 2025
- Published by Springer Nature in Algorithmica
- Vol. 88 (1) , 10
Open AccessDistributed Model Checking on Graphs of Bounded Treedepth
We establish that every monadic second-order logic (MSO) formula on graphs with bounded treedepth is decidable in a constant number of rounds within the model. To our knowledge, this marks the first meta-theorem regarding distributed model checking. Various optimization problems on graphs are expressible in MSO. Examples include determining whether a graph G has a clique of size k , whether it admits a coloring with k colors, whether it contains a graph H as a subgraph or minor, or whether terminal vertices in G could be connected via vertex-disjoint paths. Our meta-theorem significantly enhances the work of Bousquet et al. (in: 41st ACM Symposium on Principles of Distributed Computing (PODC), 2022), which was focused on distributed certification of MSO on graphs with bounded treedepth. Moreover, our results can be extended to solving optimization and counting problems expressible in MSO, in graphs of bounded treedepth.
- Open Access
- 10 November 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 22 (1) , 1-44
Tree Containment above Minimum Degree Is FPT
According to the classic Chvátal’s Lemma from 1977, a graph \( G \) of minimum degree \(\delta(G)\) contains every tree on \(\delta(G)+1\) vertices. Our main result is the following algorithmic “extension” of Chvátal’s Lemma: For any \( n \) -vertex graph \( G \) , an integer \( k \) , and a tree \( T \) on at most \(\delta(G)+k\) vertices, deciding whether \( G \) contains a subgraph isomorphic to \( T \) can be done in time \(f(k)\cdot n^{\mathcal{O}(1)}\) for some function \( f \) of \( k \) only. The proof is based on an intricate interplay between extremal graph theory and parameterized algorithms.- 10 November 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 22 (1) , 1-44
Open AccessTree Containment above Minimum Degree Is FPT
According to the classic Chvátal’s Lemma from 1977, a graph \( G \) of minimum degree \(\delta(G)\) contains every tree on \(\delta(G)+1\) vertices. Our main result is the following algorithmic “extension” of Chvátal’s Lemma: For any \( n \) -vertex graph \( G \) , an integer \( k \) , and a tree \( T \) on at most \(\delta(G)+k\) vertices, deciding whether \( G \) contains a subgraph isomorphic to \( T \) can be done in time \(f(k)\cdot n^{\mathcal{O}(1)}\) for some function \( f \) of \( k \) only. The proof is based on an intricate interplay between extremal graph theory and parameterized algorithms.