Counting minimal transversals in β-acyclic Hypergraph

Counting minimal transversals in β-acyclic Hypergraph

Benjamin Bergougnoux, Florent Capelli^†, Mamadou M. Kanté^?

?LIMOS, CNRS, Université Clermont Auvergne

†Université Lille 3, CRIStAL, CNRS, INRIA

Algorithm Seminar, Bergen, November 22, 2019

Hypergraphs

1 2 3

4

5 6 7

Definitions

Transversal

A set of vertices intersecting allhyperedges.

I Transversals of graph: Vertex Cover.

I Minimal w.r.t. inclusion.

I Everyvertex has aprivate hyperedge.

1 2 3

4

5 6 7

Definitions

Transversal

A set of vertices intersecting allhyperedges.

I Transversals of graph: Vertex Cover.

I Minimal w.r.t. inclusion.

I Everyvertex has aprivate hyperedge.

1 2 3

4

5 6 7

2

Motivations

I Graphs: vertex covers, dominating sets (transversals ofclosed neighborhoods),...

I AI: models of monotoneCNF-formula.

Counting andenumerating them have a lot ofapplications

I Graphs Theory, A.I. (robustness), Datamining, Model-checking,...

Counting

Goal

Find thenumberof solutions to some problem.

I An analogous hierarchy toP ⊆N P. I Polynomial

I #P

I #P-hard / complete

I Counting can be much harderthan finding:

I Minimal Transversal, Perfect Matching, 2-SAT,...

I k-path,k-cycle!

Minimality matters

Theorem [Okamoto, Uno, Uehara 2005]

In chordal graphs:

I Countingtransversals is doable inpolynomial time.

I Countingminimal transversals is #P-complete.

I Chordal graph: no induced cycle of size≤4.

β-acyclic

Definition

A hypergraph is β-acyclicif it does not haveβ-cycles.

I Theincidence graph (vertices/hyperedges) isBipartite Chordal.

β-acyclic

Definition bis

A hypergraph is β-acyclicif

I Strong Elimination orderingonV(H) : β-leaf

e1 e2 e3

e₁⊆ e₂⊆ e₃ ⊆. . .⊆ e_`

e`

I Not related to thex-width of the incidence graph.

Results on β-acyclic hypergraph

Theorem [Brault-Baron, Capelli, Mengel 2017]

We can count the transversalsof a β-acyclichypergraph in polynomial time.

Theorem [B., Capelli, Kanté 2017]

We can count the minimaltransversals of a β-acyclichypergraph in polynomial time.

I The ingredients: recursive decompositionand“blocked transversals”.

Basic facts

x

H

Fact

The nb. of minimal transversals ofH not containingx is the nb. of minimal transversals of H −x.

Basic facts

H − x

Fact

The nb. of minimal transversals ofH not containingx is the nb. of minimal transversals of H −x.

Basic facts

x

H

Lemma

Basic facts

H \ H(x)

Lemma

Basic facts

H \ H(x)

Lemma

Basic facts

x

H

Lemma

Basic facts

x

H

Lemma

T ∪x is a min. transversalof Hiff:

I T is a min. transversal of H \ H(x) I T is not a transversal of H

Formula

Corollary

The following values are equal:

I The nb. of minimal transversals ofH containingx.

I The nb. of minimal transversals ofH − H(x) that are not transversals of H.

I The nb. of minimal transversals ofH − H(x) minus the nb. of minimal transversals ofH − H(x) that aretransversals of H.

Blocked-Transversals

S: a subset of vertices.

Definition

S-blockedtransversal ofH (denoted by S-btr(H)):

I Minimal transversals of Hand of H \ H(S)

I ∅-btr(H) = min. transversals ofH.

I Private hyperedges cannot contain a vertex ofS.

x

H

Blocked Transversal

Lemma (reformulation)

The nb. of minimal transversals ofH = nb. of min. transversals ofH excluding x

+ nb. of min. transversals ofH \ H(x)

− nb. of min. transversals ofH \ H(x)and of H.

Lemma (generalization)

The nb. of S-blocked transversals ofH =

#S-btr(H −x) + #S-btr(H \ H(x))

− #S∪{x}-btr(H \ (H(x)∩ H(S))).

Blocked Transversal

Lemma (reformulation)

The nb. of minimal transversals ofH =

#∅-btr(H −x)

+ nb. of min. transversals ofH \ H(x)

− nb. of min. transversals ofH \ H(x)and of H.

Lemma (generalization)

The nb. of S-blocked transversals ofH =

#S-btr(H −x) + #S-btr(H \ H(x))

− #S∪{x}-btr(H \ (H(x)∩ H(S))).

Blocked Transversal

Lemma (reformulation)

The nb. of minimal transversals ofH =

#∅-btr(H −x) + #∅-btr(H \ H(x))

− nb. of min. transversals ofH \ H(x)and of H.

Lemma (generalization)

The nb. of S-blocked transversals ofH =

#S-btr(H −x) + #S-btr(H \ H(x))

− #S∪{x}-btr(H \ (H(x)∩ H(S))).

Blocked Transversal

Lemma (reformulation)

The nb. of minimal transversals ofH =

#∅-btr(H −x) + #∅-btr(H \ H(x))

− #x-btr(H).

Lemma (generalization)

The nb. of S-blocked transversals ofH =

#S-btr(H −x) + #S-btr(H \ H(x))

− #S∪{x}-btr(H \ (H(x)∩ H(S))).

Blocked Transversal

