On the Complexity of Reconfiguration of Clique, Cluster Vertex Deletion, and Dominating Set
Abstract
A graph problem P is a vertex-subset problem if feasible solutions for P consist of
subsets of the vertices of a graph G. The st-connectivity problem for a vertex-subset
problem P takes as input two feasible solutions S_s and S_t, and determines if there is a
sequence of recon figuration steps that can be applied to transform S_s into S_t, such that
each step results in a feasible solution of P of size bounded by k and each step is a vertex addition or deletion. For most NP-complete problems, this problem has been shown to be PSPACE-complete, while for some problems in P, this problem could be either in P or PSPACE-complete. However, knowing the complexity of a decision problem does not directly imply the complexity of its st-connectivity problem. Therefore, it is natural to ask whether we can fi nd a connection between the complexity of a decision problem and its st-connectivity problem when restricted to graph classes. This question motivated us to study the st-connectivity problems Clique Reconfiguration and Dominating Set
Reconfiguration, whose decision problems' complexity for restricted graph classes is
extensively studied, to get a better understanding of the boundary between polynomial-time solvable and intractable instances of these reconfi guration problems. Furthermore, we study the Cluster Vertex Deletion Reconfiguration problem, a problem whose
decision problem is related to the Clique problem, to fi nd whether there is a connection between the complexity of this problem and the Clique Reconfiguration problem. Following are the main contributions of this thesis. First, we show that the Clique Re-
configuration problem is linear-time solvable for paths, trees, bipartite graphs, chordal
graphs, and cographs. Then, we prove that the Cluster Vertex Deletion Reconfiguration problem is linear-time solvable for paths and trees, and that it is NP-hard on
bipartite graphs, and PSPACE-complete in general. Finally, we determine that the Dominating Set Reconfiguration problem is linear-time solvable for paths, cographs,
trees, and interval graphs. Furthermore, we show that the problem is PSPACE-complete for general graphs, bipartite graphs, and split graphs.
Collections
Cite this version of the work
Youcef Tebbal
(2015).
On the Complexity of Reconfiguration of Clique, Cluster Vertex Deletion, and Dominating Set. UWSpace.
http://hdl.handle.net/10012/9470
Other formats