<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T12:14:33Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/9470" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/9470</identifier><datestamp>2017-03-21T15:13:41Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="5114038c-3b2f-4887-a6b7-31e598d64d36" confidence="600">Tebbal, Youcef</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2015-07-15T20:09:20Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2015-07-15T20:09:20Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2015-07-15</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2015</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/9470</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">A graph problem P is a vertex-subset problem if feasible solutions for P consist of&#xd;
subsets of the vertices of a graph G. The st-connectivity problem for a vertex-subset&#xd;
problem P takes as input two feasible solutions S_s and S_t, and determines if there is a&#xd;
sequence of recon figuration steps that can be applied to transform S_s into S_t, such that&#xd;
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&#xd;
Reconfiguration, whose decision problems&amp;apos; complexity for restricted graph classes is&#xd;
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&#xd;
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-&#xd;
configuration problem is linear-time solvable for paths, trees, bipartite graphs, chordal&#xd;
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&#xd;
bipartite graphs, and PSPACE-complete in general. Finally, we determine that the Dominating Set Reconfiguration problem is linear-time solvable for paths, cographs,&#xd;
trees, and interval graphs. Furthermore, we show that the problem is PSPACE-complete for general graphs, bipartite graphs, and split graphs.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">reconfiguration</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">On the Complexity of Reconfiguration of Clique, Cluster Vertex Deletion, and Dominating Set</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>