Blar i Bergen Open Research Archive på forfatter "Fomin, Fedor"

An Algorithmic MetaTheorem for Graph Modification to Planarity and FOL
Fomin, Fedor; Golovach, Petr; Stamoulis, Giannos; Thilikos, Dimitrios M. (Journal article; Peer reviewed, 2020)In general, a graph modification problem is defined by a graph modification operation ⊠ and a target graph property 𝒫. Typically, the modification operation ⊠ may be vertex removal, edge removal, edge contraction, or edge ... 
Approximating Acyclicity Parameters of Sparse Hypergraphs
Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios (Peer reviewed; Journal article, 2009)The notions of hypertree width and generalized hypertree width were introduced by Gottlob, Leone, and Scarcello (PODS'99, PODS'01) in order to extend the concept of hypergraph acyclicity. These notions were further generalized ... 
Bidimensionality and Kernels
Fomin, Fedor; Lokshtanov, Daniel; Saurabh, Saket; Thilikos, Dimitrios (Journal article; Peer reviewed, 2020)Bidimensionality theory was introduced by [E. D. Demaine et al., J. ACM, 52 (2005), pp. 866893] as a tool to obtain subexponential time parameterized algorithms on Hminorfree graphs. In [E. D. Demaine and M. Hajiaghayi, ... 
Building large kcores from sparse graphs
Fomin, Fedor; Sagunov, Danil; Simonov, Kirill (Journal article; Peer reviewed, 2020)A popular model to measure network stability is the kcore, that is the maximal induced subgraph in which every vertex has degree at least k. For example, kcores are commonly used to model the unraveling phenomena in ... 
Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs
Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios M. (Journal article; Peer reviewed, 2023)We introduce the rendezvous game with adversaries. In this game, two players, Facilitator and Divider, play against each other on a graph. Facilitator has two agents and Divider has a team of k agents located in some ... 
Connecting Vertices by Independent Trees
Basavaraju, Manu; Fomin, Fedor; Golovach, Petr; Saurabh, Saket (Journal article; Peer reviewed, 2014)We study the paramereteized complexity of the following connectivity problem. For a vertex subset U of a graph G, trees T1, . . . , Ts of G are completely independent spanning trees of U if each of them contains U , and ... 
Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals
Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav (Peer reviewed; Journal article, 2019)Perturbed graphic matroids are binary matroids that can be obtained from a graphic matroid by adding a noise of small rank. More precisely, an rrank perturbed graphic matroid M is a binary matroid that can be represented ... 
Decomposition of map graphs with applications
Fomin, Fedor; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav (Peer reviewed; Journal article, 2019) 
Detours in Directed Graphs
Fomin, Fedor; Golovach, Petr; Lochet, William Alexandre; Sagunov, Danil; Simonov, Kirill; Saurabh, Saket (Journal article; Peer reviewed, 2022)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 Path that we study, called Longest Detour, ... 
Detours in directed graphs
Fomin, Fedor; Golovach, Petr; Lochet, William Alexandre; Sagunov, Danil; Saurabh, Saket; Simonov, Kirill (Journal article; Peer reviewed, 2023)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 Path that we study, called Longest Detour, ... 
Diverse Collections in Matroids and Graphs
Fomin, Fedor; Golovach, Petr; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (Journal article; Peer reviewed, 2021)We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems, two from the theory of matroids and the third from graph theory. The input to the Weighted Diverse ... 
Diverse collections in matroids and graphs
Fomin, Fedor; Golovach, Petr; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (Journal article; Peer reviewed, 2023)We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems. The input to the Weighted Diverse Bases problem consists of a matroid M, a weight function ω : ... 
Diverse Pairs of Matchings
Fomin, Fedor; Golovach, Petr; Jaffke, Lars; Philip, Geevarghese; Sagunov, Danil (Journal article; Peer reviewed, 2020)We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph G and an integer k, ask whether G has two (maximum/perfect) matchings whose symmetric difference is at least k. Diverse ... 
ETH Tight Algorithms for Geometric Intersection Graphs: Now in Polynomial Space
Fomin, Fedor; Golovach, Petr; Inamdar, Tanmay Nitin; Saurabh, Saket (Journal article; Peer reviewed, 2021)De Berg et al. in [SICOMP 2020] gave an algorithmic framework for subexponential algorithms on geometric graphs with tight (up to ETH) running times. This framework is based on dynamic programming on graphs of weighted ... 
ETHtight algorithms for long path and cycle on unit disk graphs
Fomin, Fedor; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2020)We present an algorithm for the extensively studied Long Path and Long Cycle problems on unit disk graphs that runs in time 2O(√k)(n + m). Under the Exponential Time Hypothesis, Long Path and Long Cycle on unit disk graphs ... 
Exact algorithms for treewidth and minimum fillin
Fomin, Fedor; Todinca, Ioan; Kratsch, Dieter; Villanger, Yngve (Journal article, 2006) 
Exact Exponential Algorithms for Clustering Problems
Fomin, Fedor; Golovach, Petr; Inamdar, Tanmay Nitin; Purohit, Nidhi; Saurabh, Saket (Journal article; Peer reviewed, 2022)In this paper we initiate a systematic study of exact algorithms for some of the well known clustering problems, namely kMEDIAN and kMEANS. In kMEDIAN, the input consists of a set X of n points belonging to a metric ... 
Exploring Subexponential Parameterized Complexity of Completion Problems
Drange, Pål Grønås; Fomin, Fedor; Pilipczuk, Michal Pawel; Villanger, Yngve (Peer reviewed; Journal article, 20140219)Let F be a family of graphs. In the FCompletion problem, we are given an nvertex graph G and an integer k as input, and asked whether at most k edges can be added to G so that the resulting graph does not contain a graph ... 
Finding Induced Subgraphs via Minimal Triangulations
Fomin, Fedor; Villanger, Yngve (Peer reviewed; Journal article, 2010)Potential maximal cliques and minimal separators are combinatorial objects which were introduced and studied in the realm of minimal triangulation problems in cluding Minimum Fillin and Treewidth. We discover unexpected ... 
A FixedParameter Perspective on #BIS
Curticapean, Radu; Dell, Holger; Fomin, Fedor; Goldberg, Leslie Ann; Lapinskas, John (Peer reviewed; Journal article, 20190718)The problem of (approximately) counting the independent sets of a bipartite graph (#BIS) is the canonical approximate counting problem that is complete in the intermediate complexity class #RHΠ1. It is believed that #BIS ...