Browsing Department of Informatics by Author "Zehavi, Meirav"
Now showing items 114 of 14

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 ... 
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 ... 
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 ... 
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 ... 
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 ... 
Parameterization Above a Multiplicative Guarantee
Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2020)Parameterization above a guarantee is a successful paradigm in Parameterized Complexity. To the best of our knowledge, all fixedparameter tractable problems in this paradigm share an additive form defined as follows. Given ... 
The Parameterized Complexity of Guarding Almost Convex Polygons
Agrawal, Akanksha; Knudsen, Kristine Vitting Klinkby; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2020)The Art Gallery problem is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an integer k; the task is to decide ... 
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 ... 
Subquadratic Kernels for Implicit 3Hitting Set and 3Set Packing Problems
Fomin, Fedor; Le, TienNam; Lokshtanov, Daniel; Saurabh, Saket; Thomasse, Stephan; Zehavi, Meirav (Peer reviewed; Journal article, 2019)We consider four wellstudied NPcomplete packing/covering problems on graphs: Feedback Vertex Set in Tournaments (FVST), Cluster Vertex Deletion (CVD), Triangle Packing in Tournaments (TPT) and Induced P3Packing. For ...