Digraphs with caterpillar duality
Semigroup Seminar York
Catarina Carvalho
PAM, UH
05/12/2023 (updated: 2023-12-06)
Homomorphism problem
Given two finite digraphs G and H is there a homomorphism h:G⟶H?
We fix a target digraph H and ask which digraphs admit a homomorphism to H, CSP(H)=HOM(H)={G:G⟶H}
Homomorphism problem
Given two finite digraphs G and H is there a homomorphism h:G⟶H?
We fix a target digraph H and ask which digraphs admit a homomorphism to H, CSP(H)=HOM(H)={G:G⟶H}
Example: The 2-colourability problem is equivalent to CSP(K2).
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})
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 Lx⊂H, for each x∈G, decide if there exists a homomorphism f:G⟶H s.t. f(x)∈Lx
LHOM correspond to conservative CSPs
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 Lx⊂H, for each x∈G, decide if there exists a homomorphism f:G⟶H 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:Hn⟶H is an homorphism.
Interesting operations
Example: Oriented paths are preserved by min(x1,…,xn) operation, for every n≥1.
Example: An undirected square is not preserved by a min operation.
Interesting operations
Example: Oriented paths are preserved by min(x1,…,xn) operation, for every n≥1.
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.
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.
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...
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).
Obstruction sets
An obstruction set for a digraph B is a class, OB, of digraphs such that, for all A
A↦B iff A′↦/A ∀A′∈OB.
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.
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).
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)
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)
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)
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)
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 S2⊆S1.
Example: For a fixed linear order the operation min(max(x11,…,x1m),…,max(xn1,…,xnm)) is an m-ABS operation.
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 S2⊆S1.
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;
- co−CSP(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,n≥1;
- B is homomorphically equivalent to a structure A with polymorphisms x⊓y and x⊔y for some distributive lattice (A,⊔,⊓);
- B is homomorphically equivalent to a structure A with polymorphisms x⊓y and x⊔y for some lattice (A,⊔,⊓).
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.
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)
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.
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.
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
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 Lx⊂H for each x∈G, is there a homomorphism f:G⟶H s.t. f(x)∈Lx
we use conservative polymorphisms
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 Lx⊂H for each x∈G, is there a homomorphism f:G⟶H 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
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
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.
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 )
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.
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.
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.
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.
Thank you!