On Guarded Extensions of MMSNP
Alexey Barsukov and Florent Madelaine

CiE, Batumi, 25.07.2023

On Guarded Extensions of MMSNP

1/24

Fagin’s theorem (1974)
SNP

ESO

NP

The set of problems expressible with existential second-order logic
is exactly the class NP. MMSNP with ̸=
monadic SNP

monotone SNP

GMPART̸=Matrix Partitions

GMSNP
MMSNP2MPARTGMSNP/one rel.

GMMSNP̸=MMSNPCSPOn Guarded Extensions of MMSNP

2/24

Ladner’s theorem (1975)
SNP

ESO

NP

NO dichotomy
monadic SNP

MMSNP with ̸=

monotone SNP

GMPART̸=If P̸=NP, then there are problems
in NP GMSNP
that are neither in P nor
NP-complete.
GMSNP/one rel.
MMSNP

Matrix Partitions

MPART

2GMMSNP̸=MMSNPCSPOn Guarded Extensions of MMSNP

3/24

Monotone Monadic SNP without Inequality
Definition ([Feder, Vardi, 1998])
The MMSNP logic consists of ESO sentences of the form
∃X1 , . . . , Xs ∀x1 , . . . , xnm^

¬ αi ∧ βi ∧ εi , wherei=1

every αi is a conjunction of input atomic formulas,
every βi is a conjunction of existential atomic formulas,
every εi is a conjunction of inequalities (xj ̸= xk ),all atomic formulas of αi must be non-negated (monotone),all existential relations X1 , . . . , Xs have arity 1 (monadic),
every εi is empty (without inequality).

On Guarded Extensions of MMSNP

4/24

Example

No Monochromatic Triangle

G

Given a graph G, color its
vertices with 2 colors so that theresult omits the two following
subgraphs.

On Guarded Extensions of MMSNP

5/24

Example

No Monochromatic Triangle

G

Given a graph G, color its
vertices with 2 colors so that theresult omits the two followingsubgraphs.

On Guarded Extensions of MMSNP

6/24

“No Monochromatic Triangle” as a sentence in MMSNP∃R, B ∀x, y, z¬(¬Rx ∧ ¬Bx) ∧ ¬(Rx ∧ Bx) (R and B partition the elements)∧¬(Exy ∧ Eyz ∧ Ezx ∧ Rx ∧ Ry ∧ Rz) (no all-red triangle)∧¬(Exy ∧ Eyz ∧ Ezx ∧ Bx ∧ By ∧ Bz) (no all-blue triangle)

On Guarded Extensions of MMSNP

7/24

Feder and Vardi’s results (1998)
SNP

ESO

NPNO dichotomy
monadic SNP

MMSNP with ̸=GMPART̸=Matrix Partitions

monotone SNP

GMSNP
MMSNP2MPART

GMMSNP̸=MMSNPGMSNP/one rel.

Arrows stand for inclusions modulo P-timeequivalence

CSP

On Guarded Extensions of MMSNP

8/24

Zhuk’s theorem (2017)
SNP

ESO

NP

NO dichotomy
monadic SNP

MMSNP with ̸=

GMPART̸=monotone SNP

GMSNP

Every finite CSP isMatrix Partitions
MPART
either in P or NPcomplete

MMSNP2GMSNP/one rel.

GMMSNP̸=MMSNP

dichotomy

On Guarded Extensions of MMSNP

9/24

CSP

Guarded Monotone SNP without Inequality

Definition ([Bienvenu et al., 2014])
The GMSNP logic consists of ESO sentences of the form
∃X1 , . . . , Xs ∀x1 , . . . , xnm^

¬ αi ∧ βi , wherei=1

every αi is a conjunction of input atomic formulas,every βi is a conjunction of existential atomic formulas,
all atomic formulas of αi must be non-negated (monotone),for every Xj (t) in βi there exists R(u) in αi such that t ⊆ u(i.e., t is guarded by u).

On Guarded Extensions of MMSNP

10/24

Example

No Monochromatic Edge Triangle

GGiven a graph G, color its edges
with 2 colors so that the result omits
the two following subgraphs.

On Guarded Extensions of MMSNP

11/24

Example

No Monochromatic Edge Triangle

GGiven a graph G, color its edges
with 2 colors so that the result omits
the two following subgraphs.

On Guarded Extensions of MMSNP

12/24

“No Monochromatic Edge Triangle” as a GMSNP sentence∃R, B ∀x, y, z¬(Exy ∧ ¬Rxy ∧ ¬Bxy) ∧ ¬(Exy ∧ Rxy ∧ Bxy) (partition of edges)∧¬(Exy ∧ Eyz ∧ Ezx ∧ Rxy ∧ Ryz ∧ Rzx) (no all-red triangle)∧¬(Exy ∧ Eyz ∧ Ezx ∧ Bxy ∧ Byz ∧ Bzx) (no all-blue triangle)

On Guarded Extensions of MMSNP

13/24

Guarded Monotone SNP without Inequality (2014)
SNP

ESO

NPNO dichotomy
monadic SNP

MMSNP with ̸=GMPART̸=monotone SNP

GMSNP
MMSNP2Matrix Partitions
Our
contributionsMPART
arehighlighted with blue

GMSNP/single relation
GMMSNP̸=MMSNP

dichotomy

On Guarded Extensions of MMSNP

14/24

CSP

