Digraphs with caterpillar duality

 Semigroup Seminar York
Catarina Carvalho
PAM, UH
05/12/2023 (updated: 2023-12-06)
1 / 14

Homomorphism problem

Given two finite digraphs $G$ and $H$ is there a homomorphism $h: G \longrightarrow H$?

We fix a target digraph $H$ and ask which digraphs admit a homomorphism to $H$, $CSP(H)= HOM(H) =\{G: G\longrightarrow H\}$

2 / 14

Homomorphism problem

Given two finite digraphs $G$ and $H$ is there a homomorphism $h: G \longrightarrow H$?

We fix a target digraph $H$ and ask which digraphs admit a homomorphism to $H$, $CSP(H)= HOM(H) =\{G: G\longrightarrow H\}$

Example: The 2-colourability problem is equivalent to $CSP(K_2)$.

2 / 14

Retraction and List Homomorphism

$CSP(H_c)$ - retraction problem:

given a digraph $G$ containing a copy of $H$, decide if $G$ retracts to $H$.

If $H=(H, E(H))$, then $H_c=(H; E(H), \{c_1\}, \{c_2\}, \dots \{c_n\})$

3 / 14

Retraction and List Homomorphism

$CSP(H_c)$ - retraction problem:

given a digraph $G$ containing a copy of $H$, decide if $G$ retracts to $H$.

If $H=(H, E(H))$, then $H_c=(H; E(H), \{c_1\}, \{c_2\}, \dots \{c_n\})$

$CSP(H_u)= LHOM(H)$ - list homomorphism: given $G$ and lists $L_x \subset H$, for each $x\in G$, decide if there exists a homomorphism $f: G \longrightarrow H$ s.t. $f (x)\in L_x$

LHOM correspond to conservative CSPs

3 / 14

Retraction and List Homomorphism

$CSP(H_c)$ - retraction problem:

given a digraph $G$ containing a copy of $H$, decide if $G$ retracts to $H$.

If $H=(H, E(H))$, then $H_c=(H; E(H), \{c_1\}, \{c_2\}, \dots \{c_n\})$

$CSP(H_u)= LHOM(H)$ - list homomorphism: given $G$ and lists $L_x \subset H$, for each $x\in G$, decide if there exists a homomorphism $f: G \longrightarrow H$ s.t. $f (x)\in L_x$

LHOM correspond to conservative CSPs

Proved by Bulatov and Zhuk (independently) in 2017.

Theorem [Bulatov/ Zhuk/ .....]: If $\mathcal{B}$ is preserved by a weak-near-unanimity operation then $CSP(\mathcal{B})$ is in $\mathbf{P}$, otherwise it is $\mathbf{NP}$-complete.

A weak-near-unanimity operation is an $n$-ary operation $w$ s.t.

$$w(x, y, y, \ldots, y)=w(y, x, y, \ldots, y)=\cdots =w(y, \ldots, y, x)$$

a digraph $H$ being preserved by $w$ means that $w: H^n \longrightarrow H$ is an homorphism.

3 / 14

Interesting operations

Example: Oriented paths are preserved by $\min(x_1, \ldots, x_n)$ operation, for every $n\ge 1$.

Example: An undirected square is not preserved by a $\min$ operation.

4 / 14

Interesting operations

Example: Oriented paths are preserved by $\min(x_1, \ldots, x_n)$ operation, for every $n\ge 1$.

Example: An undirected square is not preserved by a $\min$ operation.

An $n$-ary operation $f$ is

idempotent if $f(x, \ldots, x)=x$,
symmetric if $f(x_1, \ldots, x_n)= f(x_{\pi(1)}, \ldots, x_{\pi(n)})$ for any permutation $\pi$ of $\{1, \ldots, n\}$,
totally symmetric (TS) if $f(x_1, \ldots, x_n)=f(y_1,\ldots, y_n)$ whenever $\{x_1, \ldots, x_n\}=\{y_1, \ldots, y_n\}$,
near-unanimity (NU) if $f(x, y, \ldots, y)=f(y, x, y, \ldots, y)=\cdots= f(y, \ldots, y, x)=y$

Example: $\min$ is a TSI operation. It can be defined of any arity we want.

4 / 14

More operations

A ternary operation $m$ is majority if $m(x, y, y)=m(y, x, y)=m(y, y, x)=y$.

Example: The undirected 3-path is preserved by a majority.

Example: The undirected 6-cycle is not preserved by a majority.

5 / 14

More operations

A ternary operation $m$ is majority if $m(x, y, y)=m(y, x, y)=m(y, y, x)=y$.

Example: The undirected 3-path is preserved by a majority.

Example: The undirected 6-cycle is not preserved by a majority.

To look at homomorphism, sometimes it makes sense to look at what does not admit an homomorphism to a given structure...

5 / 14

Duality land

The idea is to justify the existence of a homomorphism by the non-existence of other homomorphisms.

If all structures $\mathcal{A}\not\longrightarrow \mathcal{B}$ can be characterized in uniform way then we can obtain information about the complexity of $CSP(\mathcal{B})$.

6 / 14

Obstruction sets

An obstruction set for a digraph $\mathcal{B}$ is a class, $\mathcal{O}_{\mathcal{B}}$, of digraphs such that, for all $\mathcal{A}$

$$\mathcal{A}\mapsto\mathcal{B} \ \ \ {\rm iff} \ \ \mathcal{A'}\not\mapsto \mathcal{A}\ \ \ \ \ \ \ \forall \mathcal{A'}\in \mathcal{O}_{\mathcal{B}}.$$

Example: If $\mathcal{B}$ is a bipartite graph then $\mathcal{O}_{\mathcal{B}}$ can be chosen to consist of all odd cycles.

Example: If $\mathcal{B}$ is the transitive tournament of $k$ vertices, we can choose $\mathcal{O}_{\mathcal{B}}$ to consist of the directed path on $k+1$ vertices.

7 / 14

Dualities