**March 7, STACS 2015, Munich**

Marcin Wrochna

**Input: ** [$G$], [$\alpha,\beta$] – 3-colorings
, [$\mathcal{l}$]

**Question: ** Can [$\alpha$] be recolored to [$\beta$]?

in [$\leq\mathcal{l}$] steps?

**3-Recoloring** is in **P**.

(Bonsma et al. 2007)

**4-Recoloring** is **PSPACE**-complete.

(Johnson et al. 2014)
**Shortest 3-Recoloring** is in **P**.

[$\alpha : V(G)\to V(H) $] such that

[$uv$] is an edge [$\implies \alpha(u)\alpha(v)$] is an edge

[$k$]-coloring = homomorphism to [$K_k$]

[$\alpha$] is also called an [$H$]-coloring of [$G$].

**Input: ** [$G$], [$\alpha,\beta$] – [$H$]-colorings of [$G$]

**Question: ** Can [$\alpha$] be recolored to [$\beta$]?

vertices = [$H$]-colorings of [$G$]

edges = one color change

**Question = ** Is there a path from [$\alpha$] to [$\beta$] in Hom[$(G,H)$]?

Hom[$(G,H)$] was used for [$\chi$] lower bounds like Kneser's Conjecture

[$\chi(G_{n,k})=n-2k+2$]

[$H^G$] was used to prove a case of Hedetniemi' Conjecture

[$\chi(G\times H) = \min(\chi(G), \chi(H)) $]

**Input: ** [$G$], [$\alpha,\beta$] – [$H$]-colorings of [$G$]

**Question: ** Can [$\alpha$] be recolored to [$\beta$]?

**[$K_3$]-Recoloring** is in **P**.

**[$K_4$]-Recoloring** is **PSPACE**-complete.

- For [$H$] with no [$C_4$] subgraph,
**[$H$]-Recoloring**is in**P**. - [$\mathcal{O}(|G|^2+|H|)$] algorithm for finding a solution.
- For [$H$] with no [$C_4$] subgraph,
**Shortest [$H$]-Recoloring**is in**P**. - A description of all solutions…

[$H$] has no [$C_4$] subgraphs if and only if:

For every two colors in [$V(H)$], there is [$\leq 1$] color compatible with both.

or: Whenever a vertex is recolored, all its neighbors have one color.

Is this property enough? Yes!

A homomorphism from [$G$] to [$H$]:

[$H$]-recoloring [$G$] can look like this:

Assumption: If a vertex is recolored, all its neighbors have one color.

Assumption: If a vertex is recolored, all its neighbors have one color.

Then we can view the recoloring as a homotopy (continuous transformation) of [$G$] within [$H$]:

Assumption: If a vertex is recolored, all its neighbors have one color.

**If** [$\alpha$] can be recolored to [$\beta$],

**then** the corresponding continuous maps are homotopic

(can be transformed continuously into one another):

Assumption: If a vertex is recolored, all its neighbors have one color.

**If** [$\alpha$] can be recolored to [$\beta$],

**then** the corresponding continuous maps are homotopic.

For example, the left cycle of [$G$] will always go around the left cycle of [$H$]!

- oriented edge: [$(u,v)$] for [$\{u,v\}\in E(H)$]
- walk = sequence of oriented edges: [$W = (v_1,v_2) (v_2, v_3) \dots (v_{n-1},v_n)$]
- reducing = removing [$(u,v) (v,u)$] greedily, call the result [$\overline{W}$]

- reducing = removing [$(u,v) (v,u)$] greedily, call the result [$\overline{W}$]

- reducing = removing [$(u,v) (v,u)$] greedily
- [$\pi(H)$] =
- elements: reduced walks in [$H$]
- multiplication: [$W_1 \cdot W_2 = \overline{W_1 W_2}$]
- inverse: [$W^{-1} = (v_n,v_{n-1}) \dots (v_3,v_2) (v_2,v_1)$]

- (groupoid = like a group, but multiplication is a partial function)

