11 citations · 35 across the 50 of their papers we have counts for
95 papers
Collision-free Movement on Grids and Beyond
Hendrik Molter, Meirav Zehavi
We study collision-free movement problems on graphs, where the task is to coordinate a set of robots so that they reach a target formation satisfying a desired property while minim…
Counting Paths and Trees via Exterior Algebra
Fahad Panolan, Saket Saurabh, Meirav Zehavi +1
We give randomized approximation algorithms for counting k-paths and k-forests in a host graph. Here k denotes the number of pattern vertices, n and m denote the numbers of host ve…
Fine-Grained Bounds for Courcelle's Theorem
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh +2
Courcelle's theorem states that there exists an algorithm that takes as input a graph of treewidth at most and a MSO formula , and determines whether satisfies i…
Minimum Temporal Spanners in Happy Graphs
Arnaud Casteigts, Hendrik Molter, Michelle Döring +1
Temporal graphs are graphs whose edge set changes over discrete time steps. These graphs can model scenarios related to transportation, scheduling, social networks, and networking…
When agents choose bundles autonomously: guarantees beyond discrepancy
Sushmita Gupta, Pallavi Jain, Sanjay Seetharaman +1
We consider the fair division of indivisible items among agents with additive non-negative normalized valuations, with the goal of obtaining high value guarantees, that is, clo…
FPT Approximations for Connected Maximum Coverage
Tanmay Inamdar, Satyabrata Jana, Madhumita Kundu +3
We revisit connectivity-constrained coverage through a unifying model, Partial Connected Red-Blue Dominating Set. Given a red-blue bipartite graph and an auxiliary connectivity…
Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs
Jie Gao, Pawel Gawrychowski, Panos Giannopoulos +4
A \emph{disk graph} is the intersection graph of (closed) disks in the plane. We consider the classic problem of finding a maximum clique in a disk graph. For general disk graphs,…
Tight Parameterized (In)tractability of Layered Crossing Minimization: Subexponential Algorithms and Kernelization
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar +2
The starting point of our work is a decade-old open question concerning the subexponential parameterized complexity of \textsc{2-Layer Crossing Minimization}. In this problem, the…
A Parameterized Perspective on Uniquely Restricted Matchings
Juhi Chaudhary, Ignasi Sau, Meirav Zehavi
Given a graph G, a matching is a subset of edges of G that do not share an endpoint. A matching M is uniquely restricted if the subgraph induced by the endpoints of the edges of M…
On Kernelization with Access to NP-Oracles
Hendrik Molter, Meirav Zehavi
Kernelization is the standard framework to analyze preprocessing routines mathematically. Here, in terms of efficiency, we demand the preprocessing routine to run in time polynomia…
A Simple Algorithm for Combinatorial n-Fold ILPs Using the Steinitz Lemma
Sushmita Gupta, Pallavi Jain, Sanjay Seetharaman +1
We present an algorithm for a class of -fold ILPs whose existing algorithms in literature are often either (1) based on the \textit{augmentation framework} where one starts with…
What makes an Ensemble (Un) Interpretable?
Shahaf Bassan, Guy Amir, Meirav Zehavi +1
Ensemble models are widely recognized in the ML community for their limited interpretability. For instance, while a single decision tree is considered interpretable, ensembles of t…
Tournament Robustness via Redundancy
Klim Efremenko, Hendrik Molter, Meirav Zehavi
A knockout tournament is one of the most simple and popular forms of competition. Here, we are given a binary tournament tree where all leaves are labeled with seed position names.…
Learning Small Decision Trees with Few Outliers: A Parameterized Perspective
Harmender Gahlawat, Meirav Zehavi
Decision trees are a fundamental tool in machine learning for representing, classifying, and generalizing data. It is desirable to construct ``small'' decision trees, by minimizing…
(Almost-)Optimal FPT Algorithm and Kernel for -Cycle on Planar Graphs
Harmender Gahlawat, Abhishek Rathod, Meirav Zehavi
Research of cycles through specific vertices is a central topic in graph theory. In this context, we focus on a well-studied computational problem, \textsc{-Cycle}: given an und…
Treewidth Parameterized by Feedback Vertex Number
Hendrik Molter, Meirav Zehavi, Amit Zivan
We provide the first algorithm for computing an optimal tree decomposition for a given graph that runs in single exponential time in the feedback vertex number of , that is,…
Adaptive Manipulation for Coalitions in Knockout Tournaments
Juhi Chaudhary, Hendrik Molter, Meirav Zehavi
Knockout tournaments, also known as single-elimination or cup tournaments, are a popular form of sports competitions. In the standard probabilistic setting, for each pairing of pla…
Parameterized Geometric Graph Modification with Disk Scaling
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar +2
The parameterized analysis of graph modification problems represents the most extensively studied area within Parameterized Complexity. Given a graph and an integer $k\in\mathb…
Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
Daniel Lokshtanov, Paweł Rzążewski, Saket Saurabh +2
In this article we show that Maximum Partial List H-Coloring is polynomial-time solvable on P_5-free graphs for every fixed graph H. In particular, this implies that Maximum k-Colo…
Exact Algorithms for Clustered Planarity with Linear Saturators
Giordano Da Lozzo, Robert Ganian, Siddharth Gupta +3
We study Clustered Planarity with Linear Saturators, which is the problem of augmenting an -vertex planar graph whose vertices are partitioned into independent sets (called clus…
A Polynomial Kernel for Deletion to the Scattered Class of Cliques and Trees
Ashwin Jacob, Diptapriyo Majumdar, Meirav Zehavi
The class of graph deletion problems has been extensively studied in theoretical computer science, particularly in the field of parameterized complexity. Recently, a new notion of…
Subexponential Parameterized Algorithms for Hitting Subgraphs
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh +2
For a finite set of graphs, the -Hitting problem aims to compute, for a given graph (taken from some graph class ) of vertices (and…
Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh +2
In a disk graph, every vertex corresponds to a disk in and two vertices are connected by an edge whenever the two corresponding disks intersect. Disk graphs form an…
Hybrid k-Clustering: Blending k-Median and k-Center
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar +2
We propose a novel clustering model encompassing two well-known clustering models: k-center clustering and k-median clustering. In the Hybrid k-Clusetring problem, given a set P of…