Complexity of Reconfiguration Problems for Constraint Satisfaction
Tatsuhiko Hatanaka Takehiro Ito Xiao Zhou


CMB lensing  bi-spectrum: assessing analytical predictions against full-sky lensing simulations
    Atsushi Taruya
    December 30, 2023
===============================================================================================




	Constraint satisfaction problem (CSP) is a well-studied combinatorial search problem, in which we are asked to find an assignment of values to given variables so as to satisfy all of given constraints.
	We study a reconfiguration variant of CSP, in which we are given an instance of CSP together with its two satisfying assignments, and asked to determine whether one assignment can be transformed into the other by changing a single variable assignment at a time, while always remaining satisfying assignment.
	This problem generalizes several well-studied reconfiguration problems such as Boolean satisfiability reconfiguration, vertex coloring reconfiguration, homomorphism reconfiguration.
	In this paper, we study the problem from the viewpoints of polynomial-time solvability and parameterized complexity, and give several interesting boundaries of tractable and intractable cases. 
 



§ INTRODUCTION


	Recently, the framework of reconfiguration <cit.> has been extensively studied in the field of theoretical computer science.
	This framework models several “dynamic” situations where we wish to find a step-by-step transformation between two feasible solutions of a combinatorial (search) problem such that all intermediate solutions are also feasible and each step respects a fixed reconfiguration rule.
	This reconfiguration framework has been applied to several well-studied combinatorial problems.
	(See surveys <cit.>.)



	As an example, we consider the (vertex) coloring reconfiguration problem <cit.>, which is one of the most well-studied reconfiguration problems.
	Let G=(V,E) be a graph and let  be a set of  colors.
	A -coloring of G is a mapping V → such that (v)(w) holds for every edge vw∈ E.
	In the reconfiguration framework, we wish to transform one -coloring into another one by recoloring a single vertex at a time, while always remaining -coloring.
	(See  <ref> for example.)



	
	In this paper, we study a reconfiguration variant of the well-known constraint satisfaction problem (CSP, for short), which is a generalization of several combinatorial problems including vertex coloring, Boolean satisfiability, graph homomorphism.
	The formal definitions of CSP and its reconfiguration variant will be given in Section <ref>, but we here briefly introduce them.
	Let G=(V,) be a hypergraph.
	Let  be a set, called a domain; each element of  is called a value and we always denote by  the size of a domain.

	In CSP, each hyperedge X∈ has a constraint which represents the values allowed to be assigned to the vertices in X at the same time, and we wish to find a mapping V → which satisfies the constraints of all hyperedges in G. 
	(See  <ref> for an example.)







	In the case of vertex coloring, we can see that every hyperedge consists of two vertices, and has the common constraint that any two different colors can be assigned to the two vertices in the hyperedge at the same time.  





	In the reconfiguration framework for CSP, we are given a CSP instance together with its two mappings satisfying all constraints, and we wish to transform one mapping into the other by changing a value of a single vertex at a time, while always satisfying all constraints.
	
	The reconfiguration problem for CSP has been studied as several spacial cases such as 
		Boolean constraint satisfiability reconfiguration <cit.>, 
		homomorphism reconfiguration <cit.>, 
		and (list) coloring reconfiguration <cit.>.
	We will briefly summarize these results in the next section.
	
	In this paper, we study the reconfiguration problem for CSP and its special cases from the viewpoints of polynomial-time solvability and parameterized complexity, and give several interesting boundaries of tractable and intractable cases.
	Our results are roughly summarized as follows:
	We first investigate the complexity of the problem with respect to the size  of a domain (summarized in  <ref>).
	We next analyze the (parameterized) complexities with respect to the structure of an input hypergraph (summarized in s <ref> and <ref>).
	We finally explore the boundary of time complexity of the problem; we give some exact algorithms, and a lower bound of the computation time that meets the running times of our algorithms under the exponential time hypothesis.



