cnfgen icon indicating copy to clipboard operation
cnfgen copied to clipboard

--guarded option for dominating set formulas

Open jakobnordstrom opened this issue 7 years ago • 0 comments

For the dominating set formulas it would be nice to have a more descriptive option than --alternative, say, perhaps, --guarded, for the version of the formulas with clauses:

  1. x(v) \vee \bigvee_{u \in N_G(v)} x(u) for each v in [n].
  2. !x(v) \vee \bigvee_{i \in [k]} g(v,i) for each v in [n].
  3. !x(v) \vee !g(v,i) \vee !g(v,j) for each v in [n] and i,j in [k] with i != j.
  4. !x(u) \vee !x(v) \vee !g(u,i) \vee !g(v,i) for each u,v in [n] with u != v and each i in [k].

Where clauses 1 say that each vertex is dominated, clauses 2 and 3 say that g is a total map from { v : x(v) = 1 } into [k], and clauses 4 say that g is injective on { v : x(v) = 1 }.

jakobnordstrom avatar Nov 18 '16 12:11 jakobnordstrom