Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6874679 | Journal of Computer and System Sciences | 2018 | 10 Pages |
Abstract
A vertex-subset graph problem Q defines which subsets of the vertices of an input graph are feasible solutions. A reconfiguration variant of a vertex-subset problem asks, given two feasible solutions of size k, whether it is possible to transform one into the other by a sequence of vertex additions/deletions such that each intermediate set remains a feasible solution of size bounded by k. We study reconfiguration variants of two classical vertex-subset problems, namely Independent Set and Dominating Set. We denote the former by and the latter by . Both and are PSPACE-complete on graphs of bounded bandwidth and W[1]-hard parameterized by k on general graphs. We show that is fixed-parameter tractable parameterized by k when the input graph is of bounded degeneracy or nowhere dense. For , we show the problem fixed-parameter tractable parameterized by k when the input graph does not contain large bicliques.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, M.S. Ramanujan, Saket Saurabh,