§ PROBLEM DEFINITION AND RESULTS





 §.§ Our problem


	In this subsection, we formally define CSP and its reconfiguration variant by means of hypergraphs.
	
	We first give some terminologies regarding hypergraphs and mappings.	
	A hypergraph G is a pair (V,), where V is a set of vertices and  is a family of non-empty vertex subsets, called hyperedges.
	A hypergraph G is r-uniform if every hyperedge consists of exactly r (≥ 1) vertices.	
	Sometimes, a 2-uniform hypergraph G is simply called a graph and each hyperedge of G is called an edge.
	An edge {v,w} is sometimes denoted by vw or wv for notational convenience.
	Let A and B be any sets.
	We denote by B^A the set of all mappings from A to B, because we can identify a mapping ϕ A → B with a vector (ϕ(a_1), ϕ(a_2), …, ϕ(a_|A|)) ∈ B^|A|, where A={a_1,a_2,…,a_|A|}.
	Let ϕ∈ B^A be a mapping.



	For any subset A^' of A, we denote by ϕA^' the restriction of ϕ on A^'; that is, ϕA^' is a mapping in B^A^' such that ϕA^'(a)=ϕ(a) for any a∈ A^'.
	
	We next define CSP and give some notation.
	Let G=(V,) be a hypergraph.
	Let  be a set, called a domain; each element of  is called a value and we always denote by  the size (cardinality) of a domain.
	In CSP, each hyperedge X∈ has a set (X) ⊆^X; we call (X) a constraint of X.
	If (X)=^X, it is called a trivial constraint.
	The arity of a constraint (X) of X is exactly |X|, and we call (X) an -ary constraint, where =|X|.
	We define the constraint (G) of G as the union of all constraints of hyperedges, that is, (G)=⋃_X∈ E(G)(X).
	For a vertex v∈ V(G), a list (v) of v is the set {i∈∃∈(G), (v)=i}.
	For a hyperedge X∈, we say that a mapping ∈^V satisfies a constraint of X if X∈(X) holds.
	 is a solution if it satisfies all constraints.
	
	An instance of constraint satisfiability is a triple (G,,) consisting of a hypergraph G, a domain , and a constraint assignment to hyperedges over .
	Then, the problem asks whether there exists a solution or not.
	Constraint satisfiability includes many combinatorial problems as its special cases as follows.
	
		
  * Boolean constraint satisfiability is the special case of constraint satisfiability where ||=2.
		
  * For an integer ≥ 1, -ary constraint satisfiability is the special case of constraint satisfiability where all constraints are of arity at most , that is, all hyperedges have size at most .
		
  * List homomorphism is the special case of 2-ary constraint satisfiability where G is a 2-uniform hypergraph (i.e., a graph) and there exists a simple undirected graph H with a vertex set , called an  graph[
			In this paper, we only consider simple undirected  graphs, although loops and/or directed edges are often allowed in researches related to graph homomorphisms.], 
		such that (vw)=E(H)∩((v) ×(w)) holds for every edge vw∈ E(G), where (v) and (w) are lists of v and w, respectively.
		In other words, (vw) is the set of all homomorphisms from the edge vw to H which respect the lists of v and w.
		
  * Homomorphism is the special case of list homomorphism where (v)= holds for every vertex v∈ V(G).
		
  * (List) coloring is the special case of (list) homomorphism where an  graph H is complete, that is, (vw) is a set of all injective mappings from {v,w} to  (which respect the lists of v and w).
	
	
	We then define a reconfiguration variant of constraint satisfiability, that is, constraint satisfiability reconfiguration.
	Let  and ^' be two solutions for an instance =(G,,) of 0.
	We define the difference ^' between  and ^' as the set {v∈ V(G)(v) ^'(v) }.
	We now define the solution graph  for  as follows.
	V() is the set of all solutions for , and two solutions  and ^' are connected by an edge if and only if |^'|=1.
	A walk in  is called a reconfiguration sequence.
	Two solutions  and ^' are reconfigurable if and only if there exists a reconfiguration sequence between them.
	
	An instance of constraint satisfiability reconfiguration (0 for short) is a 5-tuple (G,,,_,_), where (G,,) is an instance of constraint satisfiability, and _ and _ are two solutions to (G,,), called initial and target solutions.
	Then, the problem asks whether _ and _ are reconfigurable or not.
	Similarly, for each special case P of constraint satisfiability, we define “P reconfiguration” as a special case of 0.
	We use the following abbreviations:
	
		
  *  for Boolean constraint satisfiability reconfiguration;
		
  *  for -ary constraint satisfiability reconfiguration for each integer ≥ 1;
		
  * (L) for (list) homomorphism reconfiguration; and
		
  * (L) for (list) coloring reconfiguration.
	
	Relationships between problems are illustrated in  <ref>(a).
	
	
	



 §.§ Known and related results

	
	There are many literatures which study special cases of 0 and their shortest variants.
	In the shortest variant, we are given an instance with an integer ℓ≥ 0, and asked whether there exists a reconfiguration sequence of length at most ℓ.
	We here state only the results from the viewpoint of the computational complexity.
	
	One of the most well-studied special cases of 0 is  <cit.>.
	Gopalan et al. <cit.> gave a computational dichotomy for  with respect to a set  of logical relations which can be used to define each constraint;
	the problem is PSPACE-complete or in P for each fixed .
	In addition, Cardinal et al. <cit.> showed that the problem remains PSPACE-complete even if  is equivalent to monotone Not-All-Equal 3-SAT (i.e., each constraint is a set of surjections) and a “variable-clause incidence graph” is planar.
	For the shortest variant, a computational trichotomy is known; Mouawad et al. <cit.> proved that the problem is PSPACE-complete, NP-complete or in P for each fixed .
	Bonsma et al. <cit.> proved that the shortest variant is W[2]-hard when parameterized by ℓ even if  is equivalent to Horn SAT.
	
	Another well-studied spacial case is  <cit.>.
	This problem is PSPACE-complete for ≥ 4 and bipartite planar graphs <cit.> but in P for ≤ 3 <cit.>.
	We note that these results (including tractability one) can be extended for L.
	Moreover, it is known that the problem remains PSPACE-complete even if  is a fixed constant for several graph classes such as line graphs (for any fixed ≥ 5) <cit.>, bounded bandwidth graphs <cit.>, and chordal graphs <cit.>.
	On the other hand, several polynomial-time algorithms are known for subclasses of chordal graphs such as trivially perfect graphs, split graphs <cit.>, and (-2)-connected chordal graphs <cit.>.
	For the shortest variant parameterized by ℓ, some intractability results are known;
	it is W[1]-hard <cit.> and does not admit a polynomial kernelization when  is fixed unless the polynomial hierarchy collapses <cit.>.
	
	As a generalization of , L is also studied <cit.>.
	The problem is PSPACE-complete even if  is a constant for graphs with pathwidth two <cit.>, while it is polynomial-time solvable for graphs with pathwidth one <cit.>.

	Hatanaka et al. <cit.> gave fixed-parameter algorithms for L parameterized by + and for the shortest variant parameterized by +.
	In contrast, they also showed that the problem is W[1]-hard when parameterized only by .
	
	 is also well-studied as a generalization of .
	Several literatures investigated  from the viewpoint of graph classes in which a given graph G or an  graph H lies <cit.>.
	Brewster et al. <cit.> gave a dichotomy for a special case of  in which H is a (p,q)-circular clique;
	it is PSPACE-complete if p/q≥ 4 but is in P otherwise.
	We note that this result generalizes the complexity of  with respect to , since a complete graph K_ is a (,1)-circular clique.
	It is also known that the problem is PSPACE-complete even if H is an odd wheel <cit.> or H is some fixed graph and G is a cycle <cit.>.
	On the other hand, it can be solved in polynomial time if G is a tree <cit.> or H contains no cycles of length four as a subgraph <cit.>.
	Furthermore, a fixed-parameter algorithm is known when parameterized by + <cit.>; note that it can be easily extended for L.
	
	Finally, we refer to the shortest variant of 0.
	Bonsma et al. <cit.> gave a fixed-parameter algorithm for the shortest variant parameterized by ++ℓ, where  is the maximum arity of a constraint.
	This implies that shortest variants of  and 2 are fixed-parameter tractable when parameterized by +ℓ and +ℓ, respectively.
	They also showed that the problem is intractable in general if at least one of {,,ℓ} is excluded from the parameter.



 §.§ Our contribution


	In this paper, we investigate the complexity of 0 and its spacial cases, especially 3, 2, (L) and (L), from several viewpoints.



  
*The sizes of a domain and lists





	We first classify the complexity of the problems for each fixed size  of a domain in Section <ref>; recall that  corresponds to the number of colors in (L).
	Together with known results, our results give interesting boundaries of (in)tractability as summarized in  <ref>.
	In particular, our results unravel the boundaries with respect to  for 2 and L.
	The other interesting contrast we show is the boundary between 2 and L for =3.
	This might be caused by the difference of variety of constraints; in L, a constraint is unique for each pair of lists.
	
	We then extend Theorem <ref>, which states that 2 can be solved in polynomial time if =2.
	More precisely, we give a fixed-parameter algorithm with respect to +, where  is the number of vertices whose lists have size more than two.
	Notice that =2 implies that =0, and hence our algorithm generalizes Theorem <ref>.
	Moreover, this result gives the boundary of the complexity of 2 between =3 and =2.
	We also investigate the parameterized complexity when parameterized only by .
	The results are summarized in  <ref>.



  
*Graph parameters





	As mentioned in the previous subsection, , L and  have been studied from the viewpoint of graph parameters.
	In this paper, we extend the notion of graph parameters to hypergraphs by taking a “primal graph.”
	The primal graph G of a hypergraph G is a graph such that V(G)=V(G) and two distinct vertices are connected by an edge if they are contained in the same hyperedge of G.
	Then, we define any graph parameter of a hypergraph G as the parameter of its primal graph G.[
		For example, when we refer to the treewidth of a hypergraph G, it means the treewidth of its primal graph G.
		Note that G=G if G is 2-uniform.]
	Then we can draw s <ref>	and <ref> from this viewpoint; throughout the paper, , ,  and  are the modular-width, the pathwidth, the tree-depth and the size of a minimum vertex cover of a given hypergraph, respectively.
	The relationships between graph parameters are summarized in  <ref>(b); note that tractability (resp., intractability) result propagates downward (resp., upward).
	We extend several known fixed-parameter algorithms to 2 (+), and 0 (+ and +).
	On the other hand, we show that the first one cannot be extended to 2.
	We also note that a fixed-parameter tractability of 0 parameterized by + can be obtained as a corollary of Theorem <ref>.
	However, Theorem <ref> gives a faster algorithm and Theorem <ref> gives an algorithm for the shortest variant.
	


  
*Boundary of time comlexity

	In Section <ref>, we explore the boundary of time complexity of 0.
	We first give an algorithm for 0 running in time O^*(^O(n)), where n is the number of vertices of a given hypergraph, and hence 0 is in the class XP when parameterized by n.
	On the other hand, we prove that  is W[1]-hard when parameterized by n.
	Furthermore, we prove that 2 cannot be solved in time (+n)+n under the exponential time hypothesis (ETH).
	This lower bound matches the running time shown in Theorems <ref>, <ref> and <ref>.	
	
	We move several proofs to Appendices.



 §.§ Preliminary


	
	Let G be a hypergraph, and let v∈ V(G) be a vertex.
	We denote by Gv the set {w  w v, ∃ X∈ E(G), {v,w}⊆ X} of vertices which are adjacent to v.
	For a vertex subset V^'⊆ V(G), we denote GV^':=⋃_v∈ V^'Gv∖ V^'.
	
	Two hypergraphs G and G^' are isomorphic if there exist two bijections V(G) → V(G^') and E(G) → E(G^') such that (X)={(v_1),(v_2),…,(v_)}∈ E(G^') holds for each hyperedge X={v_1,v_2,…,v_}∈ E(G).
	(See  <ref>.)
	
	For a hypergraph G and a vertex subset V^'⊆ V(G), we define the subhypergraph of G induced by V^' as the hypergraph G^' such that V(G^')=V^' and E(G^')={X∩ V^' X∈ E(G), X∩ V^'∅}.
	We denote by G[V^'] the subhypergraph of G induced by V^' for any vertex subset V^'.
	(See  <ref>.)
	We use the notation G∖ V^' to denote G[V(G)∖ V^'].
	
	
	

	We say that two mappings ϕ∈ B^A and ϕ^'∈ B^A^' are compatible if ϕA∩ A^''=ϕ^'A∩ A^'' holds.




	
	Let (G,,) be an instance of 0.
	A Boolean vertex is a vertex v∈ V(G) with |(v)|≤ 2, and a non-Boolean vertex is a vertex v∈ V(G) with |(v)|>2.
	Let X and X^' be hyperedges in E(G) such that |X|=|X^'|.
	For a bijection X→ X^', we denote by (X) the set {∘^-1∈(X)}⊆^X^' of mappings from X^' to ,
	where ∘ means the composition of mappings.
	Intuitively, (X) is a “translation” of (X) into a constraint of X^' via a bijection .
	For example, assume that ({v_1,v_2,v_3}) contains a mapping =(1,2,3).
	If a bijection ϕ{v_1,v_2,v_3}→{u_1,u_2,u_3} maps v_1,v_2,v_3 to u_2,u_1,u_3, respectively, 
	then ({v_1,v_2,v_3}) contains a mapping ^'{u_1,u_2,u_3}→{1,2,3} such that (^'(u_1),^'(u_2),^'(u_3))=(∘^-1(u_1),∘^-1(u_2),∘^-1(u_3))=((v_2),(v_1),(v_3))=(2,1,3).
	
	Let (G,,) be an instance of 2.
	Without loss of generality, we assume that G is connected, |V(G)|≥ 2, and ={0,1}.
	Moreover, we can assume that G is 2-uniform as follows.
	If G contains a size-one hyperedge {v}, there must exist a size-two hyperedge (i.e., an edge) vw∈ E(G) from the assumption.
	Then, we remove {v} from E(G) and replace (vw) with the set of all solutions satisfying ({v}) and (vw).
	Note that this modification does not change the set of solutions and the primal graph.





