## Homomorphism reconfiguration via homotopy

March 7, STACS 2015, Munich

Marcin Wrochna

## 3-Recoloring

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.

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

## Graph homomorphism

$\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$.

## $H$-Recoloring

Input:  $G$,    $\alpha,\beta$ – $H$-colorings of $G$
Question:  Can $\alpha$ be recolored to $\beta$?

### Hom$(G,H)$

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))$

## $H$-Recoloring

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.

### My results

• 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…

## Why graphs without $C_4$?

$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!

## Example

A homomorphism from $G$ to $H$:

## Example

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

## Example

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

## Homotopy

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$:

## Homotopy

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):

## Homotopy – invariant

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$!

## Describing paths up to homotopy

• 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}$

## Describing paths up to homotopy

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

## Describing paths up to homotopy

• 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)

## Walks

• $\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.

## Example

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

## One crucial lemma

$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$$

## One crucial lemma

$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}$$

## Topologically valid

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.

## Tight cycles

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.

## Characterization

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
• $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\|)$.

## Example

$G = C_8$. We can move $v$ around one cycle of $H$ any number of times
(but the length is always odd).

## Example

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

## Proof of characterization

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))$.

## Proof of characterization

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$

## Proof of characterization

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.

## All solutions

Let $\alpha,\beta: G\to H$, $v\in V(G)$.
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\|)$.

## All solutions

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:
• $\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\|)$.

## Open questions

• 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!

/