13 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…
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 …
Polynomial Kernels for Spanning Tree with Diversity Requirements
Petr A. Golovach, Diptapriyo Majumdar, Saket Saurabh
Given a connected undirected graph , a spanning tree is a subgraph of such that and is a tree. A collection of spanning trees $T_1,\ldots,T_\ell…
Dominating Set with Quotas: Balancing Coverage and Constraints
Sobyasachi Chatterjee, Sushmita Gupta, Saket Saurabh +2
We study a natural generalization of the classical \textsc{Dominating Set} problem, called \textsc{Dominating Set with Quotas} (DSQ). In this problem, we are given a graph \( G \),…
Algorithms for Euclidean Distance Matrix Completion: Exploiting Proximity to Triviality
Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan +1
In the d-Euclidean Distance Matrix Completion (d-EDMC) problem, one aims to determine whether a given partial matrix of pairwise distances can be extended to a full Euclidean dista…
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…