+ - 0:00:00
Notes for current slide
Notes for next slide

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:GH?

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

2 / 14

Homomorphism problem

Given two finite digraphs G and H is there a homomorphism h:GH?

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

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

2 / 14

Retraction and List Homomorphism

CSP(Hc) - retraction problem:

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

If H=(H,E(H)), then Hc=(H;E(H),{c1},{c2},{cn})

3 / 14

Retraction and List Homomorphism

CSP(Hc) - retraction problem:

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

If H=(H,E(H)), then Hc=(H;E(H),{c1},{c2},{cn})

CSP(Hu)=LHOM(H) - list homomorphism: given G and lists LxH, for each xG, decide if there exists a homomorphism f:GH s.t. f(x)Lx

LHOM correspond to conservative CSPs

3 / 14

Retraction and List Homomorphism

CSP(Hc) - retraction problem:

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

If H=(H,E(H)), then Hc=(H;E(H),{c1},{c2},{cn})

CSP(Hu)=LHOM(H) - list homomorphism: given G and lists LxH, for each xG, decide if there exists a homomorphism f:GH s.t. f(x)Lx

LHOM correspond to conservative CSPs

Proved by Bulatov and Zhuk (independently) in 2017.

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

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

w(x,y,y,,y)=w(y,x,y,,y)==w(y,,y,x)

a digraph H being preserved by w means that w:HnH is an homorphism.

3 / 14

Interesting operations

Example: Oriented paths are preserved by min(x1,,xn) operation, for every n1.

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

4 / 14

Interesting operations

Example: Oriented paths are preserved by min(x1,,xn) operation, for every n1.

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

