Blar i Bergen Open Research Archive på forfatter "Fomin, Fedor"
-
Exact algorithms for treewidth and minimum fill-in
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 k-MEDIAN and k-MEANS. In k-MEDIAN, 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, 2014-02-19)Let F be a family of graphs. In the F-Completion problem, we are given an n-vertex 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 Fill-in and Treewidth. We discover unexpected ... -
A Fixed-Parameter Perspective on #BIS
Curticapean, Radu; Dell, Holger; Fomin, Fedor; Goldberg, Leslie Ann; Lapinskas, John (Peer reviewed; Journal article, 2019-07-18)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 ... -
FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges
Fomin, Fedor; Golovach, Petr; Inamdar, Tanmay Nitin; Koana, Tomohiro (Journal article; Peer reviewed, 2023)We study the α-Fixed Cardinality Graph Partitioning (α-FCGP) problem, the generic local graph partitioning problem introduced by Bonnet et al. [Algorithmica 2015]. In this problem, we are given a graph G, two numbers k,p ... -
FPT Approximation for Fair Minimum-Load Clustering
Bandyapadhyay, Sayan; Fomin, Fedor; Golovach, Petr; Purohit, Nidhi; Simonov, Kirill (Journal article; Peer reviewed, 2022)In this paper, we consider the Minimum-Load k-Clustering/Facility Location (MLkC) problem where we are given a set P of n points in a metric space that we have to cluster and an integer k > 0 that denotes the number of ... -
Going Far from Degeneracy
Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2020)An undirected graph $G$ is $d$-degenerate if every subgraph of $G$ has a vertex of degree at most $d$. By the classical theorem of Erdös and Gallai from 1959, every graph of degeneracy $d>1$ contains a cycle of length at ... -
Going Far From Degeneracy
Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav (Peer reviewed; Journal article, 2019-09-06)An undirected graph G is d-degenerate if every subgraph of G has a vertex of degree at most d. By the classical theorem of Erd\H{o}s and Gallai from 1959, every graph of degeneracy d>1 contains a cycle of length at least ... -
How to find a good explanation for clustering?
Bandyapadhyay, Sayan; Fomin, Fedor; Golovach, Petr; Lochet, William Alexandre; Purohit, Nidhi; Simonov, Kirill (Journal article; Peer reviewed, 2023)k-means and k-median clustering are powerful unsupervised machine learning techniques. However, due to complicated dependencies on all the features, it is challenging to interpret the resulting cluster assignments. Moshkovitz, ... -
Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
Fernau, Henning; Fomin, Fedor; Lokshtanov, Daniel; Raible, Daniel; Saurabh, Saket; Villanger, Yngve (Peer reviewed; Journal article, 2009)The {\sc \(k\)-Leaf Out-Branching} problem is to find an out-branching, that is a rooted oriented spanning tree, with at least \(k\) leaves in a given digraph. The problem has recently received much attention from the ... -
Kernelization for Spreading Points
Fomin, Fedor; Golovach, Petr; Inamdar, Tanmay Nitin; Zehavi, Meirav (Journal article; Peer reviewed, 2023)We consider the following problem about dispersing points. Given a set of points in the plane, the task is to identify whether by moving a small number of points by small distance, we can obtain an arrangement of points ... -
Kernelization of Graph Hamiltonicity: Proper H-Graphs
Chaplick, Steven; Fomin, Fedor; Golovach, Petr; Knop, Dusan; Zeman, Peter (Journal article; Peer reviewed, 2021)We obtain new polynomial kernels and compression algorithms for Path Cover and Cycle Cover, the well-known generalizations of the classical Hamiltonian Path and Hamiltonian Cycle problems. Our choice of parameterization ... -
Kernelization of Whitney Switches
Fomin, Fedor; Golovach, Petr (Journal article; Peer reviewed, 2020)A fundamental theorem of Whitney from 1933 asserts that 2-connected graphs G and H are 2-isomorphic, or equivalently, their cycle matroids are isomorphic, if and only if G can be transformed into H by a series of operations ... -
Kernelization of Whitney Switches
Fomin, Fedor; Golovach, Petr (Journal article; Peer reviewed, 2021)A fundamental theorem of Whitney from 1933 asserts that 2-connected graphs $G$ and $H$ are 2-isomorphic, or equivalently, their cycle matroids are isomorphic if and only if $G$ can be transformed into $H$ by a series of ... -
Kernelizing Temporal Exploration Problems
Arrighi, Emmanuel Jean Paul Pierre; Fomin, Fedor; Golovach, Petr; Wolf, Petra Henrike Karola (Journal article; Peer reviewed, 2023)We study the kernelization of exploration problems on temporal graphs. A temporal graph consists of a finite sequence of snapshot graphs 𝒢 = (G₁, G₂, … , G_L) that share a common vertex set but might have different edge ... -
Largest chordal and interval subgraphs faster than 2n
Bliznets, Ivan; Fomin, Fedor; Pilipczuk, Michal Pawel; Villanger, Yngve (Peer reviewed; Journal article, 2015-08-22)We prove that in a graph with n vertices, induced chordal and interval subgraphs with the maximum number of vertices can be found in time O(2λn) for some λ< 1. These are the first algorithms breaking the trivial 2nnO(1) ... -
Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms
Fomin, Fedor; Golovach, Petr; Sagunov, Danil; Simonov, Kirill (Journal article; Peer reviewed, 2022)We discuss recent algorithmic extensions of two classic results of extremal combinatorics about long paths in graphs. First, the theorem of Dirac from 1952 asserts that a 2-connected graph G with the minimum vertex degree ... -
Longest Cycle Above Erdös-Gallai Bound
Fomin, Fedor; Golovach, Petr; Sagunov, Danil; Simonov, Kirill (Journal article; Peer reviewed, 2022)In 1959, Erdős and Gallai proved that every graph G with average vertex degree ad(G) ≥ 2 contains a cycle of length at least ad(G). We provide an algorithm that for k ≥ 0 in time 2^𝒪(k)⋅n^𝒪(1) decides whether a 2-connected ... -
Lossy Kernelization of Same-Size Clustering
Bandyapadhyay, Sayan; Fomin, Fedor; Golovach, Petr; Purohit, Nidhi; Simonov, Kirill (Journal article; Peer reviewed, 2023)In this work, we study the k-median clustering problem with an additional equal-size constraint on the clusters from the perspective of parameterized preprocessing. Our main result is the first lossy (2-approximate) ...