cnfgen.families.dominatingset module

Formulas that encode dominating set problems

DominatingSet(G, d, alternative=False)

Generates the clauses for a dominating set for G of size <= d

The formula encodes the fact that the graph \(G\) has a dominating set of size \(d\). This means that it is possible to pick at most \(d\) vertices in \(V(G)\) so that all remaining vertices have distance at most one from the selected ones.

Parameters:

G : cnfgen.Graph or networkx.Graph

a simple undirected graph

d : a positive int

the size limit for the dominating set

alternative : bool

use an alternative construction that is provably hard from resolution proofs.

Returns:

CNF

the CNF encoding for dominating of size \(\leq d\) for graph \(G\)

Tiling(G)

Generates the clauses for a tiling of G

The formula encodes the fact that the graph \(G\) has a tiling. This means that it is possible to pick a subset of vertices \(D\) so that all vertices have distance at most one from exactly one verteix in \(D\).

Parameters:

G : cnfgen.Graph or networkx.Graph

a simple undirected graph

Returns:

CNF

the CNF encoding of a tiling of graph \(G\)

unique_neighborhoods(G)

List the neighborhoods of a graph

List sets of vertices, each of them representing a neighborhood in the graph. Each neighborhood is listed just one. Each one is sorted and they are enumerated in a sorted fashion.