An n-ary operation f is

  • idempotent if f(x,,x)=x,

  • symmetric if f(x1,,xn)=f(xπ(1),,xπ(n)) for any permutation π of {1,,n},

  • totally symmetric (TS) if f(x1,,xn)=f(y1,,yn) whenever {x1,,xn}={y1,,yn},

  • near-unanimity (NU) if f(x,y,,y)=f(y,x,y,,y)==f(y,,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 A⟶̸B can be characterized in uniform way then we can obtain information about the complexity of CSP(B).

6 / 14

Obstruction sets

An obstruction set for a digraph B is a class, OB, of digraphs such that, for all A

AB   iff  A↦̸A       AOB.

Example: If B is a bipartite graph then OB can be chosen to consist of all odd cycles.

Example: If B is the transitive tournament of k vertices, we can choose OB to consist of the directed path on k+1 vertices.

7 / 14

Dualities

A structure B has "nice" duality if OB can be chosen to be "simple":

  • Nice= Finite, Simple= finite. Ex: B is a transitive tournament;

  • Nice= Path, Simple= consisting of "paths" Ex: B is an oriented path (Hell, Zhu'94);

  • Nice= Caterpillar, Simple= consisting of ... Ex: ...later...

  • Nice= Tree, Simple= consisting of "trees" Ex: B is an oriented tree that is preserved by a min order (Hell, Nesestril, Zhu'96).

8 / 14

Dualities

A structure B has "nice" duality if OB can be chosen to be "simple":

  • Nice= Finite, Simple= finite. Ex: B is a transitive tournament;

  • Nice= Path, Simple= consisting of "paths" Ex: B is an oriented path (Hell, Zhu'94);

  • Nice= Caterpillar, Simple= consisting of ... Ex: ...later...

  • Nice= Tree, Simple= consisting of "trees" Ex: B is an oriented tree that is preserved by a min order (Hell, Nesestril, Zhu'96).

We then have:

  • B has finite duality iff CSP(B) is FO-definable iff CSP(B) is in non-uniform AC0 (Larose, Loten, Tardif'07; Libkin'04)
8 / 14

Dualities

A structure B has "nice" duality if OB can be chosen to be "simple":

  • Nice= Finite, Simple= finite. Ex: B is a transitive tournament;

  • Nice= Path, Simple= consisting of "paths" Ex: B is an oriented path (Hell, Zhu'94);

  • Nice= Caterpillar, Simple= consisting of ... Ex: ...later...

  • Nice= Tree, Simple= consisting of "trees" Ex: B is an oriented tree that is preserved by a min order (Hell, Nesestril, Zhu'96).

We then have:

  • B has finite duality iff CSP(B) is FO-definable iff CSP(B) is in non-uniform AC0 (Larose, Loten, Tardif'07; Libkin'04)

  • if B has bounded pathwidth duality then CSP(B) is in NL (Dalmau'05)

8 / 14

Dualities

A structure B has "nice" duality if OB can be chosen to be "simple":

  • Nice= Finite, Simple= finite. Ex: B is a transitive tournament;

  • Nice= Path, Simple= consisting of "paths" Ex: B is an oriented path (Hell, Zhu'94);

  • Nice= Caterpillar, Simple= consisting of ... Ex: ...later...

  • Nice= Tree, Simple= consisting of "trees" Ex: B is an oriented tree that is preserved by a min order (Hell, Nesestril, Zhu'96).

We then have:

  • B has finite duality iff CSP(B) is FO-definable iff CSP(B) is in non-uniform AC0 (Larose, Loten, Tardif'07; Libkin'04)

  • if B has bounded pathwidth duality then CSP(B) is in NL (Dalmau'05)

  • B has bounded treewidth duality iff it has weak-NU polymorphisms of all but finitely many arities (Barto, Kozik '09)
8 / 14

Dualities

A structure B has "nice" duality if OB can be chosen to be "simple":

  • Nice= Finite, Simple= finite. Ex: B is a transitive tournament;

  • Nice= Path, Simple= consisting of "paths" Ex: B is an oriented path (Hell, Zhu'94);

  • Nice= Caterpillar, Simple= consisting of ... Ex: ...later...

  • Nice= Tree, Simple= consisting of "trees" Ex: B is an oriented tree that is preserved by a min order (Hell, Nesestril, Zhu'96).

We then have:

  • B has finite duality iff CSP(B) is FO-definable iff CSP(B) is in non-uniform AC0 (Larose, Loten, Tardif'07; Libkin'04)

  • if B has bounded pathwidth duality then CSP(B) is in NL (Dalmau'05)

  • B has bounded treewidth duality iff it has weak-NU polymorphisms of all but finitely many arities (Barto, Kozik '09)
  • B has tree duality iff it has TSIs of all arities (Dalmau, Pearson '99)
8 / 14

Caterpillar duality

A (mn)-ary operation f is m-block symmetric if f(S1,,Sn)=f(T1,,Tn)

whenever {S1,,Sn}={T1,,Tn} , with Si={xi1,,xim}.

f is an m-ABS operation if it is m-block symmetric and it satisfies the absorptive rule f(S1,S2,S3,,Sn)=f(S2,S2,S3,,Sn) whenever S2S1.

Example: For a fixed linear order the operation min(max(x11,,x1m),,max(xn1,,xnm)) is an m-ABS operation.

9 / 14

Caterpillar duality

A (mn)-ary operation f is m-block symmetric if f(S1,,Sn)=f(T1,,Tn)

whenever {S1,,Sn}={T1,,Tn} , with Si={xi1,,xim}.

f is an m-ABS operation if it is m-block symmetric and it satisfies the absorptive rule f(S1,S2,S3,,Sn)=f(S2,S2,S3,,Sn) whenever S2S1.

Example: For a fixed linear order the operation min(max(x11,,x1m),,max(xn1,,xnm)) is an m-ABS operation.

Theorem[C., Dalmau, Krokhin '08]: Tfae

  • B has caterpillar duality;
  • coCSP(B) is definable by a linear monadic Datalog program with at most one EDB per rule;
  • B has m-ABS polymorphisms of arity mn, for all m,n1;
  • B is homomorphically equivalent to a structure A with polymorphisms xy and xy for some distributive lattice (A,,);
  • B is homomorphically equivalent to a structure A with polymorphisms xy and xy for some lattice (A,,).
9 / 14

Example

For reflexive digraphs H, MinHOM(H) is polynomial iff H has a Min-Max ordering. (Gupta, Hell, Karimi, Rafiey '08)

If a digraph has a Min-Max ordering then it has caterpillar duality.

10 / 14

Example

For reflexive digraphs H, MinHOM(H) is polynomial iff H has a Min-Max ordering. (Gupta, Hell, Karimi, Rafiey '08)

If a digraph has a Min-Max ordering then it has caterpillar duality.

An attempt at simplification

If H has caterpillar duality then it also has tree duality and so it is preserved by TSIs operations of all arities (set function)

10 / 14

Example

For reflexive digraphs H, MinHOM(H) is polynomial iff H has a Min-Max ordering. (Gupta, Hell, Karimi, Rafiey '08)

If a digraph has a Min-Max ordering then it has caterpillar duality.

An attempt at simplification

If H has caterpillar duality then it also has tree duality and so it is preserved by TSIs operations of all arities (set function)

From a 6-ary 2-ABS polymorphism f, we obtain m(x,y,z)=f(x,y,z,x,y,z) a majority polymorphism.

10 / 14

Example

For reflexive digraphs H, MinHOM(H) is polynomial iff H has a Min-Max ordering. (Gupta, Hell, Karimi, Rafiey '08)

If a digraph has a Min-Max ordering then it has caterpillar duality.

An attempt at simplification

If H has caterpillar duality then it also has tree duality and so it is preserved by TSIs operations of all arities (set function)

From a 6-ary 2-ABS polymorphism f, we obtain m(x,y,z)=f(x,y,z,x,y,z) a majority polymorphism.

So caterpillar duality implies set function and majority.

10 / 14

Retraction and List Homomorphism

CSP(Hc) - retraction problem: given a digraph G containing a copy of H, decide if G retracts to H.

we use idempotent polymorphisms

11 / 14

Retraction and List Homomorphism

CSP(Hc) - retraction problem: given a digraph G containing a copy of H, decide if G retracts to H.

we use idempotent polymorphisms

CSP(Hu)=LHOM(H) - list homomorphism: G and LxH for each xG, is there a homomorphism f:GH s.t. f(x)Lx

we use conservative polymorphisms

11 / 14

Retraction and List Homomorphism

CSP(Hc) - retraction problem: given a digraph G containing a copy of H, decide if G retracts to H.

we use idempotent polymorphisms

CSP(Hu)=LHOM(H) - list homomorphism: G and LxH for each xG, is there a homomorphism f:GH s.t. f(x)Lx

we use conservative polymorphisms

LHOM Reflexive graphs

Theorem [Feder, Hell '98]: For a reflexive graph H the LHOM problem is solvable in polynomial time if H is an interval graph, otherwise it is NP-complete.

Theorem [C., Dalmau, Krokhin '08]: Interval graphs have caterpillar duality.

In this case, caterpillar duality = set function + majority

11 / 14

Retraction reflexive digraphs

Theorem [C, Dalmau, Krokhin '08]: For any reflexive digraph H, tfae

  • Hc has caterpillar duality;
  • Hc has set function and a majority polymorphism;
  • Hc has path duality
12 / 14

Retraction reflexive digraphs

Theorem [C, Dalmau, Krokhin '08]: For any reflexive digraph H, tfae

  • Hc has caterpillar duality;
  • Hc has set function and a majority polymorphism;
  • Hc has path duality

List homomorphism for undirected graphs

  • Undirected graphs with a conservative majority are the bi-arc graphs. (Feder, Hell, Huang '03)

The majority operation was not explicit, except for trees.

12 / 14

Retraction reflexive digraphs

Theorem [C, Dalmau, Krokhin '08]: For any reflexive digraph H, tfae

  • Hc has caterpillar duality;
  • Hc has set function and a majority polymorphism;
  • Hc has path duality

List homomorphism for undirected graphs

  • Undirected graphs with a conservative majority are the bi-arc graphs. (Feder, Hell, Huang '03)

The majority operation was not explicit, except for trees.

  • Undirected graphs with conservative set function are the bi-arc graphs with no loopless edge (Larose, Lemaitre '13 )
12 / 14

Retraction reflexive digraphs

Theorem [C, Dalmau, Krokhin '08]: For any reflexive digraph H, tfae

  • Hc has caterpillar duality;
  • Hc has set function and a majority polymorphism;
  • Hc has path duality

List homomorphism for undirected graphs

  • Undirected graphs with a conservative majority are the bi-arc graphs. (Feder, Hell, Huang '03)

The majority operation was not explicit, except for trees.

  • Undirected graphs with conservative set function are the bi-arc graphs with no loopless edge (Larose, Lemaitre '13 )

Theorem: Bi-arc graphs with no loopless edge have caterpillar duality.

In this case, caterpillar duality = set function + majority

It also provides an explicit majority for a bigger family of graphs.

12 / 14

LHOM for directed digraphs

  • Digraphs with conservative set function are bi-arc digraphs.

Theorem [Hell, Rafiey '19]: Let H be a digraph. Tfae

  • H admits a conservative semilattice polymorphism;
  • H admits conservative cyclic polymorphisms of all arities;
  • H admits conservative symmetric polymorphisms of all arities;
  • H admits conservative TS polymorphisms of all arities, i.e. CSP(Hu) has width 1;
  • H is a bi-arc digraph.
13 / 14

LHOM for directed digraphs

  • Digraphs with conservative set function are bi-arc digraphs.

Theorem [Hell, Rafiey '19]: Let H be a digraph. Tfae

  • H admits a conservative semilattice polymorphism;
  • H admits conservative cyclic polymorphisms of all arities;
  • H admits conservative symmetric polymorphisms of all arities;
  • H admits conservative TS polymorphisms of all arities, i.e. CSP(Hu) has width 1;
  • H is a bi-arc digraph.

Bi-arc digraphs don't all have majority, so not all have caterpillar duality

Theorem: End-consistent bi-arc digraphs have caterpillar duality.

13 / 14

LHOM for directed digraphs

  • Digraphs with conservative set function are bi-arc digraphs.

Theorem [Hell, Rafiey '19]: Let H be a digraph. Tfae

  • H admits a conservative semilattice polymorphism;
  • H admits conservative cyclic polymorphisms of all arities;
  • H admits conservative symmetric polymorphisms of all arities;
  • H admits conservative TS polymorphisms of all arities, i.e. CSP(Hu) has width 1;
  • H is a bi-arc digraph.

Bi-arc digraphs don't all have majority, so not all have caterpillar duality

Theorem: End-consistent bi-arc digraphs have caterpillar duality.

Even for digraphs with conservative majority it would be nice to have a better classification.

13 / 14

Thank you!

14 / 14

Homomorphism problem

Given two finite digraphs G and H is there a homomorphism h:GH?

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

2 / 14
Paused

Help

Keyboard shortcuts

, , Pg Up, k Go to previous slide
, , Pg Dn, Space, j Go to next slide
Home Go to first slide
End Go to last slide
Number + Return Go to specific slide
b / m / f Toggle blackout / mirrored / fullscreen mode
c Clone slideshow
p Toggle presenter mode
t Restart the presentation timer
?, h Toggle this help
Esc Back to slideshow