cnfgen icon indicating copy to clipboard operation
cnfgen copied to clipboard

Make documentation for formulas generated from graphs more specific

Open jakobnordstrom opened this issue 7 years ago • 0 comments

A suggestion regarding documentation of formulas generated from graphs.

(1) Say that the formulas can be generated from graphs, and that general info about graph formats and families can be found at blah.

(2) Then, importantly, briefly specify the only graph families that are relevant for this family. Quick examples:

(a) For PHP we want only bipartite graphs, and for UNSAT instances we want graphs with more left-hand vertices than right-hand vertices (or at least wihout complete matchings). If there is a complete matching, the formula is SAT.

(b) For subset cardinality formulas we want bipartite graphs that are regular on both sides and have bounded, even degree. Add an extra edge to get an UNSAT instance.

(c) For Tseitin, only undirected graphs are relevant.

(d) For pebbling, only DAGs are relevant. (Do we allow multiple sinks, but the way? I guess there is no real reason not to.)

Et cetera...

jakobnordstrom avatar Aug 25 '16 13:08 jakobnordstrom