Reconfiguration on sparse graphs
From MaRDI portal
Publication:1747496
DOI10.1007/978-3-319-21840-3_42zbMATH Open1390.68351arXiv1502.04803OpenAlexW2795775903WikidataQ130028149 ScholiaQ130028149MaRDI QIDQ1747496
Author name not available (Why is that?)
Publication date: 8 May 2018
Published in: (Search for Journal in Brave)
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 S and T of size k, whether it is possible to transform S into T by a sequence of vertex additions and deletions such that each intermediate set is also 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 ISR and the latter by DSR. Both ISR and DSR are PSPACE-complete on graphs of bounded bandwidth and W[1]-hard parameterized by k on general graphs. We show that ISR is fixed-parameter tractable parameterized by k when the input graph is of bounded degeneracy or nowhere-dense. As a corollary, we answer positively an open question concerning the parameterized complexity of the problem on graphs of bounded treewidth. Moreover, our techniques generalize recent results showing that ISR is fixed-parameter tractable on planar graphs and graphs of bounded degree. For DSR, we show the problem fixed-parameter tractable parameterized by k when the input graph does not contain large bicliques, a class of graphs which includes graphs of bounded degeneracy and nowhere-dense graphs.
Full work available at URL: https://arxiv.org/abs/1502.04803
No records found.
No records found.
This page was built for publication: Reconfiguration on sparse graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1747496)
