11 citations · 35 across the 50 of their papers we have counts for
18 papers · 1 filter
Collective Graph Exploration Parameterized by Vertex Cover
Siddharth Gupta, Guy Sa'ar, Meirav Zehavi
We initiate the study of the parameterized complexity of the {\sc Collective Graph Exploration} ({\sc CGE}) problem. In {\sc CGE}, the input consists of an undirected connected gra…
Drawn Tree Decomposition: New Approach for Graph Drawing Problems
Siddharth Gupta, Guy Sa'ar, Meirav Zehavi
Over the past decade, we witness an increasing amount of interest in the design of exact exponential-time and parameterized algorithms for problems in Graph Drawing. Unfortunately,…
Parameterized Complexity of Incomplete Connected Fair Division
Harmender Gahlawat, Meirav Zehavi
\textit{Fair division} of resources among competing agents is a fundamental problem in computational social choice and economic game theory. It has been intensively studied on vari…
Kernels for the Disjoint Paths Problem on Subclasses of Chordal Graphs
Juhi Chaudhary, Harmender Gahlawat, Michal Włodarczyk +1
Given an undirected graph and a multiset of terminal pairs , the Vertex-Disjoint Paths (\VDP) and Edge-Disjoint Paths (\EDP) problems ask whether has p…
Sidestepping Barriers for Dominating Set in Parameterized Complexity
Ioannis Koutis, Michał Włodarczyk, Meirav Zehavi
We study the classic {\sc Dominating Set} problem with respect to several prominent parameters. Specifically, we present algorithmic results that sidestep time complexity barriers…
How to Make Knockout Tournaments More Popular?
Juhi Chaudhary, Hendrik Molter, Meirav Zehavi
Given a mapping from a set of players to the leaves of a complete binary tree (called a seeding), a knockout tournament is conducted as follows: every round, every two players with…
Kernelization for Spreading Points
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar +2
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,…
Finding Long Directed Cycles Is Hard Even When DFVS Is Small Or Girth Is Large
Ashwin Jacob, Michał Włodarczyk, Meirav Zehavi
We study the parameterized complexity of two classic problems on directed graphs: Hamiltonian Cycle and its generalization {\sc Longest Cycle}. Since 2008, it is known that Hamilto…
Lossy Kernelization for (Implicit) Hitting Set Problems
Fedor V. Fomin, Tien-Nam Le, Daniel Lokshtanov +3
We re-visit the complexity of kernelization for the -Hitting Set problem. This is a classic problem in Parameterized Complexity, which encompasses several other of the most well…
Kernelization of Counting Problems
Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh +1
We introduce a new framework for the analysis of preprocessing routines for parameterized counting problems. Existing frameworks that encapsulate parameterized counting problems pe…
Meta-theorems for Parameterized Streaming Algorithms
Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan +3
The streaming model was introduced to parameterized complexity independently by Fafianie and Kratsch [MFCS14] and by Chitnis, Cormode, Hajiaghayi and Monemizadeh [SODA15]. Subseque…
-matchings Parameterized by Treewidth
Juhi Chaudhary, Meirav Zehavi
A \emph{matching} is a subset of edges in a graph that do not share an endpoint. A matching is a \emph{-matching} if the subgraph of induced by the endpoin…
Planar Disjoint Paths, Treewidth, and Kernels
Michał Włodarczyk, Meirav Zehavi
In the Planar Disjoint Paths problem, one is given an undirected planar graph with a set of vertex pairs and the task is to find pairwise vertex-disjoint paths…
Parameterized Results on Acyclic Matchings with Implications for Related Problems
Juhi Chaudhary, Meirav Zehavi
A matching in a graph is an \emph{acyclic matching} if the subgraph of induced by the endpoints of the edges of is a forest. Given a graph and a positive intege…
Parameterized Analysis of the Cops and Robber Problem
Harmender Gahlawat, Meirav Zehavi
\textit{Pursuit-evasion games} have been intensively studied for several decades due to their numerous applications in artificial intelligence, robot motion planning, database theo…
Efficient Approximation for Subgraph-Hitting Problems in Sparse Graphs and Geometric Intersection Graphs
Zdeněk Dvořák, Daniel Lokshtanov, Fahad Panolan +3
We investigate a fundamental vertex-deletion problem called (Induced) Subgraph Hitting: given a graph and a set of forbidden graphs, the goal is to compute a mini…
In Which Graph Structures Can We Efficiently Find Temporally Disjoint Paths and Walks?
Pascal Kunz, Hendrik Molter, Meirav Zehavi
A temporal graph has an edge set that may change over discrete time steps, and a temporal path (or walk) must traverse edges that appear at increasing time steps. Accordingly, two…
Long Directed Detours: Reduction to -Disjoint Paths
Ashwin Jacob, Michał Włodarczyk, Meirav Zehavi
We study an "above guarantee" version of the {\sc Longest Path} problem in directed graphs: We are given a graph , two vertices and of , and a non-negative integer $k…