Browsing Bergen Open Research Archive by Author "Saurabh, Saket"
Now showing items 120 of 35

A (2 + ε)Factor Approximation Algorithm for Split Vertex Deletion
Lokshtanov, Daniel; Misra, Pranabendu; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (Journal article; Peer reviewed, 2020)In the Split Vertex Deletion (SVD) problem, the input is an nvertex undirected graph G and a weight function w: V(G) → ℕ, and the objective is to find a minimum weight subset S of vertices such that GS is a split graph ... 
Approximation in (poly) logarithmic space
Biswas, Arindam; Raman, Venkatesh; Saurabh, Saket (Journal article; Peer reviewed, 2020)We develop new approximation algorithms for classical graph and set problems in the RAM model under space constraints. As one of our main results, we devise an algorithm for d–Hitting Set that runs in time nO(d2+(d/ε)), ... 
Bchromatic number: Beyond NPhardness
Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (Conference object; Peer reviewed; Journal article, 2015)The bchromatic number of a graph G, chi_b(G), is the largest integer k such that G has a kvertex coloring with the property that each color class has a vertex which is adjacent to at least one vertex in each of the other ... 
Balanced judicious bipartition is fixedparameter tractable
Lokshtanov, Daniel; Saurabh, Saket; Sharma, Roohani; Zehavi, Meirav (Journal article; Peer reviewed, 2019)The family of judicious partitioning problems, introduced by Bollobás and Scott to the field of extremal combinatorics, has been extensively studied from a structural point of view for over two decades. This rich realm of ... 
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, ... 
Connecting the Dots (with Minimum Crossings)
Agrawal, Akanksha; Guspiel, Grzegorz; Madathil, Jayakrishnan; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2019)We study a prototype Crossing Minimization problem, defined as follows. Let F be an infinite family of (possibly vertexlabeled) graphs. Then, given a set P of (possibly labeled) n points in the Euclidean plane, a collection ... 
Connecting Vertices by Independent Trees
Basavaraju, Manu; Fomin, Fedor; Golovach, Petr; Saurabh, Saket (Conference object, 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) 
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 and approximate digraph bandwidth
Jain, Pallavi; Kanesh, Lawqueen; Lochet, William; Saurabh, Saket; Sharma, Roohani (Journal article; Peer reviewed, 2019)In this paper, we introduce a directed variant of the classical Bandwidth problem and study it from the viewpoint of moderately exponential time algorithms, both exactly and approximately. Motivated by the definitions of ... 
Fault tolerant subgraphs with applications in kernelization
Lochet, William; Lokshtanov, Daniel; Misra, Pranabendu; Saurabh, Saket; Sharma, Roohani; Zehavi, Meirav (Journal article; Peer reviewed, 2020)In the past decade, the design of fault tolerant data structures for networks has become a central topic of research. Particular attention has been given to the construction of a subgraph H of a given digraph D with as ... 
Finding even subgraphs even faster
Goyal, Prachi; Misra, Pranabendu; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (Conference object; Peer reviewed; Journal article, 2015)Problems of the following kind have been the focus of much recent research in the realm of parameterized complexity: Given an input graph (digraph) on n vertices and a positive integer parameter k, find if there exist k ... 
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, 20190906)An undirected graph G is ddegenerate 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 ... 
Kernel(s) for Problems with No Kernel: On OutTrees with Many Leaves
Fernau, Henning; Fomin, Fedor; Lokshtanov, Daniel; Raible, Daniel; Saurabh, Saket; Villanger, Yngve (Conference object; Peer reviewed; Journal article, 2009)The {\sc \(k\)Leaf OutBranching} problem is to find an outbranching, 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 ... 
On cutwidth parameterized by vertex cover
Cygan, Marek; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal Pawel; Saurabh, Saket (Peer reviewed; Journal article, 201404)We study the CUTWIDTH problem, where the input is a graph G, and the objective is find a linear layout of the vertices that minimizes the maximum number of edges intersected by any vertical line inserted between two ... 
On the parameterized complexity of deletion to Hfree strong components
Neogi, Rian; Ramanujan, M.S.; Saurabh, Saket; Sharma, Roohani (Journal article; Peer reviewed, 2020)Directed Feedback Vertex Set (DFVS) is a fundamental computational problem that has received extensive attention in parameterized complexity. In this paper, we initiate the study of a wide generalization, the HSCC Deletion ... 
Packing arcdisjoint cycles in tournaments
Bessy, Stephane; Bougeret, Marin; Krithika, R; Sahu, Abhishek; Saurabh, Saket; Thiebaut, Jocelyn; Zehavi, Meirav (Journal article; Peer reviewed, 2019)A tournament is a directed graph in which there is a single arc between every pair of distinct vertices. Given a tournament T on n vertices, we explore the classical and parameterized complexity of the problems of determining ... 
Packing cycles faster than ErdosPosa
Lokshtanov, Daniel; Mouawad, Amer E.; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2019)The Cycle Packing problem asks whether a given undirected graph $G=(V,E)$ contains $k$ vertexdisjoint cycles. Since the publication of the classic ErdösPósa theorem in 1965, this problem received significant attention ...