14 citations · 69 across the 31 of their papers we have counts for
Showing 2017Show all
3 papers · 1 filter
cs.CC2017
The complexity of independent set reconfiguration on bipartite graphs
Daniel Lokshtanov, Amer E. Mouawad
We settle the complexity of the Independent Set Reconfiguration problem on bipartite graphs under all three commonly studied reconfiguration models. We show that under the token ju…
cs.DS2017
Packing Cycles Faster Than Erdős-Pósa
Daniel Lokshtanov, Amer E. Mouawad, Saket Saurabh +1
The Cycle Packing problem asks whether a given undirected graph contains vertex-disjoint cycles. Since the publication of the classic Erdős-Pósa theorem in 1965, this…
cs.DS2017
Lossy Kernels for Connected Dominating Set on Sparse Graphs
Eduard Eiben, Mithilesh Kumar, Amer E. Mouawad +2
For , an -approximate (bi-)kernel is a polynomial-time algorithm that takes as input an instance of a problem and outputs an instance (of…