Monotone Monadic SNP with Guarded Inequality
Definition (B., Madelaine)
The GMMSNP̸= logic consists of ESO sentences of the form
∃X1 , . . . , Xs ∀x1 , . . . , xnm^

¬ αi ∧ βi ∧ εi , wherei=1every αi is a conjunction of input atomic formulas,
every βi is a conjunction of existential atomic formulas,
every εi is a conjunction of inequalities (xj ̸= xk ),all atomic formulas of αi must be non-negated (monotone),all existential relations X1 , . . . , Xs have arity 1 (monadic),
for every xj ̸= xk in εi there exists R(u) in αi such that
xj , xk ∈ u (guarded inequality).
On Guarded Extensions of MMSNP

15/24

Monotone Monadic SNP with Guarded Inequality
SNPESONPNO dichotomy
monadic SNP

MMSNP with ̸=GMPART̸=Matrix Partitions

monotone SNP

GMSNP
MMSNP2MPARTGMSNP/single relation
GMMSNP̸=MMSNP

dichotomy

On Guarded Extensions of MMSNP

16/24

CSP

Matrix Partition

M=0∗

∗

1Definition (Feder, Hell)
Let M be a square matrix of size m with elements from {0, 1, ∗}.
Given an input digraph, split its vertices into disjoint classes
P1 , . . . , Pm such that, for i, j ∈ [m] and any distinct x ∈ Pi , y ∈ Pj :if M(i, j) = 0, then there is no edge between x and y;if M(i, j) = 1, then there is an edge between x and y;if M(i, j) = ∗, then there is no restriction.
On Guarded Extensions of MMSNP

17/24

Matrix Partition

M=0∗

∗

1Definition (Feder, Hell)
Let M be a square matrix of size m with elements from {0, 1, ∗}.
Given an input digraph, split its vertices into disjoint classes
P1 , . . . , Pm such that, for i, j ∈ [m] and any distinct x ∈ Pi , y ∈ Pj :if M(i, j) = 0, then there is no edge between x and y;if M(i, j) = 1, then there is an edge between x and y;if M(i, j) = ∗, then there is no restriction.
On Guarded Extensions of MMSNP

18/24

Towards a Logic for Matrix Partition
Definition (B., Madelaine)
The MPART logic consists of ESO sentences of the form
∃X1 , . . . , Xs ∀x1 , . . . , xnm^

¬ αi ∧ βi , wherei=1

every αi is a conjunction of input atomic formulas,
every βi is a conjunction of existential atomic formulas,
all existential relations X1 , . . . , Xs have arity 1 (monadic),
atomic formulas in αi are either all non-negated or all negated(same polarity).

On Guarded Extensions of MMSNP

19/24

MPART with Guarded Inequality
Definition (B., Madelaine)
The GMPART̸= logic consists of ESO sentences of the form
∃X1 , . . . , Xs ∀x1 , . . . , xnm^

¬ αi ∧ βi ∧ εi , wherei=1αi , βi , εi are the same as before,
all existential relations X1 , . . . , Xs have arity 1 (monadic),
atomic formulas in αi are either all non-negated or all negated(same polarity),
for every xj ̸= xk in εi there exists R(u) in αi such that
xj , xk ∈ u (guarded inequality).

On Guarded Extensions of MMSNP

20/24

Split graph recognition as a GMPART̸= sentence

M=0∗

∗

1

∃C, I ∀x, y¬(Cx ∧ ¬Ix) ∧ ¬(Cx ∧ Ix) (partition of vertices in 2 classes)∧¬(¬Exy ∧ Cx ∧ Cy ∧ x ̸= y) (C induces a clique)∧¬(Exy ∧ Ix ∧ Iy ∧ x ̸= y) (I induces an independent set)

On Guarded Extensions of MMSNP

21/24

Matrix Partition and MPART and GMPART̸=SNPESONPNO dichotomy
monadic SNP

MMSNP with ̸=GMPART̸=monotone SNP

GMSNP
MMSNP2Matrix Partitions

GMSNP/single relation

MPART
GMMSNP̸=MMSNP

dichotomy

On Guarded Extensions of MMSNP

22/24

CSP

GMPART̸= has NO dichotomy
SNP

ESONP

NO dichotomy
monadic SNP

MMSNP with ̸=

GMPART̸=monotone SNP

GMSNP
MMSNP2Matrix Partitions

GMSNP/single relation

MPART
GMMSNP̸=MMSNP

dichotomy

On Guarded Extensions of MMSNP

23/24

CSP

References▶ Richard E. Ladner

On the Structure of Polynomial Time Reducibility
J. ACM, 1975, 10.1145/321864.321877▶ Tomás Feder and Moshe Y. VardiThe Computational Structure of Monotone Monadic SNP and Constraint
Satisfaction: A Study through Datalog and Group Theory
SIAM J. Comput., 1998, 10.1137/S0097539794266766▶ Meghyn Bienvenu and Balder ten Cate and Carsten Lutz and Frank Wolter

Ontology-Based Data Access: A Study through Disjunctive Datalog, CSP,and MMSNPACM Trans. Database Syst., 2014, 10.1145/2661643▶ Pavol Hell

Graph partitions with prescribed patterns
Eur. J. Comb., 2014, 10.1016/j.ejc.2013.06.043▶ Dmitriy Zhuk

A Proof of the CSP Dichotomy Conjecture
J. ACM, 2020, 10.1145/3402029On Guarded Extensions of MMSNP

24/24