Photo:
Det Norske Videnskaps-Akademi/Thomas B. Eckhoff
- E-mailfedor.fomin@uib.no
- Phone+47 55 58 40 24
- Visitor AddressHIB - Thormøhlens gate 555006 Bergen
- Postal AddressPostboks 78035020 Bergen
I am a professor in Algorithms at the University of Bergen. My research area is Theoretical Computer Science, and my current research interests are in Graph Algorithms, Parameterized Complexity, Algorithmic Fairness, Algorithmic Foundations of Machine Learning, and Combinatorial Games. I am a member of the Norwegian Academy of Science and Letters, the Norwegian Academy of Technological Sciences, and the Academia Europaea.
Open acess publications in arXiv.
Books (with links to free downloads)
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi, Kernelization. Theory of Parameterized Preprocessing, Cambridge University Press, 2019. Amazon link. Free downloadable version and errata are available from here.
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh, Parameterized Algorithms, Springer, 2015. Amazon link. Free downloadable version and errata are available from here.
Fedor V. Fomin and Dieter Kratsch, Exact Exponential Algorithms, Springer, 2010. Amazon link. Free downloadable version and errata are available from here.
The following list of publications is automatically generated from the Norwegian national database CRIStin.
Academic article
- (2022). Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering. SIAM journal on computing (Print). 1866-1930.
- (2022). Present-biased optimization. Mathematical Social Sciences. 56-67.
- (2022). Parameterized Complexity of Elimination Distance to First-Order Logic Properties. ACM Transactions on Computational Logic. 1-35.
- (2022). On the optimality of pseudo-polynomial algorithms for integer programming. Mathematical programming.
- (2022). On the Parameterized Complexity of the Expected Coverage Problem. Theory of Computing Systems. 432-453.
- (2022). Lossy Kernelization of Same-Size Clustering. Lecture Notes in Computer Science (LNCS). 96-114.
- (2022). Longest Cycle Above Erdös-Gallai Bound. Leibniz International Proceedings in Informatics. 1-15.
- (2022). Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms. Leibniz International Proceedings in Informatics. 1-4.
- (2022). How to Find a Good Explanation for Clustering? Proceedings of the AAAI Conference on Artificial Intelligence. 3904-3912.
- (2022). Fast FPT-approximation of branchwidth. Proceedings of the Annual ACM Symposium on Theory of Computing. 886-899.
- (2022). FPT Approximation for Fair Minimum-Load Clustering. Leibniz International Proceedings in Informatics. 1-14.
- (2022). Exact Exponential Algorithms for Clustering Problems. Leibniz International Proceedings in Informatics. 1-14.
- (2022). Detours in Directed Graphs. Leibniz International Proceedings in Informatics. 1-6.
- (2022). Boolean and Fp-Matrix Factorization: From Theory to Practice. Proceedings of the International Joint Conference on Neural Networks.
- (2022). Algorithmic Extensions of Dirac's Theorem. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 406-416.
- (2022). (Re)packing Equal Disks into Rectangle. Leibniz International Proceedings in Informatics. 1-17.
- (2021). ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs . Journal of Computational Geometry. 126-148.
- (2021). Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds. ACM Transactions on Computation Theory. 10:1-10:25.
- (2019). Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems. ACM Transactions on Algorithms (TALG). 44 pages.
- (2019). Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree. SIAM Journal on Discrete Mathematics. 327-345.
- (2019). On width measures and topological problems on semi-complete digraphs. Journal of combinatorial theory. Series B (Print). 78-165.
- (2019). Modification to planarity is fixed parameter tractable. Leibniz International Proceedings in Informatics. 28:1-28:17.
- (2019). Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs. Discrete & Computational Geometry. 879-911.
- (2019). Exact algorithms via monotone local search. Journal of the ACM. 8:1-8:23.
- (2018). Parameterized low-rank binary matrix approximation. Leibniz International Proceedings in Informatics. 1-16.
- (2018). On the tractability of optimization problems on H-graphs. Leibniz International Proceedings in Informatics. 1-14.
- (2018). On the optimality of pseudo-polynomial algorithms for integer programming. Leibniz International Proceedings in Informatics. 31:1-31:13.
- (2018). A Fixed-Parameter Perspective on #BIS. Leibniz International Proceedings in Informatics. 13:1-13:13.
- (2017). Tight lower bounds on graph embedding problems. Journal of the ACM. 1-22.
- (2017). Representative families of product families. ACM Transactions on Algorithms (TALG). 1-29.
- (2017). Metric Dimension of Bounded Tree-length Graphs. SIAM Journal on Discrete Mathematics. 1217-1243.
- (2017). Matrix rigidity from the viewpoint of parameterized complexity. Leibniz International Proceedings in Informatics.
- (2017). Finding, hitting and packing cycles in subexponential time on unit disk graphs. Leibniz International Proceedings in Informatics. 1-15.
- (2017). Finding detours is fixed-parameter tractable. Leibniz International Proceedings in Informatics. 2326-2345.
- (2017). Faster exact algorithms for some terminal set problems. Journal of computer and system sciences. 195-207.
- (2017). Exact algorithms for terrain guarding. Leibniz International Proceedings in Informatics. 111-1115.
- (2017). Covering vectors by spaces: Regular matroids. Leibniz International Proceedings in Informatics. 1-15.
- (2017). Algorithms parameterized by vertex cover and modular width, through potential maximal cliques. Algorithmica. 1146-1169.
- (2016). Vertex cover structural parameterization revisited. Lecture Notes in Computer Science (LNCS). 171-182.
- (2016). Subexponential algorithms for rectilinear Steiner tree and arborescence problems. Leibniz International Proceedings in Informatics. 39.1-39.15.
- (2016). Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering. Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS). 515-524.
- (2016). Parameterized complexity of the anchored k-core problem for directed graphs. Information and Computation. 11-22.
- (2016). Parameterized complexity of secluded connectivity problems. Theory of Computing Systems. 1-25.
- (2016). Parameterized Complexity of Superstring Problems. Algorithmica. 1-16.
- (2016). Kernelization and sparseness: The case of dominating set. Leibniz International Proceedings in Informatics. 14 pages.
- (2016). How to hunt an invisible rabbit on a graph. European journal of combinatorics (Print). 12-26.
- (2016). Hitting forbidden minors: Approximation and kernelization. SIAM Journal on Discrete Mathematics. 383-410.
- (2016). Exact algorithms via monotone local search. Proceedings of the Annual ACM Symposium on Theory of Computing. 764-775.
- (2016). Efficient computation of representative families with applications in parameterized and exact algorithms. Journal of the ACM.
- (2016). Editing to connected f-degree graph. Leibniz International Proceedings in Informatics. 1-15.
- (2016). A $c^k n$ 5-approximation algorithm for treewidth. SIAM journal on computing (Print). 317-378.
- (2016). (Meta) Kernelization. Journal of the ACM.
- (2015). Parameterized complexity of secluded connectivity problems. Leibniz International Proceedings in Informatics. 408-419.
- (2015). On the parameterized complexity of vertex cover and edge cover with connectivity constraints. Theoretical Computer Science. 1-15.
- (2015). Minimizing Rosenthal potential in multicast games. Theory of Computing Systems. 81-96.
- (2015). Large induced subgraphs via triangulations and CMSO. SIAM journal on computing (Print). 54-87.
- (2015). Computing tree-depth faster than 2n. Algorithmica. 202-216.
- (2014). To satisfy impatient Web surfers is hard. Theoretical Computer Science. 1-17.
- (2014). Tight bounds for parameterized complexity of Cluster Editing with a small number of clusters. Journal of computer and system sciences. 1430-1447.
- (2014). Social choice meets graph drawing: How to get subexponential time algorithms for ranking and drawing problems. Tsinghua Science and Technology. 374-386.
- (2014). Searching for better fill-in. Journal of computer and system sciences. 1374-1383.
- (2014). Representative sets of product families. Lecture Notes in Computer Science (LNCS). 443-454.
- (2014). Preprocessing subgraph and minor problems: When does a small vertex cover help? Journal of computer and system sciences. 468-495.
- (2014). Parameterized complexity of firefighting. Journal of computer and system sciences. 1285-1297.
- (2014). Parameterized complexity of connected even/odd subgraph problems. Journal of computer and system sciences. 157-179.
- (2014). Parameterized algorithms to preserve connectivity. Lecture Notes in Computer Science (LNCS). 800-811.
- (2014). Long circuits and large euler subgraphs. SIAM Journal on Discrete Mathematics. 878-892.
- (2014). Enumerating minimal subset feedback vertex sets. Algorithmica. 216-231.
- (2014). Almost optimal lower bounds for problems parameterized by clique-width. SIAM journal on computing (Print). 1541-1563.
- (2014). Algorithms parameterized by vertex cover and modular width, through potential maximal cliques. Lecture Notes in Computer Science (LNCS). 182-193.
- (2014). A subexponential parameterized algorithm for proper interval completion. Lecture Notes in Computer Science (LNCS). 173-184.
- (2013). Tight bounds for parameterized complexity of Cluster Editing. Leibniz International Proceedings in Informatics. 32-43.
- (2013). Subexponential parameterized algorithm for minimum fill-in. SIAM journal on computing (Print). 2197-2216.
- (2013). Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph. Lecture Notes in Computer Science (LNCS). 505-516.
- (2013). Quadratic upper bounds on the Erdős–Pósa property for a generalization of packing and covering cycles. Journal of Graph Theory. 417-424.
- (2013). Largest chordal and interval subgraphs faster than 2^n. Lecture Notes in Computer Science (LNCS). 193-204.
- (2013). Jungles, bundles, and fixed parameter tractability. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 396-413.
- (2013). Exact algorithms for finding longest cycles in claw-free graphs. Algorithmica. 129-145.
- (2013). Computing tree-depth faster than 2^n. Lecture Notes in Computer Science (LNCS). 137-149.
- (2013). Beyond bidimensionality: Parameterized subexponential algorithms on directed graphs. Information and Computation. 60-70.
- (2013). An O(c^k n) 5-approximation algorithm for treewidth. Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS). 499-508.
- (2013). A polynomial kernel for proper interval vertex deletion. SIAM Journal on Discrete Mathematics. 1964-1976.
- (2012). Treewidth computation and extremal combinatorics. Combinatorica. 289-308.
- (2012). Subexponential parameterized algorithm for minimum fill-in. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 1737-1746.
- (2012). Sharp separation and applications to exact and parameterized algorithms. Algorithmica. 692-706.
- (2012). Planar F-deletion: Approximation, kernelization and optimal FPT algorithms (extended abstract). Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS). 470-479.
- (2012). Parameterized complexity of the spanning tree congestion problem. Algorithmica. 85-111.
- (2012). On exact algorithms for treewidth. ACM Transactions on Algorithms (TALG). 23 pages.
- (2012). Making Life Easier for Firefighters. Lecture Notes in Computer Science (LNCS). 177-188.
- (2012). Local search: Is brute-force avoidable? Journal of computer and system sciences. 707-719.
- (2012). Kernel(s) for Problems with no Kernel: On Out-Trees with Many Leaves. ACM Transactions on Algorithms (TALG). 19 pages.
- (2012). Faster algorithms for finding and counting subgraphs. Journal of computer and system sciences. 698-706.
- (2012). Counting subgraphs via homomorphisms. SIAM Journal on Discrete Mathematics. 695-717.
- (2012). Cops and robber with constraints. SIAM Journal on Discrete Mathematics. 571-590.
- (2012). Cops and robber game without recharging. Theory of Computing Systems. 611-620.
- (2012). Connected graph searching. Information and Computation. 1-16.
- (2012). Catalan structures and dynamic programming in H-minor-free graphs. Journal of computer and system sciences. 1606-1622.
- (2012). A note on exact algorithms for vertex ordering problems on graphs. Theory of Computing Systems. 420-432.
- (2011). Subexponential algorithms for partial cover problems. Information Processing Letters. 814-818.
- (2011). Strengthening Erdos-Posa Property for Minor-Closed Graph Classes. Journal of Graph Theory. 235-240.
- (2011). Spanners of bounded degree graphs. Information Processing Letters. 142-144.
- (2011). Spanners in sparse graphs. Journal of computer and system sciences. 1108-1119.
- (2011). On the complexity of some colorful problems parameterized by treewidth. Information and Computation. 143-153.
- (2011). On the Complexity of Reconstructing H-Free Graphs from Their Star Systems. Journal of Graph Theory. 113-124.
- (2011). Minimum Fill-in of Sparse Graphs: Kernelization and Approximation. Leibniz International Proceedings in Informatics. 164-175.
- (2011). Kernels for feedback arc set in tournaments. Journal of computer and system sciences. 1071-1078.
- (2011). Implicit branching and parameterized partial cover problems. Journal of computer and system sciences. 1159-1171.
- (2011). How to Guard a Graph? Algorithmica. 839-856.
- (2011). Guard games on graphs: Keep the intruder out! Theoretical Computer Science. 6484-6497.
- (2011). Faster parameterized algorithms for minor containment. Theoretical Computer Science. 7018-7028.
- (2011). Exact Algorithm for the Maximum Induced Planar Subgraph Problem. Lecture Notes in Computer Science (LNCS). 287-298.
- (2011). Enumerating minimal subset feedback vertex sets. Lecture Notes in Computer Science (LNCS). 399-410.
- (2011). Contraction obstructions for treewidth. Journal of combinatorial theory. Series B (Print). 302-314.
- (2011). Branch and Recharge: Exact Algorithms for Generalized Domination. Algorithmica. 252-273.
- (2011). Approximation Algorithms for Domination Search. Lecture Notes in Computer Science (LNCS). 130-141.
- (2011). Approximating width parameters of hypergraphs with excluded minors. SIAM Journal on Discrete Mathematics. 1331-1348.
- (2011). An exact algorithm for minimum distortion embedding. Theoretical Computer Science. 3530-3536.
- (2010). Pursuing a fast robber on a graph. Theoretical Computer Science. 1167-1181.
- (2010). Intractability of clique-width parameterizations. SIAM journal on computing (Print). 1941-1956.
- (2010). Efficient exact algorithms on planar graphs: exploiting sphere cut decompositions. Algorithmica. 790-810.
- (2010). Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem. Journal of computer and system sciences. 650-662.
- (2009). Subexponential Algorithms for Partial Cover Problems. Leibniz International Proceedings in Informatics. 193-201.
- (2009). Sort and Search: Exact algorithms for generalized domination. Information Processing Letters. 795-798.
- (2009). On two techniques of combining branching and treewidth. Algorithmica. 181-207.
- (2009). Mixed search number and linear-width of interval and split graphs. Networks.
- (2009). Kernels for Feedback Arc Set In Tournaments. Leibniz International Proceedings in Informatics. 37-47.
- (2009). Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves. Leibniz International Proceedings in Informatics. 421-432.
- (2009). Distortion Is Fixed Parameter Tractable. Lecture Notes in Computer Science (LNCS). 463-474.
- (2009). Computing branchwidth via efficient triangulations and blocks. Discrete Applied Mathematics. 2726-2736.
- (2009). Approximating Acyclicity Parameters of Sparse Hypergraphs. Leibniz International Proceedings in Informatics. 445-456.
- (2009). An Exact Algorithm for Minimum Distortion Embedding. Lecture Notes in Computer Science (LNCS). 112-121.
- (2009). Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem. Lecture Notes in Computer Science (LNCS). 37-46.
- (2009). A measure & conquer approach for the analysis of exact algorithms. Journal of the ACM. 32 pages.
- (2008). On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms. Algorithmica. 293-307.
- (2008). Improved algorithms for feedback vertex set problems. Journal of computer and system sciences. 1188-1198.
- (2008). Faster Steiner Tree Computation in Polynomial-Space. Lecture Notes in Computer Science (LNCS). 430-441.
- (2008). Exact algorithms for treewidth and minimum fill-in. SIAM journal on computing (Print). 1058-1079.
- (2008). Combinatorial Bounds via Measure and Conquer: Bounding Minimal Dominating Sets and Applications. ACM Transactions on Algorithms (TALG). 17 pages.
- (2008). An annotated bibliography on guaranteed graph searching. Theoretical Computer Science. 236-245.
- (2007). On self duality of pathwidth in polyhedral graph embeddings. Journal of Graph Theory. 42-54.
- (2007). Mixed search number and linear-width of interval and split graphs. Lecture Notes in Computer Science (LNCS). 304-315.
- (2007). Exact algorithms for graph homomorphisms. Theory of Computing Systems. 381-393.
- (2007). Branch and Recharge: Exact Algorithms for Generalized Domination. Lecture Notes in Computer Science (LNCS). 507-518.
- (2007). Backbone colorings for graphs: Tree and path backbones. Journal of Graph Theory. 137-152.
- (2006). Solving Connected Dominating Set Faster than O(2n). Lecture Notes in Computer Science (LNCS). 152-163.
- (2006). Planar graph coloring avoiding monochromatic subgraphs: Trees and paths make it difficult. Algorithmica. 343-361.
- (2006). Pathwidth of cubic graphs and exact algorithms. Information Processing Letters. 191-196.
- (2006). Optimal linear arrangement of interval graphs. Lecture Notes in Computer Science (LNCS). 267-279.
- (2006). On exact algorithms for treewidth. Lecture Notes in Computer Science (LNCS). 672-683.
- (2006). New upper bounds on the decomposability of planar graphs. Journal of Graph Theory. 53-81.
- (2006). Finding a Minimum Feedback Vertex Set in time O(1.7548n). Lecture Notes in Computer Science (LNCS). 184-191.
- (2006). Fast subexponential algorithm for non-local problems on graphs of bounded genus. Lecture Notes in Computer Science (LNCS). 172-183.
- (2006). Dominating sets in planar graphs: Branch-width and exponential speed-up. SIAM journal on computing (Print). 281-309.
- (2006). Branching and treewidth based exact algorithms. Lecture Notes in Computer Science (LNCS). 16-25.
- (2006). A 3-approximation for the pathwidth of Halin graphs. Journal of Discrete Algorithms. 499-510.
- (2005). Tree decompositions with small cost. Discrete Applied Mathematics. 143-154.
- (2005). Nondeterministic Graph Searching: From Pathwidth to Treewidth. Lecture Notes in Computer Science (LNCS). 364-375.
- (2005). Measure and conquer: Domination - A case study. Lecture Notes in Computer Science (LNCS). 191-203.
- (2005). Fixed-parameter algorithms for (k,r)-center in planar graphs and map graphs. ACM Transactions on Algorithms (TALG). 33-47.
- (2005). Bidimensional parameters and local treewidth. SIAM Journal on Discrete Mathematics. 501-511.
- (2004). Radio labeling with preassigned frequencies. SIAM Journal on Optimization. 1-16.
- (2004). Parallel knock-out schemes in networks,. Lecture Notes in Computer Science (LNCS). 204-214.
- (2004). On distance constrained labeling of disk graphs. Theoretical Computer Science. 261-292.
- (2004). Graph searching, elimination trees, and a generalization of bandwidth. Algorithmica. 73-87.
- (2004). Fast parameterized algorithms for graphs on surfaces: Linear kernel and exponential speed-up. Lecture Notes in Computer Science (LNCS). 581-592.
- (2004). Exact (exponential) algorithms for treewidth and minimum fill-in. Lecture Notes in Computer Science (LNCS). 568-580.
- (2004). Equitable colorings of bounded treewidth graphs. Lecture Notes in Computer Science (LNCS). 180-190.
- (2004). Dominating sets and local treewidth. Lecture Notes in Computer Science (LNCS). 221-229.
- (2004). Backbone colorings for networks. Lecture Notes in Computer Science (LNCS). 131-142.
- (2004). A simple and fast approach for solving problems on planar graphs. Lecture Notes in Computer Science (LNCS). 56-67.
- (2003). On the domination search numbe. Discrete Applied Mathematics. 565-580.
- (2003). Interval degree and bandwidth of a graph. Discrete Applied Mathematics. 345-359.
- (2002). More About Subcolorings. Computing. 187-203.
- (2002). Approximation of pathwidth of outerplanar graphs. Journal of Algorithms. 190-200.
- (2002). A generalization of the graph bandwidth. Vestnik St. Petersburg Univ. Math.. 15-19.
Academic lecture
- (2022). Lossy Kernelization of Same-Size Clustering.
- (2008). Catalan structures and dynamic programming in H-minor-free graphs.
- (2004). Parallel knock-out schemes in networks.
- (2004). Exact (exponential) algorithms for treewidth and minimum fill-in.
- (2004). Equitable colorings of bounded treewidth graphs.
- (2004). Dominating sets in planar graphs: branch-width and exponential speed-up.
- (2004). Bidimensional Parameters and Local Treewidth.
- (2004). A Simple and Fast Approach for Solving Problems on Planar Graphs.
- (2003). Graph searching, elimination trees, and a generalization of bandwidth.
- (2003). Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs.
- (2003). Dominating sets and local treewidth.
- (2003). Backbone colorings for networks.
- (2002). Tree Decompositions with Small Cost.
- (2002). Radio Labeling with Pre-assigned Frequencies.
- (2001). Planar Graph Coloring with Forbidden Subgraphs: Why Trees and Paths Are Dangerous.
Academic anthology/Conference proceedings
- (2018). Computer Science - Theory and Applications - 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6-10, 2018, Proceedings. Springer.
- (2012). Algorithm Theory - SWAT 2012 - 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings. Springer.
- (2009). Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009. Springer.
- (2007). Counting Minimum Weighted Dominating Sets. Springer.
- (2006). Graph-Theoretic Concepts in Computer Science, 32nd International Workshop, WG 2006 Bergen, Norway, June 22-23, 2006 Revised Papers, Lecture Notes in Computer Science, vol. 4271. Springer.
Abstract
- (2013). On the Parameterized Complexity of Cutting a Few Vertices from a Graph. Lecture Notes in Computer Science (LNCS). 421-432.
- (2013). Long Circuits and Large Euler Subgraphs. Lecture Notes in Computer Science (LNCS). 493-504.
- (2008). 08431 Executive Summary -- Moderately Exponential Time Algorithms. Dagstuhl Seminar Proceedings. 3 pages.
Academic literature review
- (2013). Exact exponential algorithms. Communications of the ACM. 80-88.
- (2012). Kernelization algorithms (keynote speech). Smart Innovation, Systems and Technologies. 1-7.
More information in national current research information system (CRIStin)
Related content
