7 citations · 14 across the 41 of their papers we have counts for
63 papers · 1 filter
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, Meirav Zehavi
Temporal graphs have edge sets that change over discrete time steps. Such graphs are temporally connected (TC) if all pairs of vertices can reach each other using paths that traver…
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…
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…