From the 1 of 22 linked papers with an AI index.
22 papers
Courcelle's Theorem in Truly Linear FPT
Tuukka Korhonen, Daniel Lokshtanov, Saket Saurabh
The paper develops a general technique for obtaining truly linear fixed‑parameter tractable (TLFPT) algorithms when parameterized by treewidth, providing a TLFPT version of Courcel…
Covering Points with Rectangular Boundaries
Madhumita Kundu, Daniel Lokshtanov, Soumi Nandi +2
Geometric covering problems ask for a small family of geometric objects whose union covers a given point set. We study the more restrictive \emph{boundary covering} variant, where…
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 …
(Treewidth, Clique)-Boundedness and Poly-logarithmic Tree-Independence
Maria Chudnovsky, Ajaykrishnan E S, Daniel Lokshtanov
An independent set in a graph is a set of pairwise non-adjacent vertices. A tree decomposition of is a pair where is a tree and $Ï: V(T) \rightarrow 2^{V(G)}…
Parameterized Approximation of Rectangle Stabbing
Huairui Chu, Ajaykrishnan E S, Daniel Lokshtanov +4
In the Rectangle Stabbing problem, input is a set of axis-parallel rectangles and a set of axis parallel lines in the plane. The task is to find a minimum siz…
Induced minors and subpolynomial treewidth
Maria Chudnovsky, Julien Codsi, David Fischer +1
Given a family of graphs, we say that a graph is -induced-minor-free if no induced minor of is isomorphic to a member of , We denote…