§ COMPUTATIONAL COMPLEXITY WITH RESPECT TO 



	In this section, we classify the complexity of the problems for each fixed size  of a domain.
	
		
		2 is PSPACE-complete for bipartite planar graphs even if =3.
	
	
		We give a polynomial-time reduction from L to 2.
		It is known that L is PSPACE-complete for bipartite planar graphs even if each list has size at most three <cit.>.
		Let =(G,,,_,_) be such an instance of L, and let  is a list assignment.
		Without loss of generality, we assume that ={1,2,3,4}.
		We then construct an instance (G,{1,2,3},^',_^',_^') of 2 as follows.
		The idea is to simply replace a value 4 with some value from {1,2,3} for each vertex without changing the graph G.
		Let v∈ V(G) be a vertex such that 4∈(v).
		Since |(v)|≤ 3, there exists a value i in {1,2,3}∖(v).
		Let π→ be a permutation such that π(i)=4, π(4)=i and π(j)=j for each j∉{i,4}, and we update (,,_,_) as follows:
		
			
  * (v):=(v)∖{4}∪{i};
			
  * :=(π((v)),(w)) for each neighbor w of v and each mapping ∈(vw); and
			
  * _(v):=π(_(v)) for each ∈{,}.
		
		We repeat this operation until there is no vertex v such that 4∈(v), and let ^'=(G,{1,2,3},^',_^',_^') be the resulting instance.
		Observe that the construction can be done in polynomial time.
		
		Because we only replace values, ^' is a valid instance of 2 which is essentially equivalent to .
		Moreover, G is bipartite planar and the domain has only three values, and thus this completes the proof.
	
	
	In contrast to Theorem <ref>, there exist polynomial-time algorithms for more restricted cases.
	We first show that the problem becomes tractable when restricted to L and =3.
	
			
		L can be solved in polynomial time if =3.
	
	
		Let =(G,,,_,_) be a given instance of L such that H is the  graph with |V(H)|≤ ||=3 and  is a list assignment.
		We assume without loss of generality that G is connected and has at least two vertices.
		Since G is connected, for any homomorphism  from G to H, there exists exactly one connected component C of H such that (v)∈ V(C) holds for every vertex v∈ V(G).
		Moreover, for any two homomorphisms  and ^' from G to H which correspond to different connected components, |^'|=|V(G)|≥ 2 holds; and hence they are not adjacent in the solution graph.
		Because the relation of reconfigurability between homomorphisms is transitive, C_=C_ holds if _ and _ are reconfigurable, where C_ and C_ are connected components of H corresponding to _ and _, respectively.
		Thus, we can assume that C_=C_, and let H:=C_ and :=V(C_).
		If H is complete,  is also an instance of L with ||≤ 3, which is solvable in polynomial time <cit.>.
		Otherwise, H is a path ({1,2,3},{12,23}) of length two.
		Let V_ (resp. V_) be the set of all vertices v∈ V(G) with _(v)∈{1,3} (_(v)∈{1,3}).
		We now claim that  is a yes-instance if and only if V_=V_, which can be checked in polynomial time.
		
		If V_=V_, then __⊆ V_ holds.
		Because H contains no edge between 1 and 3 and _ is a homomorphism from G to H, V_ must be an independent set of G.
		Therefore, we can independently change the value of each vertex in __⊆ V_ to obtain _; and hence  is a yes-instance.
		
		We next assume that  is a yes-instance but V_ V_.
		Then, there exist two consecutive homomorphisms  and ^' in the reconfiguration sequence such that ((v),^'(v))∈{(1,2),(2,1),(3,2),(2,3)} holds, where v is the unique vertex in ^';
		that is, ^' is obtained from  by changing the value of v along an edge of H.
		Since G is connected and has at least two vertices, v has at least one neighbor w in G.
		Because  is a homomorphism, (v)=2 if and only if (w) 2.
		Similarly, because ^' is a homomorphism, ^'(v)=2 if and only if ^'(w)=(w) 2.
		From the definition of v, (v)=2 if and only if ^'(v) 2.
		We thus have that (w) 2 if and only if (w)=2, which is a contradiction.
		Therefore, V_ V_ if  is a yes-instance.
	
	
	We next show that 2 becomes tractable if  is reduced from three to two.
	
		
		2 can be solved in polynomial time if =2.
	
	
		We reduce the problem to bijunctive , which is solvable in polynomial time <cit.>.
		Bijunctive  is a special case of  where ={0,1} and there exists a 2-CNF formula ϕ(v_1,…,v_r) such that ({v_1…,v_r}) is exactly the set of all satisfying assignments of ϕ for every hyperedge {v_1…,v_r}∈ E(G).
		Let =(G,,,_,_) be a given instance of 2 where G is a graph and ={0,1}.
		We now show that for every edge vw∈ E(G) there exists a 2-CNF formula ϕ(v,w) such that (vw) is exactly the set of all satisfying assignments of ϕ.
		For each i∈ and u∈{v,w}, we denote by u^i a literal u if i=0 or u̅ if i=1.
		Then we define a 2-CNF formula ϕ(v,w) as follows:
		
    ϕ(v,w)=⋀_(a,b)∈^2 ∖(vw) (v^a ∨ w^b).

		Notice that a clause (v^a ∨ w^b) corresponds to a set ^2 ∖{(a,b)}.
		Therefore, ϕ(v,w) corresponds to the set
		
    ⋂_(a,b)∈^2 ∖(vw)^2 ∖{(a,b)}=^2 ∖ (^2 ∖(vw))=(vw)

		as required.
	



