Header menu link for other important links
X
Reconfiguration on sparse graphs
D. Lokshtanov, A.E. Mouawad, , M.S. Ramanujan, S. Saurabh
Published in Academic Press Inc.
2018
Volume: 95
   
Pages: 122 - 131
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 [Figure presented] and the latter by [Figure presented]. Both [Figure presented] and [Figure presented] are PSPACE-complete on graphs of bounded bandwidth and W[1]-hard parameterized by k on general graphs. We show that [Figure presented] is fixed-parameter tractable parameterized by k when the input graph is of bounded degeneracy or nowhere dense. For [Figure presented], we show the problem fixed-parameter tractable parameterized by k when the input graph does not contain large bicliques. © 2018 Elsevier Inc.
About the journal
JournalJournal of Computer and System Sciences
PublisherAcademic Press Inc.
ISSN00220000