11 citations · 35 across the 50 of their papers we have counts for
10 papers · 1 filter
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,…