12 citations · 12 across the 4 of their papers we have counts for
9 papers · 1 filter
On Sparse Hitting Sets: from Fair Vertex Cover to Highway Dimension
Johannes Blum, Yann Disser, Andreas Emil Feldmann +2
We consider the Sparse Hitting Set (Sparse-HS) problem, where we are given a set system with two families of subsets of .…
Grid Recognition: Classical and Parameterized Computational Perspectives
Siddharth Gupta, Guy Sa'ar, Meirav Zehavi
Grid graphs, and, more generally, grid graphs, form one of the most basic classes of geometric graphs. Over the past few decades, a large body of works studied the (in)…
How to Catch Marathon Cheaters: New Approximation Algorithms for Tracking Paths
Michael T. Goodrich, Siddharth Gupta, Hadi Khodabandeh +1
Given an undirected graph, , and vertices, and in , the tracking paths problem is that of finding the smallest subset of vertices in whose intersection with any $…
Multivariate Analysis of Scheduling Fair Competitions
Siddharth Gupta, Meirav Zehavi
A \emph{fair competition}, based on the concept of envy-freeness, is a non-eliminating competition where each contestant (team or individual player) may not play against all other…
Parameterized Complexity of Finding Subgraphs with Hereditary Properties on Hereditary Graph Classes
David Eppstein, Siddharth Gupta, Elham Havvaei
We investigate the parameterized complexity of finding subgraphs with hereditary properties on graphs belonging to a hereditary graph class. Given a graph , a non-trivial heredi…
The Parameterized Complexity of Motion Planning for Snake-Like Robots
Siddharth Gupta, Guy Sa'ar, Meirav Zehavi
We study the parameterized complexity of a variant of the classic video game Snake that models real-world problems of motion planning. Given a snake-like robot with an initial posi…