e2f374c3418c50bc30d67d5f7454a5b4-AuthorFeedback.pdf

Certifying anyof these approaches is highly relevant: e.g. The problem: Given a boolean 3-CNF formula s.t.22 the clauses contain only un-negated atoms, does there exist atruth assignment s.t.in23 eachclause,exactlyoneliteralistrue. The reason is that adding an additional edge from aliteral already inO to some clause leads to asmaller35 ht increase than adding an edge from aliteral not yet inO tosome clause. Given this, the right-to-left direction of36 the claim above is trivial: Since eachfj = 1, every clause has exactly one literal set to true. To show how the runtime scales with number of nodes we randomly generate SBM graphs of46 increasing size.