- [$\alpha:G\to H$], [$W$] – a walk in [$G$].

Then [$\alpha(W)$] is a walk in [$H$]. - [$S=\alpha_1,\dots,\alpha_{|S|}$] – an [$H$]-recoloring sequence of [$G$].

For [$v\in V(G)$],

[$S(v) = (\alpha_1(v), \_)\ \ (\_, \alpha_2(v))\ \ (\alpha_2(v), \_)\ \ \dots\ \ (\_, \alpha_{|S|}(v))$] defines a unique walk in [$H$].

**Question:** given [$v$] and [$Q\in\pi(H)$],

**is there a solution from [$\alpha$] to [$\beta$] such that [$\overline{S(v)}=Q$]?**

[$S(v)$] has even length and reduction doesn't change parity.

So [$Q$] must have even length.

A walk [$W$] from [$u$] to [$v$] (in [$G$]) is [$H$]-recolored.

[$S=\alpha,\dots,\beta$] – an [$H$]-recoloring sequence of [$G$].

[$W$] – a walk from [$u$] to [$v$] in [$G$]. Then
$$\overline{\alpha(W)} \cdot \overline{S(v)} \cdot \overline{\beta(W)}^{-1} \cdot \overline{S(u)}^{-1} = \varepsilon$$

[$S=\alpha,\dots,\beta$] – an [$H$]-recoloring sequence of [$G$].

[$W$] – a walk from [$u$] to [$v$] in [$G$]. Then
$$\overline{S(u)} = \overline{\alpha(W)} \cdot \overline{S(v)} \cdot \overline{\beta(W)}^{-1}$$

So if we know [$\alpha,\beta$] and [$S(v)$], then we known all [$S$].

For every closed walk [$C$] (from [$v$] to [$v$]) in [$G$],

$$\overline{S(v)}= \overline{\alpha(C)} \cdot \overline{S(v)} \cdot \overline{\beta(C)}^{-1}$$

Let [$Q = \overline{S(v)}$] for some solution [$S$].

Then for every closed walk [$C$] (from [$v$] to [$v$]) in [$G$],
$$\overline{\beta(C)} = Q^{-1} \cdot \overline{\alpha(C)} \cdot Q$$
This means [$\overline{\alpha(C)}$] and [$\overline{\beta(C)}$] are *conjugate*, and [$Q$] witnesses this.

We will call [$Q$]s with this property *topologically valid* (for [$v$]).

Surprisingly, if we find such a [$Q$],

then this *almost* implies a corresponding a valid recoloring sequence.

Call a cycle [$C = e_1 \dots e_n$] in [$G$] **tight** if

[$\alpha(C)$] is reduced and also [$e_n\neq e_1^{-1}$].

In other words, it never backtracks.

No vertex of a tight cycle can ever be recolored!

So if for some solution [$S$] we have [$Q = \overline{S(v)}$],
and [$v$] is on a tight cycle,

then [$Q = \varepsilon$] is the only possibility.

Similarly, if some other vertex [$u$] is on a tight cycle,

then [$Q = \overline{\alpha(W)}\cdot\overline{\beta(W)}^{-1}$] is the only possibility.

Fix [$v\in V(G)$]. Let [$Q\in\pi(H)$].

Then there is a solution [$S$] from [$\alpha$] to [$\beta$] such that [$\overline{S(v)}=Q$] iff

Then there is a solution [$S$] from [$\alpha$] to [$\beta$] such that [$\overline{S(v)}=Q$] iff

- [$Q$] has even length
- [$Q$] is topologically valid for [$v$], and
- [$Q = \overline{\alpha(W)}\cdot\overline{\beta(W)}^{-1}$] for any walk to a vertex on a tight cycle.

Furthermore, given such a [$Q$], we can find a valid recoloring sequence
such that [$S(v)=Q$] and all [$S(u)$] are reduced,
in time [$\mathcal{O}(|G|^2+|G|\cdot|Q|+\|H\|)$].