Lemma (reformulation)

The nb. of minimal transversals ofH =

#∅-btr(H −x) + #∅-btr(H \ H(x))

− #x-btr(H).

Lemma (generalization)

The nb. of S-blocked transversals ofH =

#S-btr(H −x) + #S-btr(H \ H(x))

− #S∪{x}-btr(H \ (H(x)∩ H(S))).

Blocked Transversal

Using the formula leads to a combinatorial explosionin general!

Decomposition of β-acyclic hypergraph

I Strong elimination ordering onV(H) : x₁, . . . , x_n. I Induced orderon the hyperedges : e₁, . . . , e_m. Definition

H(x, e)⇒ thehyperedges6econnected toethrough vertices6x .

2

1 3

4

5 6 7

2

1 3

H H(3,{2,3})

I H(x_n, e_m)=H.

I Goal is to compute#∅-btr(H(x_n, e_m)) with the help of:

I The formula: #S-btr(H) =

#S-btr(H −x)+#S-btr(H \ H(x))−#S∪ {x}-btr(H \(H(x)∩ H(S)))

Avoid the explosion

Combinatorial explosion !

To compute #{w}-btr(H) we need to compute:

I #{x, w}-btr(H \ (H(x)∩ H(w))),...

But in β-acyclic hypergraphs

We can compute #{x, w}-btr(H \ (H(x)∩ H(w))) from I #x-btr(H⁰).

I #w-btr(H⁰).

We can express each H⁰ as a H(y, f)where y < x.

Dynamic programming

#∅-btr(H(5, e₅))

3 5

4

2

1

Dynamic programming

#∅-btr(H(5, e₅))

3 5

4 #∅-btr(H(4, e₅)) #∅-btr(H(4, e₂)) #5-btr(H(4, e₅))

2

1

#∅-btr(H(2, e1))

Each termiscomputable fromsmaller terms.

Dynamic programming

#∅-btr(H(5, e₅))

3 5

4 #∅-btr(H(4, e₅)) #∅-btr(H(4, e₂)) #5-btr(H(4, e₅))

2

1

#∅-btr(H(3, e2)) #4-btr(H(3, e2))

#∅-btr(H(2, e₅))

#4-btr(H(2, e5))

Each termiscomputable fromsmaller terms.

Dynamic programming

#∅-btr(H(5, e₅))

3 5

4 #∅-btr(H(4, e₅)) #∅-btr(H(4, e₂)) #5-btr(H(4, e₅))

2

1

#∅-btr(H(3, e2)) #4-btr(H(3, e2))

Each termiscomputable fromsmaller terms.

Dynamic programming

#∅-btr(H(5, e₅))

3 5

4 #∅-btr(H(4, e₅)) #∅-btr(H(4, e₂)) #5-btr(H(4, e₅))

2

1

#∅-btr(H(3, e2))

#5-btr(H(2, e₅))

#4-btr(H(3, e2))

#∅-btr(H(2, e1))

Each termiscomputable fromsmaller terms.

Dynamic programming

#∅-btr(H(5, e₅))

3 5

4

2

1

We end up with a DAG.

Dynamic programming

#∅-btr(H(5, e₅))

3 5

4

2

1

Sink are easilycomputable.

Dynamic programming

#∅-btr(H(5, e₅))

3 5

4

2

1

As a salmon, we go back to the source.

Dynamic programming

#∅-btr(H(5, e₅))

3 5

4

2

1

As a salmon, we go back to the source.

Dynamic programming

#∅-btr(H(5, e₅))

3 5

4

2

1

Number of termsis polynomial ⇒ Algorithmpolynomial.

Result and Consequences

Theorem [B. , Capelli, Kanté 2017]

We can count the number of minimal transversalsof aβ-acyclic hypergraph in polynomialtime.

I Min. dominating sets⇒ min. transversals ofclosed neighborhoods.

I Strongly chordalgraphs⇔ {N[x]|x∈V(G)}is β-acyclic.

Corollary

We can count the number of min. dominating setsofStrongly Chordal graph in polynomialtime.

Minimal dominating sets

I Stongly Chordal graphs⇔ Chordal graphs + k-sun free, for k>3.

3-sun 4-sun 5-sun

[Kanté, Uno 2017]

Counting min. dominating setsofChordal graphs is #P-complete.

Conjecture [Kanté, Uno 2017]

Counting min. dominating setsof a subclass ofChordal graphs is I doable inpolynomial time if this class isk-sun free, fork>4, I #P-complet otherwise.

Minimal dominating sets

I Stongly Chordal graphs⇔ Chordal graphs + k-sun free, for k>3.

3-sun 4-sun 5-sun

[Kanté, Uno 2017]

Counting min. dominating setsofChordal graphs is #P-complete.

Conjecture [Kanté, Uno 2017]

Counting min. dominating setsof a subclass ofChordal graphs is I doable inpolynomial time if this class isk-sun free, fork>4, I

Possible generalizations

Theorem [Brault-Baron, Capelli, Mengel 2015]

We can count the Modelsof aβ-acyclicCNF-formula in polynomialtime.

Corollary of our result

We can count the minimal modelsof a monotoneβ-acyclicCNF-formula in polynomialtime.

I Can we do it for non-monotone formulas?

Beyond β-acyclicity

β-hypertree width

β-acyclic mim(incidence graph)

tw(incidence graph) cw(incidence graph) Hypertree width

Polytime or XP

Para-NP-hard

?

point-width

Thank you!