vertexCovers -- list the minimal vertex covers of a (hyper)graph

Synopsis

Usage:
c = vertexCovers(H)
Inputs:
- H, a hypergraph, the input
Outputs:
- c, a list, of the minimal vertex covers of H. The vertex covers are represented as monomials.

Description

This function returns the minimal vertex covers of a (hyper)graph. A vertex cover is a subset of the vertices such that every edge of the (hyper)graph has non-empty intersection with this set. The minimal vertex covers are given by the minimal generators of the cover ideal of H.

i1 : S = QQ[a..d];

i2 : g = graph {a*b,b*c,c*d,d*a} -- the four cycle

o2 = Graph{edges => {{a, b}, {b, c}, {a, d}, {c, d}}}
           ring => S
           vertices => {a, b, c, d}

o2 : Graph

i3 : vertexCovers g

o3 = {a*c, b*d}

o3 : List

i4 : coverIdeal g

o4 = monomialIdeal (a*c, b*d)

o4 : MonomialIdeal of S

i5 : flatten entries gens coverIdeal g == vertexCovers g

o5 = true

i6 : S = QQ[a..e];

i7 : h = hyperGraph {a*b*c,a*d,c*e,b*d*e}

o7 = HyperGraph{edges => {{a, b, c}, {a, d}, {c, e}, {b, d, e}}}
                ring => S
                vertices => {a, b, c, d, e}

o7 : HyperGraph

i8 : vertexCovers(h)

o8 = {a*b*c, c*d, a*e, b*d*e}

o8 : List

Ways to use `vertexCovers` :

vertexCovers(HyperGraph)

vertexCovers -- list the minimal vertex covers of a (hyper)graph

Synopsis

Description

See also

Ways to use vertexCovers :

Ways to use `vertexCovers` :