cnfformula.families.dominatingset module

Formulas that encode coloring related 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 : 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\)

class DominatingSetCmdHelper

Bases: object

Command line helper for k-dominating set

Methods

build_cnf(args)	Build the k-dominating set formula
setup_command_line(parser)	Setup the command line options for dominating set formula

static build_cnf(args)

Build the k-dominating set formula

Arguments: - args: command line options

description = 'k-Dominating set'

name = 'domset'

static setup_command_line(parser)

Setup the command line options for dominating set formula

Arguments: - parser: parser to load with options.