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

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 ... 
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) 
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 ... 
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 (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 ... 
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 ... 
Parameterized complexity classification of deletion to list matrixpartition for loworder matrices
Agrawal, Akanksha; Kolay, Sudeshna; Madathil, Jayakrishnan; Saurabh, Saket (Journal article; Peer reviewed, 2019)Given a symmetric l x l matrix M=(m_{i,j}) with entries in {0,1,*}, a graph G and a function L : V(G)  > 2^{[l]} (where [l] = {1,2,...,l}), a list Mpartition of G with respect to L is a partition of V(G) into l parts, ... 
Parameterized complexity of conflictfree matchings and paths
Agrawal, Akanksha; Jain, Pallavi; Kanesh, Lawqueen; Saurabh, Saket (Journal article; Peer reviewed, 2019)An input to a conflictfree variant of a classical problem Gamma, called ConflictFree Gamma, consists of an instance I of Gamma coupled with a graph H, called the conflict graph. A solution to ConflictFree Gamma in (I,H) ... 
Parameterized SingleExponential Time Polynomial Space Algorithm for Steiner Tree
Fomin, Fedor; Kaski, Petteri; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket (Peer reviewed; Journal article, 2019)In the Steiner Tree problem, we are given as input a connected \(n\)vertex graph with edge weights in \(\{1,2,\ldots,W\}\), and a set of \(k\) terminal vertices. Our task is to compute a minimumweight tree that contains ... 
Parameterized streaming algorithms for minones dSAT
Agrawal, Akanksha; Bonnet, Édouard; Curticapean, Radu; Miltzow, Tillmann; Saurabh, Saket; Biswas, Arindam; Brettell, Nick; Marx, Dániel; Raman, Venkatesh (Journal article; Peer reviewed, 2019)In this work, we initiate the study of the MinOnes dSAT problem in the parameterized streaming model. An instance of the problem consists of a dCNF formula F and an integer k, and the objective is to determine if F has ... 
Path Contraction Faster Than 2n
Agrawal, Akanksha; Fomin, Fedor; Lokshtanov, Daniel; Saurabh, Saket; Tale, Prafullkumar (Peer reviewed; Journal article, 2019)A graph G is contractible to a graph H if there is a set X subseteq E(G), such that G/X is isomorphic to H. Here, G/X is the graph obtained from G by contracting all the edges in X. For a family of graphs F, the FContraction ... 
Quick but odd growth of cacti
Kolay, Sudeshna; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket (Conference object; Peer reviewed; Journal article, 2015)Let F be a family of graphs. Given an input graph G and a positive integer k, testing whether G has a ksized subset of vertices S, such that G\S belongs to F, is a prototype vertex deletion problem. These type of problems ... 
Rank vertex cover as a natural problem for algebraic compression
Meesum, Syed Mohammad; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2019)The question of the existence of a polynomial kernelization of the Vertex Cover Above LP problem was a longstanding, notorious open problem in parameterized complexity. Some years ago, the breakthrough work by Kratsch and ...