On the Complexity of Reconfiguration of Clique, Cluster Vertex Deletion, and Dominating Set

reconfiguration;Computer Science

Tebbal, Youcef

University of Waterloo

关键词: reconfiguration;    Computer Science;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/9470/1/Tebbal_Youcef.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

A graph problem P is a vertex-subset problem if feasible solutions for P consist ofsubsets of the vertices of a graph G. The st-connectivity problem for a vertex-subsetproblem P takes as input two feasible solutions S_s and S_t, and determines if there is asequence of recon figuration steps that can be applied to transform S_s into S_t, such thateach 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 SetReconfiguration, whose decision problems;; complexity for restricted graph classes isextensively 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 whosedecision 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, chordalgraphs, 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 onbipartite 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.