§ BOUNDARY OF TIME COMPLEXITY



	In this section, we explore the boundary of time complexity of the problem.
	We first give a simple exact algorithm as follows.
	
		
		0 can be solved in time O^*(^O(n)), and hence 0 is fixed-parameter tractable when parameterized by +n and in XP when parameterized by n, where n is the number of vertices of a given hypergraph.
	
	
		Our algorithm explicitly construct the solution graph and then check the connectivity between two given solutions.
		The solution graph has at most ^n vertices and can be constructed in time O^*(^O(n)).
		The connectivity can be checked in time polynomial in the size of the solution graph by a simple breadth-first search.
		Therefore, our algorithm runs in time O^*(^O(n)).
	
	
	On the other hand, the following theorem implies that a fixed-parameter algorithm parameterized only by n is unlikely to exist.
	
		
		 is W[1]-hard when parameterized by n.
	
	
		We give a parameterized reduction from labeled clique reconfiguration, which is defined as follows.
		Let G^' be a simple graph and let  be a positive integer.
		A -labeled clique (-LC for short) of G^' is a vector (u_1,u_2,…,u_) consisting of  distinct vertices u_1,u_2,…,u_∈ V(G^') which form a clique.
		A -labeled clique graph G^' is a graph such that V(G^') is a set of all -LCs of G^', and two -labeled cliques C and C^' are adjacent if and only if they differ on exactly one component.
		Then, labeled clique reconfiguration asks for a given graph G^', an integer , two -LCs C_ and C_, whether there exists a walk between C_ and C_ in G^' or not.
		It is known that labeled clique reconfiguration is W[1]-hard when parameterized by  <cit.>.[
			Although they actually show the similar result for (unlabeled) independent set reconfiguration, the proof can be applied to labeled clique reconfiguration.]
		
		We now construct an instance (G,,,_,_) of  corresponding to an instance (G^',,C_,C_) of labeled clique reconfiguration.
		Let G be a complete graph K_ with  vertices {v_1,v_2,…,v_}, and let =V(G^').
		We define constraints for edges so that G^' is an  graph; that is, for each v_i v_j ∈ E(G), we define (v_i v_j)={(u_p,u_q)  u_p u_q ∈ E(G^')}.
		Observe that (G,,) is an instance of homomorphism with  vertices.
		The remaining components, two solutions _ and _, are defined as follows.
		For any -LC C=(u_1,u_2,…,u_) of G^', we define ϕ_C be a mapping such that ϕ_C(v_i)=u_i for each i∈{1,2,…,}.
		Since ϕ_C(v_i) ϕ_C(v_j)=u_i u_j∈ E(G^') holds for each distinct i,j∈{1,2,…,}, ϕ_C is a solution of (G,,).
		Thus, let _=ϕ_C_ and _=ϕ_C_.
		This completes the construction of =(G,,,_,_).
		Finally, (G^',,C_,C_) is a yes-instance if and only if  is, because G^' and  are isomorphic under a mapping ϕ.
	
	The following also follows as a corollary.
	
		
		 is W[1]-hard when parameterized by p, where p is any parameter which is polynomially bounded in n.
	

	We finally give a lower bound on the computation time, which matches the running times of Theorem <ref> and two theorems which will be shown later.
	
		
		Under ETH, there exists no algorithm solving 2 in time (+n)+n. 
	



§ PSPACE-COMPLETENESS FOR GRAPHS WITH BOUNDED PARAMETERS



	In this section, we show the PSPACE-completenesses of L and 2 for graphs with bounded parameter.

	
		
		L is PSPACE-complete even if =O(1) for paths.
	

	
		
		2 is PSPACE-complete even if =3 for complete graphs.
	
	
		Let (G,,,_,_) be an instance of 2 constructed in Theorem <ref>.
		We then add an edge between every non-adjacent pair, and give a trivial constraint (vw)=^2 to every added edge vw.
		Notice that this modification does not change the solution graph, and thus the reconfigurability.
	



§ FIXED-PARAMETER ALGORITHM WITH RESPECT TO GRAPH PARAMETERS



	We give the following theorems in this section.
	
		
		L is fixed-parameter tractable when parameterized by +.
	
	
		
		0 is fixed-parameter tractable when parameterized by +.
	



 §.§ Reduction rule


	
	In order to prove the above theorems, we give fixed-parameter algorithms which are based on the concept of “kernelization”.
	That is, we compute from the given instance into another instance whose size depends only on the parameter.
	After that, we can solve the problem by using Theorem <ref>.
	
	In this subsection, we show some useful lemma, which compresses an input hypergraph into a smaller hypergraph with keeping the reconfigurability.
	We note that this is the extension of the lemma given in <cit.> to obtain a fixed-parameter algorithm for L parameterized by +.
	The main idea is to “identify” two subgraphs which behave in the same way with respect to the reconfigurability.
	
	We now formally characterize such subhypergraphs and explain how to identify them.
	Let =(G,,,_,_) be an instance of 0.
	For each vertex v∈ V(G), we define v as a pair (_(v),_(v)) consisting of the initial and the target value assignments of v.
	Let V_1 and V_2 be two non-empty vertex subsets of G such that |V_1|=|V_2|, and V_1∩ V_2=∅.
	Assume that GV_1=GV_2=W.
	Let H_1=G[V_1], H_2=G[V_2], H_1^'=G[V_1∪ W] and H_2^'=G[V_2∪ W].
	
		
		Two induced subhypergraphs H_1 and H_2 are identical if there exist two bijections V(H_1^') → V(H_2^') and E(H_1^') → E(H_2^') which satisfy the following four conditions:
		
			
  * H_1^' and H_2^' are isomorphic under  and .
			
  * for every vertex v∈ W, (v)=v;
			
  * for every vertex v∈ V_1, v=(v), that is, _(v)=_((v)) and _(v)=_((v)); and
			
  * for every hyperedge X∈ E(H_1), ((X))=(X), where =ϕX.
		
	
	See  <ref> for an example.



	We next define another instance ^'=(G^',,^',_^',_^') as follows:
	
		
  * G^'=G ∖ V_2;
		
  * _^'=_V(G^') and _^'=_V(G^'); and
		
  * for each X^'∈ E(G^'), ^'(X^')=⋂_X∈ E^'X, 
		where E^'={X∈ E(G)  X∖ V_2=X^'} and X={X^'∈(X)}.

	
	Intuitively, ^' is obtained by restricting all components (hypergraphs, mappings in constraints, and two solutions) of  on V(G)∖ V_2.
	We say that ^' is obtained from  by identifying H_1 with H_2.
	
	Then, we have the following lemma, which says that  and ^' are equivalent with respect to the feasibility.
	
		
		Let ^' V(G^') → be a mapping from V(G^') to .
		Then, ^' is a solution for (G^',,^') if and only if there exists a solution  for (G,,) such that ^'=V(G^').
	
	Notice that Lemma <ref> ensures that the “restricted” instance ^' is a valid instance of 0.
	
	We now give the following key lemma, which says that  and ^' are equivalent with respect to even the reconfigurability.
	
		
		Let  and ^' be instances of 0 defined as above.
		Then, ^' is a yes-instance if and only if  is.
	



§ VERTEX COVER



	In this section, we consider the size  of a minimum vertex cover.
	Note that Theorem <ref> implies 0 is fixed-parameter tractable when parameterized by +.
	We strengthen it as follows.
	
		
		The shortest variant of 0 is fixed-parameter tractable when parameterized by +.
	
	
		
		There exists a fixed-parameter algorithm for 0 parameterized by + which runs in time O^*(^O()).
	



 §.§ Discussions


	We conclude this section by discussing hitting sets on hypergraphs, which is a well-known generalization of vertex covers on graphs.
	Although a hitting set of a 2-uniform hypergraph is equivalent to a vertex cover of the graph, such an equivalence does not hold for general hypergraphs.
	Thus, it is worth considering the complexity of 0 with respect to the size of a hitting set of a given hypergraph.
	We have the following theorem, which implies that a fixed-parameter algorithm for 0 is unlikely to exist when parameterized by the size of a hitting set plus .
	
		
		3 is PSPACE-complete even for hypergraphs with a hitting set of size one and =3.
	
	
		Let =(G,,,_,_) be an instance constructed in Theorem <ref>.
		Briefly speaking, we add a new vertex u to G, include it in every edge vw∈ E(G), and modify the constraints so that a value assignment to u does not affect any other vertices.
		More precisely, we construct a new instance ^'=(G^',,^',^'_,^'_) as follows.
		Let V(G^'):=V(G)∪{u} and E(G^'):={{u,v,w} vw ∈ E(G)}, where u is a new vertex which is not in G.
		Then, G^' has a hitting set {u} of size one.
		For each hyperedge {u,v,w}∈ E(G^'), we let ^'({u,v,w}):={1}×(vw).
		We finally extend _ (resp., _) to ^'_ (resp., ^'_) by setting ^'_(u)=1 (resp., ^'_(u)=1).
		This completes the construction.
		 ^' is equivalent to  by ignoring a value assignment to u.
	



§ EXTENSION OF THEOREM <REF>



	In this section, we extend Theorem <ref> to a more general situation.
	
		
		There exists a fixed-parameter algorithm for 2 parameterized by + which runs in time O^*(^O()).
	
	


§ CONCLUSION

	
	In this paper, we studied 0 and its special cases from the viewpoints of polynomial-time solvability and parameterized complexity, 
	and gave several interesting boundaries of tractable and intractable cases with respect to the size  of a domain ( <ref>), the size of lists ( <ref>), and the structure of an input hypergraph (s <ref> and <ref>).
	Moreover, we gave some exact algorithms, and a lower bound of the computation time that meets the running times of our algorithms under ETH.
	
	We leave as an open question whether some of our algorithms can be extended for the shortest variant or not.
	In particular, the extensions of the fixed-parameter algorithms parameterized by + (Theorem <ref>) and + (Theorem <ref>), respectively, are interesting.
	We note that the reduction rule (Lemma <ref>) does not preserve the shortest length of a reconfiguration sequence since we just remove vertices.





§ PROOF OF THEOREM <REF>


	We give a polynomial-time reduction from , which is defined as follows.
	An instance of  is a graph H with the vertex set {ip 1 ≤ i,p ≤}; we denote i={ip 1 ≤ p ≤} for each i∈{1,2,…,}.
	Then, the problem asks whether there exists a clique Q⊆ V(H) such that |Q∩i|=1 for every i∈{1,2,…,}.
	It is known that there exists no algorithm solving  in time  under ETH <cit.>.
	We will present a polynomial-time transformation from an instance H of  to an instance  of 2 such that
	
		
  * a graph has +2 vertices and a domain has +1 values; and 
		
  * H is a yes-instance if and only if  is.
	
	If there exists an algorithm A solving 2 in time (+n)+n, an execution of A for the transformed instance  yields an algorithm solving  in time
	
    (+n)+n=(2+3)2+3=(^2)2+3=.

	
	
	Before constructing , we first reformulate  as a special case of 2-ary constraint satisfiability by a similar idea of the proof of Theorem <ref>.
	Let G^' be a complete graph K_ with  vertices {v_1,v_2,…,v_}, and let ^'={1,2,…,}.
	We construct each constraint so that assigning a value p∈ to a vertex v_i∈ V(G^') corresponds to choosing a vertex ip as a member of a clique Q. 
	That is, we define ^'(v_i v_j):={(p,q) ipjq∈ E(H)}.
	Observe that we can simultaneously assign p and q to v_i and v_j, respectively, if and only if ip and jq are adjacent in H.
	Therefore, H and (G^',^',^') are equivalent.
	Clearly, |V(G^')|=|^'|= holds.
	
	We now construct an instance =(G,=^'∪{0},,_,_) of 2 as follows.
	A graph G is obtained from G^' by adding two new vertices w_1 and w_2 and edges {w_1 w  w∈ V(G^') ∪{w_2}}.
	These added vertices will form a key component which links the existence of a solution of (G^',^',^') with the reconfigurability of .
	Clearly, |V(G)|=+2 and ||=+1 hold.
	We first construct the constraints of the original graph G^'.
	For each edge v_i v_j∈ E(G^'), we add to a constraint ^'(v_i v_j), all mappings which contain 0; that is, (v_i v_j):=^'(v_i v_j)∪ ({0}×) ∪ (×{0}).
	We have the following observation.
	
		
		Solutions of (G^',,) in which no vertices are assigned 0 one-to-one corresponds to solutions of the original instance (G^',^',^').
	
	We next define the constraints regarding w_1 and w_2.
	The constraint (w_1 w_2) of w_1 w_2∈ E(G) is defined as (w_1 w_2):={(0,1),(0,2),(1,2),(2,1)}.
	For each v_i∈ V(G^'), we let (w_1 v_i)=^2 ∖{(0,0)}.
	Then, we have the following observation.
	
		
		we can assign 0 to w_1 if and only if no other vertices are assigned 0.
	
	Finally, we define two solutions _ and _ as follows:
	
		
  * for each vertex v_i ∈ V(G^'), let _(v_i)=_(v_i)=0; and
		
  * let _(w_1)=_(w_2)=1 and _(w_2)=_(w_1)=2.
	
	
	In order to show the correctness, it suffices to show the following lemma.
	
		(G^',^',^') has a solution if and only if  is a yes-instance.
	
	We first show the if direction.
	Assume that _ and _ are reconfigurable.
	Then, a reconfiguration sequence must contain a solution  such that (w_1)=0.
	Otherwise, values of w_1 and w_2 can never be changed because only allowed assignment to {w_1, w_2} is either (1,2) or (2,1) in this case, which contradicts the reconfigurability.
	Since  assigns 0 to w_1, no other vertices are assigned 0 by Observation <ref>.	
	In addition, by Observation <ref>, V(G^') is a solution of (G^',^',^').
	
	We next prove the only-if direction.
	Let  be a solution of (G^',^',^').
	We extend it to solutions _^' and _^' of (G,,) as follows.
	For each ∈{,}, 
	
		
  * let _^'(v_i)=(v_i) for each v_i∈ V(G^'); and
		
  * let _^'(w_1)=_(w_1) and _^'(w_2)=_(w_2).
	
	Notice that _^' is a solution, and that _ and _^' are reconfigurable by changing values of all vertices v_i∈ V(G^') from 0 to _^'(v_i).
	Furthermore, _^' and _^' are reconfigurable by the following three steps:
	
		
  * change a value of w_1 from 1 to 0;
		
  * change a value of w_2 from 2 to 1; and
		
  * change a value of w_1 from 0 to 2.
	
	We note that this yields a valid reconfiguration sequence: in particular, Observation <ref> and the construction of _^'  justify the first step.
	Therefore, _ and _ are reconfigurable.



§ PROOF OF THEOREM <REF>

	
	We give a polynomial-time reduction from -word reconfiguration, which is defined as follows.
	Let  be a (possibly non-simple) directed graph.
	An -word (of length ) is a string ∈ V()^ such that w_i w_i+1∈ E() for every pair of consecutive symbols w_i and w_i+1 in ; in other words,  can be seen as a directed walk in .
	For an integer ≥ 1, an -word graph  is a graph such that V() is a set of all -word of length , and two -words  and ^' are adjacent if and only if the hamming distance between them is exactly one.
	Then, -word reconfiguration asks for a given integer , two -words _ and _, whether there exists a walk between _ and _ in  or not.
	Wrochna showed that there exists a directed graph  such that -word reconfiguration is PSPACE-complete <cit.>.
	
		
	
	We now construct an instance (G,,,_,_) of L corresponding to an instance (,_,_) of -word reconfiguration.
	The idea is similar to the one used in the proof of the PSPACE-completeness of  for cycles <cit.>.
	Let G be a path with  vertices v_1,v_2,…,v_.
	An  graph H is constructed as follows.
	The vertex set V(H) is a union of three sets 0,1,2, where p={x^p  x∈ V()} for each p∈{0,1,2}; each p is called a layer.
	For any integer q>2, we define x^q=x^p and q=p if q≡ p (mod 3).
	The edge set E(H) is a union of three sets 0,1,2, where p={x^p y^p+1 xy∈ E()} for each p∈{0,1,2}.
	(See  <ref> for an example of p.)
	Let =V(H), and let (v_i)=i for each vertex v_i∈ V(G).
	For each edge v_i v_i+1∈ E(G), we construct the constraint (v_i v_i+1) so as to respect H, (v_i) and (v_i+1).
	Finally, we define _ for each ∈{,} as follows.
	For each v_i∈ V(G), let _(v_i)=w_i^p if w_i is the i-th symbol of _.
	This completes the construction of (G,,,_,_), which can be done in polynomial time.
	
	In order to show the correctness, we show that there exists a bijection between all solutions of (G,,) and all -words of length .
	Let V(G) → be any mapping which respects all lists such that ((v_1),(v_2),…,(v_))=(w_1^1,w_2^2,…,w_^) for some w_1,w_2,…,w_∈ V().
	We now define ω() as a string w_1 w_2 ⋯ w_.
	For each i ∈{1,2,…,-1}, (v_i) (v_i+1)=x^i y^i+1∈ E(H) if and only if w_i w_i+1=xy ∈ E().
	Therefore,  is a solution of (G,,) if and only if ω() is an -word of length .
	Let ω^' be the restriction of ϕ on V((G,,)), that is, ω^'=ωV((G,,)).
	Then, by the definition of ω, ω^' is a bijection between V((G,,)) and V().
	Moreover, this bijection preserves the adjacency relation of the solution graph, and _=ω^'(_), ∈{,}.
	Thus, (G,,,_,_) is a yes-instance if and only if (,_,_) is.



§ PROOFS OMITTED FROM SECTION <REF>




 §.§ Proof of Lemma <ref>


	We first prove the if direction.
	Assume that  is a solution for (G,,).
	In order to show that ^'=V(G^') is a solution for (G^',,^'), it suffices to check that ^' satisfies all constraints.
	For each X^'∈ E(G^'), consider the hyperedge set E^'={X∈ E(G)  X∖ V_2=X^'}.
	Recall that ^'(X^')=⋂_X∈ E^'X, where X={X^'∈(X)}.
	For every hyperedge X∈ E^', X∈(X) holds since  is a solution for (G,,).
	Notice that ^'X^'=(X)X^', and hence it is contained in X.
	Therefore, ^'X^'∈^'(X^') holds, and hence ^' is a solution for (G^',,^').



	
	We next prove the only-if direction.
	Assume that ^' is a solution for (G^',,^').
	We claim that a mapping V(G) → obtained by extending ^' as follows is a solution for (G,,):
	
    (v) ={[ ^'(^-1(v))          ;;      ^'(v)          . ].

	To this end, we show that for each hyperedge X∈ E(G), X∈(X) holds.
	Briefly, this follows the conditions (2) and (4) of Definition <ref>.
	If X∈ E(G^'), ^'(X) contains ^'X=X.
	Because ^'(X) is a subset of (X), (X) also contains X.

	Otherwise, X is a hyperedge in H_2^'=G[V_2∪ W].
	By the condition (4) of Definition <ref>, (X)=(X^') holds, where =ϕX^' and (X^')=X.
	Because W, V_1 and V_2 are disjoint each other, X^'⊆ V_1∪ W  does not intersect V_2.
	Therefore, X^' is contained as a hyperedge in G^', and hence ^' satisfies the constraint of X^'; that is, ^'X^'∈(X^').
	Recall that (X^')={∘^-1∈(X^')}.
	Thus, (^'X^')∘^-1 is in (X)=(X^').
	It now suffices to show that (^'X^')∘^-1=X.
	From the definition of , (v)=^'(^-1(v)) holds for each v∈ V_2∩ X, and (v)=^'(v) holds or each v∈ W∩ X.
	In addition, by the condition (2) of Definition <ref>, (v)=^'(^-1(v)) also holds in the later case; and hence X=(^'∘^-1)X.
	Since ^-1=(X^')^-1=^-1X is a bijection from X to X^', we have X=(^'∘ϕ^-1)X=(^'X^')∘ (^-1X)=(^'X^')∘^-1 as required.



 §.§ Proof of Lemma <ref>


	We first prove the if direction.
	Suppose that  is a yes-instance.
	Then, there exists a reconfiguration sequence _0, _1, …, _ℓ for , where _ℓ=_.
	For each i∈0ℓ, _iV(G^') is a solution for (G^',,^') by Lemma <ref>.
	Therefore, by removing all duplicate solutions appearing consecutively in the resulting sequence, _0V(G^'), _1V(G^'), …,_ℓ^'V(G^') is a reconfiguration sequence for ^'.
	Thus ^' is a yes-instance.
	
	We now prove the only-if direction.
	Suppose that ^' is a yes-instance.
	Then, there exists a reconfiguration sequence ^'=^'_0, ^'_1, …, ^'_ℓ for ^' with ^'_0=_V(G^') and ^'_ℓ=_V(G^').
	Our goal is to construct a reconfiguration sequence  for  from ^'.
	For each i∈0ℓ, we first extend ^'_i to _i as follows:
	
    _i(v) ={[ ^'_i(^-1(v))            ;;      ^'_i(v)            . ].

	Notice that _i corresponds to the mapping defined in the only-if proof of Lemma <ref>, and hence it is a solution for (G,,).
	Therefore, _0, _1, …, _ℓ is a sequence of solutions for (G,,).		
	However, there may exist several indices i∈0ℓ-1 such that _i and _i+1 are not adjacent, that is, |_i_i+1|>1 may hold.
	Recall that ^'_i and ^'_i+1 are adjacent for each i∈0ℓ-1, that is, ^'_i^'_i+1={w} for some vertex w∈ V(G^').
	Therefore we know that
	
		
  * if w∉ V(H_1), then _i_i+1={w} holds, that is, _i and _i+1 are adjacent; and
		
  * if w∈ V(H_1), then _i_i+1={w,(w)} holds, that is, _i and _i+1 are not adjacent.
	
	In the latter case, between _i and _i+1, we insert a solution _i of G defined as follows:
	
    _i(v) ={[ _i+1(v)       ;;   _i(v)       ;;   _i(v)       . ].

	Observe that _i is a solution for (G,,).
	Moreover, both _i_i={w} and _i_i+1={(w)} hold.
	Thus, we obtain a proper reconfiguration sequence  for  as claimed.



 §.§ Proof of Theorem <ref>

	
	In order to prove Theorem <ref>, we first give a sufficient condition for which two subgraphs in an instance of L satisfy Definition <ref>.	
	Let =(G,,,_,_) be a given instance of L such that H is the  graph and  is a list assignment.
	Let H_1 and H_2 are two induced subgraphs such that |V(H_1)|=|V(H_2)|, V(H_1)∩ V(H_2)=∅.
	
		
		H_1 and H_2 are L-identical if there exists a bijection V(H_1) → V(H_2) which satisfies the following two conditions:
		
			
  * vw∈ E(H_1) if and only if (v)(w)∈ E(H_2).
			
  * for every vertex v∈ V_1,
			
				
  * Gv∖ V(H_1)=G(v)∖ V(H_2);
				
  * v=(v), that is, _(v)=_((v)) and _(v)=_((v)); and
				
  * (v)=((v)).
			
		
	
	Then, we have the following lemma.
	
		
		H_1 and H_2 are identical if they are L-identical for a bijection .
	
	
		We first prove that the assumption that GV(H_1)=GV(H_2) is satisfied.
		By the condition (ii)-a, we have GV(H_1)=⋃_v∈ V(H_1)(Gv∖ V(H_1))=⋃_v∈ V(H_1)(G(v)∖ V(H_2)).
		Since  is a bijection, ⋃_v∈ V(H_1)(G(v)∖ V(H_2))=⋃_v∈ V(H_2)(Gv∖ V(H_2))=GV(H_2), as required.
		
		Let W=GV(H_1)=GV(H_2), H_1^'=G[V(H_1)∪ W] and H_2^'=G[V(H_2)∪ W].
		In order to prove the lemma, it suffices to give two bijections which satisfy all conditions of Definition <ref>.
		We define two mappings ^' and ^' as follows.
		
			
  * For each v∈ V(H_1^'), ^'(v)=(v) if v∈ V(H_1) and ^'(v)=v if v∈ W.
			
  * For each vw∈ E(H_1^'), ^'(vw)=^'(v) ^'(w).
		
		We now prove the condition (1) for ^' and ^'.
		Since  is a bijection between V(H_1) and V(H_2), ^' is a bijection between V(H_1^') and V(H_2^').
		By the definition of ^', we suffice to show that ^' is a bijection between E(H_1^') and E(H_2^').
		From the definition and the condition (i), ^'E(G[W]) is a bijection (the identity mapping) between E(G[W]) and E(G[W]) and ^'E(H_1) is a bijection between E(H_1) and E(H_2).
		Let E_1^'=E(H_1^')∖(E(H_1) ∪ E(G[W])) and E_2^'=E(H_2^')∖(E(H_2) ∪ E(G[W])).
		Then, it suffices to show that ^'E_1^' is a bijection between E_1^' and E_2^'.
		For each vertices v∈ V(H_1) and w∈ W, ^'(v) ^'(w)=(v) w holds.
		From the condition (ii)-a, vw∈ E_1^' if and only if (v) w∈ E_2^'.
		Therefore, ^'E_1^' is a bijection between E_1^' and E_2^', and hence ^' is a bijection between E(H_1^') and E(H_2^').
		
		The conditions (2) and (3) directly follows the definition of ^' and the condition (ii)-b.
		
		We finally prove the condition (4).
		Recall that each constraint (vw)={∈^{v,w}(v)(w) ∈ E(H)∩((v) ×(w))} depends only on (v) and (w).
		From the condition (ii)-c, for every vw∈ E(H_1), (v) ×(w)=(^'(v)) ×(^'(w)) holds.
		Therefore, (vw) and (^'(vw)) are the same when we see them as the sets of vectors.
	
	
	We note that Definition <ref> and Lemma <ref> are equivalent to the definition of “identical subgraphs” and a “reduction rule” given for L <cit.>.
	Therefore, by using the same argument as <cit.>, we have the following proposition.
	
		There exists a polynomial-time algorithm which computes from a given instance  of L an instance ^' such that:
		
			
  ∙ ^' can be obtained by repeatedly applying Lemma <ref>; and
			
  ∙ the size of ^' depends only on the modular-width and the size of a maximum clique of a given graph G, and .
		
	
	
	Because a given graph G has a homomorphism to a simple graph with  vertices, the size of a maximum clique of G must be at most .
	Thus, the size of ^' depends only on the modular-width and , and hence we are done.



 §.§ Proof of Theorem <ref>

	
	We first define the tree-depth and introduce some notation.
	Let G be a connected graph.
	A tree-depth decomposition of G is a rooted tree T such that V(T)=V(G) and if vw ∈ E(G) then one of two endpoint is an ancestor of the other in T.
	The depth of T is the maximum number of vertices of a path in T between the root and a leaf.
	The tree-depth (G) of G is the minimum depth of a tree-depth decomposition of G.
	It is known that there exists an algorithm computing the tree-depth decomposition of depth  in time O^*(2^O(^2)) <cit.>.
	For a tree-depth decomposition T of a graph G and for a vertex v∈ V(T)=V(G), v denote the subtree of T rooted at v, and v denote the set of all ancestors of v.
	From the definition of a tree-depth decomposition, Gv⊆ V(v)∪v holds.

Let =(G,,,_,_) be a given instance of 0, and let T be a tree-depth decomposition of G with depth .
	We assume that all vertices of V(G) are totally ordered in the pre-order of the depth-first search on T starting with its root; let ≺ be the binary relation defined by this ordering.
	
	We now explain a preprocessing of our kernelization algorithm, which will simplify the discussion, and then give a sufficient condition that two subhypergraphs are identical.
	
	Let X∈ E(G) be a hyperedge.
	From the definition of the primal graph, any two distinct vertices v and w in X are adjacent in G, and hence they are in ancestor-descendant relationship in T.
	Therefore, there exists the unique vertex which is farthest from the root.
	We call v the bottommost vertex of X.
	Then, for each vertex v∈ V(G), we modify the given instance as follows. 
	
		
  * Remove all hyperedges X whose bottommost vertices are v from G.
		
  * Add a hyperedge X_v=v∪{v} to G, and let (X_v) be the set of all mappings ∈^X_v which satisfy the constraints of all removed hyperedges.
	
	Observe that this modification can be done in time O^*(^), since each vertex has at most  ancestors, and does not change the set of solutions.
	Therefore, in the remainder of this section, we assume that there exists a one-to-one correspondence between V(G) and E(G) such that v∈ V(G) corresponds to the hyperedge v∪{v}.
	
	Let v∈ V(T) be a vertex, and assume that all vertices in V(v) are labeled as v_1,v_2,…,v_p according to ≺.
	Then, we define three p-tuples v, v and v as follows.
	
		
  * The i-th component of v is Tv_i.
		
  * The i-th component of v is v_i.
		
  * The i-th component of v is a set of vectors of length |X_i| which corresponding to (X_i) under the total order ≺, where X_i=v_i∪{v_i}.
	
	We call these tuples ID-tuples of v.
	Then, we have the following lemma.
	
		
		Let v and w be two children of a vertex u in T such that |V(v)|=|V(w)|.
		If (v,v,v)=(w,w,w) holds, then G[V(v)] and G[V(w)] are identical under some pair of two bijections.
	
	
		By the preprocessing, GV(v)=GV(w)=v=w holds.
		We denote H_1=G[V(v)], H_2=G[V(w)], H_1^'=G[V(v)∪v] and H_2^'=G[V(w)∪w].
		We now define a pair of mappings  and  as follows.
		 maps the i-th vertex in V(H_1^') to the i-th vertex in V(H_2^') according to ≺.
		(X)={(x_1),(x_2),…,(x_)} holds for each hyperedge X={x_1,x_2,…,x_}∈ E(H_1^').
		
		Then, it suffices to show that  and  satisfy the conditions (1) through (4) of Definition <ref>.		
		From the definition of , the condition (2) holds; that is, (x)=x if x∈v.
		Since v=w, the condition (3) holds.
		In order to verify the condition (1), we show that  is a bijection from E(H_1^') to E(H_2^').
		The assumption that v=w implies that v and w isomorphic under .
		Furthermore, T[V(v)∪v]=T[V(H_1^')] and T[V(w)∪w]=T[V(H_2^')] are isomorphic, too.
		Recall that for any vertex x∈ V(G), there exists the corresponding hyperedge X∈ E(G) such that X=v∪{v}.
		Therefore, for each hyperedge X∈ E(H_1^') corresponding to x∈ V(H_1^'), (X) is a hyperedge corresponding to (x) ∈ V(H_2^').
		Thus, condition (1) holds.
		Finally, since v=w, the condition (3) holds.
	

We now describe our kernelization algorithm.
	Our algorithm traverses T from leaves to the root, that is, the algorithm processes a vertex of T after its all children are processed.
	
	Let u∈ V(G) be a vertex which is currently visited.
	We check if there is a pair of children v and w which satisfies the conditions of Lemma <ref>.
	If such a pair is found, we apply Lemma <ref> to remove V(w).
	We note that the one-to-one correspondence between the vertex set and the hyperedge set is preserved during this process.
	Therefore, we repeat this as long as such a pair is left.
	
	The running time of this kernelization can be estimated as follows.
	For each pair of two children of a vertex, Lemma <ref> can be checked in time polynomial in |V(G)| and the maximum size of a constraint (i.e., O(^)).
	Since there exist at most |V(G)|^2 pairs to be checked, the algorithm runs in time polynomial in |V(G)| and O(^).
	
Finally, we prove that the obtained instance (G^',,^',^'_,^'_) has bounded size.
	We have the following lemma.
	
		
		The graph G^' has at most  vertices, where j is recursively defined for an integer j≥ 1 as follows:
		
    j ={[                      1                      ;; α^2 ·(2^α·^2 · 2^^α)^α                      , ].

		where α=j-1.
		In particular,  depends only on +.
	
	
		In order to prove the lemma, we define the level of the tree-depth decomposition:
		each leaf has the level one, and the level of each internal vertex is the maximum level of a child plus one.
		Then, we prove the following stronger claim:
		
			Let u be a vertex of level i, and let G_u and T^' be the graph and the tree-depth decomposition obtained by the algorithm after processing u.
			Then, G_u[V(T^'_u)] has at most i vertices.
		
		We prove the claim by the induction on i.		
		If i=1, then we have |V(G_u[V(T^'_u)])|=1=1 since u is a leaf.
		
		We thus assume in the remainder of the proof that i>1.
		Consider each child v of u in T^'.
		Since v's level is less than i, and G_u[v^'] is the graph obtained by the algorithm after processing v, |V(v^')|≤i-1 by the induction hypothesis.
		Thus, it suffices to show that r has at most α·(2^α·^2 · 2^^α)^α children, where α=i-1.
		Because the algorithm has processed u, there exists no pair of two children v and w of u which satisfies Lemma <ref>.
		Therefore, the number of children can be bounded by the number of distinct combinations of three ID-tuples with at most α components.
		For each β≤α, the number of distinct combinations of three ID-tuples with β components can be bounded as follows.
		Recall that for each child v such that |v^'|=β, v, v, and v consist of β subsets of v^', β pairs of tow values from , and β constraints of arity at most β, respectively.
		Thus, 
		
			
  * the number of distinct ·'s is at most (2^β)^β;
			
  * the number of distinct ·'s is at most (^2)^β; and
			
  * the number of distinct ·'s is at most (2^^β)^β.
		
		Therefore, the number of children is at most
		
    ∑_β=1^α(2^β·^2 · 2^^β)^β≤α·(2^α·^2 · 2^^α)^α

		as required.
	

	This completes the proof of the theorem.



§ PROOF OF THEOREM <REF>


	We give a fixed-parameter algorithm for a more general “weighted variant” of 0.
	Let =(G,,,_,_) be an instance of 0, and assume that each vertex v∈ V(G) has a weight (v)∈, where  is the set of all positive integers.
	According to the weight function , we define the weight of each edge ^'∈ E((G,,)) in the solution graph as the weight of v, where {v}=^'.
	We denote by (G,,) the weighted solution graph defined in this way.
	The length  of a reconfiguration sequence (i.e., a walk)  in (G,,) is the sum of the weight of the edges in .
	For each vertex v∈ V(G), we denote by v the number of edges ^' in  such that ^'={v}.
	In other words, v is the number of steps changing the value of v in .
	Notice that =∑_v∈ V(G)(v)·v holds.
	We denote by  the minimum length of a reconfiguration sequence between _ and _; we define =+∞ if  is a no-instance of 0.
	The weighted variant of 0 is to determine whether ≤ℓ or not for a given instance (,) and an integer ℓ≥ 0.
	Notice that the shortest variant is equivalent to the weighted variant where every vertex has weight one.
	Thus, in order to prove Theorem <ref>, it suffices to construct a fixed-parameter algorithm for the weighted variant parameterized by +.
	
	The central idea is the same as Section <ref>; that is, we again kernelize the input instance.
	


 §.§ Reduction rule for the weighted variant


	In this subsection, we give the counterpart of Lemma <ref> for the weighted version.
	
	Let (=(G,,,_,_),) be an instance of the weighted version, and assume that there exist two identical subgraphs H_1 and H_2 of G, both of which consist of single vertices, say, V(H_1)={v_1} and V(H_2)={v_2}.
	We now define a new instance (^',^') as follows:
	
		
  * ^' is the instance obtained by applying Lemma <ref> for H_1 and H_2; and
		
  * ^'(v_1)=(v_1)+(v_2) and ^'(v)=(v) for any v∈ V(G)∖{v_1,v_2}.
	
	Intuitively, v_2 is merged into v_1 together with its weight.
	Then, we have the following lemma.
	
		
		=^'^'.
	
	
		Let ^'=(G^',,^'_,^'_).
		By Lemma <ref>, =+∞ if and only if ^'^'=+∞.
		Therefore, we assume that ^'^'≠ +∞ and ≠ +∞.	
		
		We first show that ≤^'^'.
		Since ≤ holds for any reconfiguration sequence  for , it suffices to show that there exists a reconfiguration sequence for  whose length is at most ^'^'.
		Let ^' be a shortest reconfiguration sequence for ^' such that ^'^'=^'^'.
		Following the only-if direction proof of Lemma <ref>, we can construct a reconfiguration sequence  for  such that v_1=v_2=^'v_1 and v=^'v for any v∈ V(G)∖{v_1,v_2}.
		Therefore, 
		
    [                                                                                                     =                                     ∑_v∈ V(G)(v)·v;                                                                                                     = (v_1) ·v_1 + (v_2) ·v_2 + ∑_v∈ V(G)∖{v_1,v_2}(v)·v;                                                                                                     =     ((v_1) + (v_2))·v_1 + ∑_v∈ V(G)∖{v_1,v_2}(v)·v;                                                                                                     =      ^'(v_1) ·^'v_1 + ∑_v∈ V(G)∖{v_1,v_2}^'(v)·^'v;                                                                                                     =                               ∑_v∈ V(G^')^'(v)·^'v;                                                                                                     =                                               ^'^';                                                                                                     =                                              ^'^'. ]

		Thus,  is a desired reconfiguration sequence for .
		
		We next show that ^'^'≤.
		Since ^'^'≤^'^' holds for any reconfiguration sequence ^' for ^', it suffices to show that there exists a reconfiguration sequence for ^' whose length is at most .
		Let  be a shortest reconfiguration sequence for  such that =.
		We now construct a reconfiguration sequence for ^' from  such that ^'^'≤ as follows.
		
		Case 1. v_1≤v_2.

		In this case, we restrict all solutions in  on V(G^') to obtain a reconfiguration sequence _1 for ^'; recall the if direction proof of Lemma <ref>.
		From the construction, _1v_1=v_1≤v_2 and _1v=v holds for any vertex v∈ V(G^')=V(G) ∖{v_2}.
		Therefore, we have
		
    [                                               ^'_1                                                  =                               ∑_v∈ V(G^')^'(v)·_1v;                                                                                                     =        ^'(v_1) ·_1v_1 + ∑_v∈ V(G^')∖{v_1}^'(v)·_1v;                                                                                                     =      ((v_1)+(v_2)) ·v_1 + ∑_v∈ V(G)∖{v_1,v_2}(v)·v;                                                                                                     ≤ (v_1) ·v_1 + (v_2) ·v_2 + ∑_v∈ V(G)∖{v_1,v_2}(v)·v;                                                                                                     =                                     ∑_v∈ V(G)(v)·v;                                                                                                     =                                                   ;                                                                                                     =                                                  . ]

		Thus, _1 is a desired reconfiguration sequence for ^'.
		
		
		Case 2. v_1 > v_2.

		In this case, instead of restricting solutions in  on V(G^')=V(G)∖{v_2}, we restrict them on V(G)∖{v_1} and obtain a reconfiguration sequence _2 for an instance obtained by restricting on V(G)∖{v_1}.
		Then, because H_1 and H_2 are identical, we can easily “rephrase” _2 as a reconfiguration sequence _2^' for ^'.
		By the same arguments as the case 1 above, we have ^'_2^' < =.

		Thus, _2^' is a desired reconfiguration sequence for ^'.
		
		In this way, we have shown that =^'^' as claimed.
	
	


 §.§ Kernelization


	Finally, we give a kernelization algorithm as follows.
	
	Let (=(G,,,_,_),) be an instance of the weighted version such that the primal graph G has a vertex cover of size at most .
	Because such a vertex cover can be computed in time O(2^· n) <cit.>, assume that we are given a vertex cover  of size at most .
	Notice that :=V(G)∖ forms an independent set of G.
	In order to simplify the proof, we first modify  without changing the set of solutions as follows.
	For each vertex v in , we remove all hyperedges containing v and add a new hyperedge _v=∪{v}; note that each removed hyperedges are subsets of _v since  is an independent set of G.
	We then define a constraint of _v as the set of all mappings ∈^_v satisfying the constraints of all removed hyperedges.
	Observe that this modification can be done in time O^*(^O()) and does not change the set of solutions.
	Thus, we can assume that for each vertex v∈, there exists the unique hyperedge _v such that _v=∪{v}.
	
	Let v_1 and v_2 be two vertices in .
	We now define two mappings _v_1→_v_2 and {_v_1}→{_v_2} as follows:
	(w)=w if w∈, (v_1)=v_2, and (_v_1)=_v_2.
	Suppose that v_1=v_2 and (_v_2)=(_v_1) hold.
	Then, induced subgraphs G[{v_1}] and G[{v_2}] are identical.
	Therefore, we can apply Lemma <ref> to remove v_2 from G, and modify the weight function without changing the optimality.
	As a kernelization, we repeatedly apply Lemma <ref> for all such pairs of vertices in , which can be done in polynomial time.
	Let G^' be the resulting subgraph of G, and let ^':=V(G^')∖.
	Since  is of size at most , it suffices to prove the following lemma.
	
		
		|^'|≤ k^2 · 2^k^+1.
	
	
		Recall that ^' contains no pair of vertices which correspond to identical subgraphs, and hence any pair of vertices v_1,v_2∈^' does not satisfy at least one of v_1=v_2 and (_v_2)=(_v_1).
		Therefore, |^'| can be bounded by the number of distinct combinations of a vertex assignment and a constraint of arity +1.
		Since the domain has size , the number of (possible) vertex assignments can be bounded by k^2.
		Since a constraint of arity +1 can be seen as a subset of ^+1, the number of (possible) constraints can be bounded by 2^k^+1.
		We thus have |^'|≤ k^2 · 2^k^+1 as claimed.
	
	
	This completes the proof of Theorem <ref>.	



§ PROOF OF THEOREM <REF>

	
	In order to prove the theorem, we first introduce the notion of a “contracted solution graph”, which was first introduced in <cit.> and used in several literatures such as <cit.>.
	
	
	Let =(,_,_) be an instance of 0, where =(G,,), and let  be a partition of the vertex set of the solution graph .
	The contracted solution graph (or CSG for short)  is defined as follows.
	The vertex set V() is exactly ; we call each vertex of the CSG a node.
	Each pair of distinct nodes (i.e., sets of solutions) ,^'∈ are adjacent in the CSG if and only if there exist two solutions ∈ and ^'∈^' such that ^'∈ E().
	In other words,  is obtained by contracting a (possibly disconnected) subgraph of  induced by each set ∈ into one node.
	A partition  is proper if every set ∈ induces a connected subgraph of .
	Since the contraction of a connected subgraph maintains the connectivity of a graph, we have the following proposition.
	
		Let =(,_,_) be an instance of 0, where =(G,,), and let  be a proper partition of V().
		Then,  is a yes-instance if and only if there exists a walk between _ and _ in , where _∈_ and _∈_.
		Moreover, the above condition can be checked in time polynomial in ||.
	
	
	Therefore, we first define a proper partition  such that || depends only on +, and then give an algorithm constructing the CSG and specifying the nodes corresponding to _ and _.
	


 §.§ Defining a proper partition

	
	
	Let =(,_,_) be an instance of 0, where =(G,,).
	Assume that G has a vertex cover  of size at most .
	For each solution ∈ V(), we define ={^'=^'}.
	Then, we define ={∈ V()}; that is,  is the set of the equivalence classes under the equivalence relation “their restrictions on  are the same”.
	Clearly,  is a partition of V() and || is bounded by the number of mappings from  to , that is, ||≤^.
	
	In order to prove that  is proper, we introduce some notation.
	Let S⊆ V(G) be a vertex subset, and let S → be a mapping from S to .
	We define the substitution  as an instance (G^',,^') of 0 such that:
	
		
  * G^'=G∖ S; and
		
  * for each X^'∈ E(G^'), ^'(X^')=⋂_X∈ E^'X, 
		where E^'={X∈ E(G)  X∖ S=X^'} and X={X^'∈(X),}.
	
	We have the following lemma.
	
			
		Let ^' V(G)∖ S → and V(G) → be two mappings such that V(G)∖ S=^'.
		Then, ^' is a solution for S=(G^',,^') if and only if  is a solution for (G,,).
	
			
		We first show the if direction.
		Assume that  is a solution for (G,,).
		Let X^' be any hyperedge of G^'.
		For every hyperedge X of G such that X∖ S=X^', X∈(X) holds.
		Since S and X are compatible, by the definition of ^', (X)X^' is in ^'(X^').
		In addition, (X)X^'=X^'=^'X^' holds, and hence, ^' satisfies ^'(X^').
		Therefore, ^' is a solution for S.
		
		We next show the only-if direction.
		Assume that ^' is a solution for S=(G^',,^').
		Let X be any hyperedge of G.
		Then, there exists a hyperedge X^' of G^' such that X∖ S=X^'.
		From the definition of ^', there exists a mapping ∈(X) such that ^'X^'=X^', and S and  are compatible, that is, S∩ X=S∩ X.
		Since ^'X^'=X and X^'∪ (S∩ X)=X, X=X holds, and hence  satisfies (X).
		Therefore,  is a solution for (G,,).
	
	
	The following lemma implies that  is proper.
	
		
		Let  be a solution set in  such that = holds for every ∈.
		Then, [] is connected.
	
	
		By Lemma <ref>, there exists a one-to-one correspondence between  and the solution set for  which preserves the adjacency relation.
		Thus, we suffices to show that  is connected.
		Since  is a vertex cover of G, G[V(G)∖] has no edges.
		This means that  contains only 1-ary constraints.
		Therefore, a value assignment of each vertex v∈ V(G)∖ can be changed independently, and hence  is connected.
	
	


 §.§ Algorihm computing CSG

	
	
	In order to give an algorithm computing  correctly, we first show two claims.
	
		
		Let  be a mapping from  to .
		Then,  has a node corresponding to  if and only if =(G^',,^') has a solution.
	
	
		By Lemma <ref>,  has a solution ^' if and only if there exists a solution  for  such that V(G^')=^' and =.
		Since  is a partition of the solution set, there exists a set ∈ which contains ; and hence  has a node corresponding to .
	
	
		
		Let _1 and _2 be two nodes of , and let _1 → and _2 → be mappings corresponding to _1 and _2, respectively.
		Then, _1 _2 ∈ E() if and only if both of the following conditions hold:
		
			
  
			
				
  ∙ |_1_2|=1; and
				
  ∙ _1 and _2 has a common solution ^'.
			
		
	
	
		We first assume that the above two conditions hold.
		For each i∈{1,2}, let _i  V(G) → be a mapping such that _iV(G^')=^' and _i=_i.
		Then, by Lemma <ref>, _1 and _2 are adjacent solutions such that _1 ∈_1 and _2 ∈_2; and hence _1 _2 ∈ E().
		
		We next assume that _1 _2 ∈ E(), that is, there exist two solutions _1 and _2 such that |_1_2|=1, _1 ∈_1 and _2 ∈_2.
		From the definition of , _1_2.
		Therefore, _1_2=_1_2, and hence the first condition holds.
		Furthermore, _1V(G)∖=_2V(G)∖ holds.
		By Lemma <ref>, _1V(G)∖ and _2V(G)∖ are solutions for _1 and _2, respectively; and hence the second condition hold.
	
	
	From Claims <ref> and <ref>, we can construct the following algorithm to compute  with nodes corresponding to _ and _.
	
		
  Phase 1
		For each mapping  from  to , check if  has a solution.
		If so, create a node corresponding to .
		For each ∈{,}, if =_, it corresponds to _.
		
  Phase 2
		For each pair of two nodes _1 and _2, check if the two conditions of Claim <ref> hold.
		If so, join them by an edge.
	
	
	The correctness follows from Claims <ref> and <ref>.
	The first phase can be done in polynomial time for each mapping, because the constructed instance  of 0 contains only 1-ary constraints.
	Since |^|≤^, whole running time of this phase is O^*(^).
	In the second phase, the second condition of Claim <ref> can be checked as follows.
	Let _1 and _2 are constraint assignments in the substitutions _1 and _2.
	We now define for each X^'∈ E(G^') a constraint ^'(X^')=_1(X^')∩_2(X^').
	Then, a solution for (G^',,^') is also a solution for both of _1 and _2.
	Because (G^',,^') is an instance of 0 which contains only 1-ary constraints, we can solve it in polynomial time.
	Therefore, whole running time of this phase is O^*(^O()).
	
	We thus completed the proof of Theorem <ref>.



§ PROOF OF THEOREM <REF>


	Let =(,_,_) be an instance of 2, where =(G,,).
	We denote by  and  be the set of Boolean and non-Boolean vertices, respectively.
	We first define a partition similarly to Section <ref> as follows.
	For each solution ∈ V(), we define ={^'=^'}.
	Then, we define ={∈ V()}.
	Clearly,  is a partition of V() and ||≤^.
	In contrast to Section <ref>, however,  may be improper in this case.[
		As a simple example, let us consider 2-colorings of K_2.
		Clearly  is empty set, and hence all (indeed, only two) 2-colorings of G are in the same set of .
		On the other hand, they are not reconfigurable each other.]
	
	Therefore, as the first step of our algorithm, we modify the given instance so that  is proper by some preprocessing.
	More formally, we show the following lemma.
	
		
		Let =(,_,_) be an instance of 2, where =(G,,).
		We can compute in polynomial time an instance ^=(^,_^,_^) of 2 such that:
		
			
  * the number of non-Boolean vertices in ^ is at most that of ;
			
  *  is a yes-instance if and only if ^ is; and
			
  * the partition for ^ is proper.
		
	
	
	Then, we can compute the CSG in the same way as Section <ref>; we just replace  with .
	In order to check the existence of vertices and edges in the CSG, we solve instances of Boolean 2 which are constructed by the substitution operation.
	Since Boolean 2 can be solved in polynomial time <cit.>, the whole running time of the algorithm is O^*(^O()).
	In the remainder of this section, we prove Lemma <ref>.
	


 §.§ Implication graphs

	
	In order to describe a preprocessing, we first introduce the notion of “implication graph”, which was first introduced in <cit.> in order to prove the tractability of some variant of Boolean 2.
	Let =(G,,) be an instance of 0 where {0,1} is a domain; we consider the values 0 and 1 as Boolean values.
	We define the implication graph  for  as follows.
	For each vertex v∈ V(G) and for each value i∈ such that there exists a solution  with (v)=i, we add a vertex vi to .
	For each adjacent vertices v,w∈ V(G), add two arcs vi→wj and wj→vi if and only if (i,j)∉(vw), where  denote a negation of a Boolean value.
	Intuitively, an arc vi→wj means that if v is assigned i, then w must be assigned j in any solution.
	We note that  can be computed in polynomial time, since the existence of a vertex vi can be checked in polynomial time by solving Boolean 2 instance obtained by substituting (v)=i.
	We now prove the following lemma.
	
		
		If there exists a vertex v∈ V(G) such that v0 or v1 is contained in a directed cycle of , any two solutions _0 and _1 for  such that _0(v)=0 and _1(v)=1 are not reconfigurable.
		On the other hand, if  contains no directed cycles,  is connected.
	
	
		The second statement can be proved by the similar argument as the proof of Lemma 4.9 in <cit.>, although our implication graph is slightly different from the original one.
		
		
		
		
		
		
		
		
		
		
		
		
		
		Therefore, we prove the first statement.
		Let C=v_0i_0→v_1i_1→⋯→v_mi_m→v_0i_0 be a directed cycle in , where v_0=v and i_j∈{0,1}, 0≤ j ≤ m.
		From the construction, m≥ 1 holds.

		Without loss of generality, assume that i_0=0.
		Recall that each arc vi→wj means that if v is assigned i, then w must be assigned j.
		Then, _0(v_p)=i_p holds for every p∈0m.
		Moreover, by contrapositions of the above implications, _1(v_p)=i_p also holds for every p∈0m.
		We assume for a contradiction that _0 and _1 are reconfigurable, and consider the first solution  in a reconfiguration sequence such that (v_p)=i_p for some p∈0m.
		Since there exists an arc v_qi_q→v_pi_p in a directed cycle C, and hence (v_q) must be i_q.
		However, by the definition of , we have (v_q)=i_q, which is a contradiction.
	
	


 §.§ Preprocessing


	We now explain a preprocessing, which eliminates all “undesirable” vertices which prevent the partition from being proper.
	Let =(,_,_) be an instance of 2, where =(G,,).
	Without loss of generality, we can assume that a list (v) of every Boolean vertex v∈ is a subset of {0,1} by a simple value replacement.




	Then, we define the instance ^=(G^,,^) of 2 as the instance obtained by restricting all component of  on .
	That is, 
	
		
  * G^=G[]; and
		
  * for each X^'∈ E(G^), ^(X^')=⋂_X∈ E^'X, where E^'={X∈ E(G)  X ∩=X^'} and X={X^'∈(X)}.

	
	Let  be the set of vertices v∈ V(G) such that v0 or v1 are contained in a directed cycle of ^.
	By Lemma <ref>, in any solution for ^, all vertices v in  are fixed, that is, cannot be reconfigured at all.
	This property also holds for the original instance .
	Therefore, if __ holds, then we can immediately conclude that  is a no-instance.
	In the other case, we construct in polynomial time the substitution ^', where ^'=_=_.
	Then, we have the following proposition.
	
		 is a yes-instance if and only if ^'=(^',_V(G^'),_V(G^')) is.
	
	
		Because all vertices v in  are fixed,  is a yes-instance if and only if there exists a reconfiguration sequence  such that every solutions  in  satisfies =^'.
		By Lemma <ref>, there exists such a reconfiguration sequence if and only if there exists a reconfiguration sequence between _V(G^') and _V(G^') in ^'.
	

	Therefore, we can obtain an equivalent instance which satisfies the conditions (1) and (2) of Lemma <ref> by repeating the above transformation until the corresponding implication graph becomes acyclic or empty.
	Since the number of vertices decreases during the process, this can be done in polynomial time.
	Let ^=(^,_^,_^), where ^=(G^,,^), be an instance obtained by this preprocessing.	
	Then, it is left to prove that ^ satisfies the condition (3).
	


 §.§ Properity of the pertition

	












	Let  be the partition for ^, and let  be any solution set in  such that the restriction of every solution in  on  is .
	By Lemma <ref>, in order to prove that  is proper, it suffices to show that ^ has no directed cycles.
	
	Assume for a contradiction that ^ has a cycle C.
	Let ^ be an instance obtained by restricting all component of ^ on .
	From the definition of the implication graph, for each vertex vi in C, there exists a solution ^' for ^ such that ^'(v)=i.
	By Lemma <ref>, a mapping  such that = and =^' is a solution for ^.
	Moreover, =^' is a solution for the restricted instance ^.
	Therefore, ^ has a vertex vi.
	For each arc vi→wj, a mapping (i, j) is not contained in the constraint ^'(vw) of vw in ^.
	Recall that ^'(vw) is the mapping set 	⋂_X∈ E^'X, where E^'={X∈ E(G^)  X∖={v,w}} and X={{v,w}∈(X),}.
	Since G^ has a hyperedge of size at most two, E^' contains exactly one edge vw.
	Therefore, ^'(vw)=^(vw) holds, and hence (i, j) not contained in ^(vw).
	Moreover, the constraint ^(vw) does not contain (i, j), too.
	From the definition, ^ contains the arc vi→wj.
	By the above observations, ^ has a directed cycle C, which contradicts that we have eliminated all directed cycles from the implication graph by the preprocessing.
	
	Thus, we have proved Lemma <ref> and hence Theorem <ref>.
	