[$G = C_8$]. We can move [$v$] around one cycle of [$H$] any number of times

(but the length is always odd).

[$G = C_8$]. Paths going around the other cycle are not topologically valid.

Let [$Q \in \pi(H)$] be even and topologically valid for [$\alpha,\beta,v$].

Define [$S_u := \overline{\alpha(W)} \cdot Q \cdot \overline{\beta(W)}^{-1} $] for any/every walk [$W$] from [$u$] to [$v$].

We construct a solution such that [$S(u)=S_u$].

Let [$S_u = (u^0, u^1) (u^1, u^2) \dots $]

Vertex [$u$] is recolored from [$\alpha(u)=u^0$] to [$u^2$],
from [$u^2$] to [$u^4, \dots$]

Let [$xy\in E(G)$]

Then [$ S_x = \alpha((x,y)) \cdot S_y \cdot \beta((y,x)) $].

Let [$xy\in E(G)$].
Then [$ S_x = \alpha((x,y)) \cdot S_y \cdot \beta((y,x)) $].

Either [$\alpha((x,y))=(x^0,y^0)$] will reduce with [$S_y$] or not.

That is, either [$S_y = (y^0,x^0) S_x \dots$] or [$S_x = (x^0,y^0) S_y \dots$]

Correspondingly, [$x$] must be recolored **after** or **before** [$y$].

This gives an orientation of each edge of [$E(G)$].

If there is no cycle, the ordering gives a solution valid on each edge!

For example:

[$S_x = \hspace{3em} (x^0,y^2) (y^2,x^2) (x^2,y^4) \dots $] and

[$S_y = (y^0,x^0) (x^0,y^2) (y^2,x^2) (x^2, y^4) \dots $]

Suppose there is a cycle [$x_1,x_2,\dots$]

such that [$S_{x_{i+1}} = (x_{i+1},x_i) S_{x_i} \dots $].

Then [$S_{x_{i+1}} = (x_{i+1},x_i)(x_{i},x_{i-1}) S_{x_{i-1}} \dots $],

So the cycle is tight and all [$S_{x_{i}}$] should be empty!

This gives an algorithm that builds all the solution [$S$] from [$Q=\overline{S(v)}$] if possible.

Let [$\alpha,\beta: G\to H$], [$v\in V(G)$].

The set of topologically valid walks in [$\pi(H)$] is equal:

The set of topologically valid walks in [$\pi(H)$] is equal:

- [$\emptyset$]
- [$\{P\}$] for some [$P\in\pi(H)$]
- [$\{P\cdot R^n \mid n\in\mathbb{Z}\}$] for some [$P,R\in\pi(H)$], or
- the set of all [$\alpha(v)\to\beta(v)$] walks in [$\pi(H)$].

Furthermore, we can say which case holds and output [$P,R$]

in time [$\mathcal{O}(\|G\|\cdot|G|+\|H\|)$].

Let [$\alpha,\beta: G\to H$], [$v\in V(G)$].

The set of walks [$Q\in \pi(H)$] such that [$Q=\overline{S(v)}$] for some solution [$S$] is equal:

The set of walks [$Q\in \pi(H)$] such that [$Q=\overline{S(v)}$] for some solution [$S$] is equal:

- [$\emptyset$]
- [$\{P\}$] for some [$P\in\pi(H)$]
- [$\{P\cdot R^n \mid n\in\mathbb{Z}\}$] for some [$P,R\in\pi(H)$], or
- the set of all
**even**[$\alpha(v)\to\beta(v)$] walks in [$\pi(H)$].

Furthermore, we can say which case holds and output [$P,R$]

in time [$\mathcal{O}(\|G\|^2+\|H\|)$].

- Is
**[$H$]-Recoloring**always**P**or**PSPACE**-complete for fixed [$H$]? - Is there a generalization to CSPs?

(a connection to tractable cases of SAT reconfiguration?) - Are there more implications for [$Hom(G,H)$] as a simplicial complex?

**Thank you!**

/