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

Describing paths up to homotopy

Describing paths up to homotopy

(Groupoid multiplication example)

Walks

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

Illustration of the lemma.

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

(a cycle in G winding twice around a cycle in H)

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.

Tight cycles

(a cycle in G winding twice around a cycle in H)

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

Thank you!

/