(1) base instances B(q,d)
  q=2 d=1 |Q|=1 cover_number=1 point-degrees=[1] (expected 1 of 1; fraction 1.0000 >= 1-1/q=0.5000) OK
  q=2 d=2 |Q|=3 cover_number=2 point-degrees=[2] (expected 2 of 3; fraction 0.6667 >= 1-1/q=0.5000) OK
  q=2 d=3 |Q|=7 cover_number=3 point-degrees=[4] (expected 4 of 7; fraction 0.5714 >= 1-1/q=0.5000) OK
  q=2 d=4 |Q|=15 cover_number=4 point-degrees=[8] (expected 8 of 15; fraction 0.5333 >= 1-1/q=0.5000) OK
  q=3 d=1 |Q|=2 cover_number=1 point-degrees=[2] (expected 2 of 2; fraction 1.0000 >= 1-1/q=0.6667) OK
  q=3 d=2 |Q|=8 cover_number=2 point-degrees=[6] (expected 6 of 8; fraction 0.7500 >= 1-1/q=0.6667) OK
  q=3 d=3 |Q|=26 cover_number=3 point-degrees=[18] (expected 18 of 26; fraction 0.6923 >= 1-1/q=0.6667) OK
  q=5 d=1 |Q|=4 cover_number=1 point-degrees=[4] (expected 4 of 4; fraction 1.0000 >= 1-1/q=0.8000) OK
  q=5 d=2 |Q|=24 cover_number=2 point-degrees=[20] (expected 20 of 24; fraction 0.8333 >= 1-1/q=0.8000) OK
(2) product lemma: cover(U x Q) == min(cover(U,F), d)
  trial  0 |U|=4 |F|=2 tau(U,F)=2  -> product covers (q,d)=(2,2),(2,3),(3,2): [2, 2, 2]
  trial  1 |U|=2 |F|=1 tau(U,F)=1  -> product covers (q,d)=(2,2),(2,3),(3,2): [1, 1, 1]
  trial  2 |U|=2 |F|=3 tau(U,F)=1  -> product covers (q,d)=(2,2),(2,3),(3,2): [1, 1, 1]
  trial  3 |U|=3 |F|=1 tau(U,F)=inf  -> product covers (q,d)=(2,2),(2,3),(3,2): [2, 3, 2]
  trial  4 |U|=5 |F|=4 tau(U,F)=inf  -> product covers (q,d)=(2,2),(2,3),(3,2): [2, 3, 2]
  trial  5 |U|=5 |F|=1 tau(U,F)=inf  -> product covers (q,d)=(2,2),(2,3),(3,2): [2, 3, 2]
  trial  6 |U|=2 |F|=2 tau(U,F)=1  -> product covers (q,d)=(2,2),(2,3),(3,2): [1, 1, 1]
  trial  7 |U|=2 |F|=5 tau(U,F)=1  -> product covers (q,d)=(2,2),(2,3),(3,2): [1, 1, 1]
  trial  8 |U|=3 |F|=3 tau(U,F)=2  -> product covers (q,d)=(2,2),(2,3),(3,2): [2, 2, 2]
  trial  9 |U|=2 |F|=5 tau(U,F)=1  -> product covers (q,d)=(2,2),(2,3),(3,2): [1, 1, 1]
  trial 10 |U|=3 |F|=3 tau(U,F)=2  -> product covers (q,d)=(2,2),(2,3),(3,2): [2, 2, 2]
  trial 11 |U|=2 |F|=5 tau(U,F)=1  -> product covers (q,d)=(2,2),(2,3),(3,2): [1, 1, 1]
  40 random trials x 3 (q,d) checked
(3) reduction to eps-dense Steiner Tree: opt_nodes == min(tau, d), density >= eps
  trial  0 |U|=3 |F|=5 tau=1 (q,d)=(2,2) eps=0.25 R=1 |S|=10 |N|=8 density=0.5000 opt_nodes=1 [exhaustive] expected=1 OK
  trial  1 |U|=4 |F|=2 tau=2 (q,d)=(2,3) eps=0.25 R=1 |S|=29 |N|=9 density=0.5556 opt_nodes=2 [exhaustive] expected=2 OK
  trial  2 |U|=4 |F|=4 tau=2 (q,d)=(2,3) eps=0.40 R=2 |S|=29 |N|=18 density=0.5000 opt_nodes=2 [exhaustive] expected=2 OK
  trial  3 |U|=2 |F|=4 tau=1 (q,d)=(3,2) eps=0.50 R=1 |S|=17 |N|=12 density=0.6667 opt_nodes=1 [exhaustive] expected=1 OK
  trial  4 |U|=4 |F|=1 tau=inf (q,d)=(3,2) eps=0.60 R=1 |S|=33 |N|=9 density=0.6667 opt_nodes=2 [exhaustive] expected=2 OK
  trial  5 |U|=3 |F|=4 tau=2 (q,d)=(2,2) eps=0.25 R=1 |S|=10 |N|=7 density=0.4286 opt_nodes=2 [exhaustive] expected=2 OK
  trial  6 |U|=2 |F|=5 tau=1 (q,d)=(2,3) eps=0.25 R=1 |S|=15 |N|=12 density=0.4167 opt_nodes=1 [exhaustive] expected=1 OK
  trial  7 |U|=2 |F|=2 tau=1 (q,d)=(2,3) eps=0.40 R=1 |S|=15 |N|=9 density=0.5556 opt_nodes=1 [exhaustive] expected=1 OK
  trial  8 |U|=3 |F|=3 tau=1 (q,d)=(3,2) eps=0.50 R=1 |S|=25 |N|=11 density=0.6364 opt_nodes=1 [exhaustive] expected=1 OK
  trial  9 |U|=2 |F|=5 tau=1 (q,d)=(3,2) eps=0.60 R=3 |S|=17 |N|=29 density=0.7241 opt_nodes=1 [exhaustive] expected=1 OK
  trial 10 |U|=4 |F|=1 tau=inf (q,d)=(2,2) eps=0.25 R=1 |S|=13 |N|=4 density=0.5000 opt_nodes=2 [exhaustive] expected=2 OK
  trial 11 |U|=4 |F|=3 tau=1 (q,d)=(2,3) eps=0.25 R=1 |S|=29 |N|=10 density=0.6000 opt_nodes=1 [exhaustive] expected=1 OK
  trial 12 |U|=2 |F|=3 tau=1 (q,d)=(2,3) eps=0.40 R=1 |S|=15 |N|=10 density=0.6000 opt_nodes=1 [exhaustive] expected=1 OK
  trial 13 |U|=3 |F|=1 tau=inf (q,d)=(3,2) eps=0.50 R=1 |S|=25 |N|=9 density=0.6667 opt_nodes=2 [exhaustive] expected=2 OK
  trial 14 |U|=4 |F|=1 tau=inf (q,d)=(3,2) eps=0.60 R=1 |S|=33 |N|=9 density=0.6667 opt_nodes=2 [exhaustive] expected=2 OK
  trial 15 |U|=2 |F|=3 tau=2 (q,d)=(2,2) eps=0.25 R=1 |S|=7 |N|=6 density=0.5000 opt_nodes=2 [exhaustive] expected=2 OK
  trial 16 |U|=4 |F|=1 tau=inf (q,d)=(2,3) eps=0.25 R=1 |S|=29 |N|=8 density=0.5000 opt_nodes=3 [exhaustive] expected=3 OK
  trial 17 |U|=2 |F|=1 tau=inf (q,d)=(2,3) eps=0.40 R=1 |S|=15 |N|=8 density=0.5000 opt_nodes=3 [exhaustive] expected=3 OK
  trial 18 |U|=3 |F|=4 tau=2 (q,d)=(3,2) eps=0.50 R=1 |S|=25 |N|=12 density=0.5833 opt_nodes=2 [exhaustive] expected=2 OK
  trial 19 |U|=2 |F|=3 tau=2 (q,d)=(3,2) eps=0.60 R=2 |S|=17 |N|=19 density=0.6842 opt_nodes=2 [exhaustive] expected=2 OK
  trial 20 |U|=3 |F|=1 tau=inf (q,d)=(2,2) eps=0.25 R=1 |S|=10 |N|=4 density=0.5000 opt_nodes=2 [exhaustive] expected=2 OK
  trial 21 |U|=2 |F|=2 tau=1 (q,d)=(2,3) eps=0.25 R=1 |S|=15 |N|=9 density=0.5556 opt_nodes=1 [exhaustive] expected=1 OK
  trial 22 |U|=2 |F|=1 tau=inf (q,d)=(2,3) eps=0.40 R=1 |S|=15 |N|=8 density=0.5000 opt_nodes=3 [exhaustive] expected=3 OK
  trial 23 |U|=3 |F|=4 tau=2 (q,d)=(3,2) eps=0.50 R=1 |S|=25 |N|=12 density=0.5833 opt_nodes=2 [exhaustive] expected=2 OK
(4) 3-SAT -> Set Cover: tau <= k iff satisfiable
  120 random 3-CNFs checked (83 satisfiable, 37 unsatisfiable)
(5) chain 3-SAT -> Set Cover -> 0.25-dense Steiner Tree: opt_nodes <= k iff satisfiable
  trial  0 vars=4 clauses= 4 k=2 satisfiable=True |S|=43 |N|=15 density=0.533 opt_nodes=2 (<=k: True) OK
  trial  1 vars=3 clauses=20 k=2 satisfiable=True |S|=155 |N|=13 density=0.462 opt_nodes=2 (<=k: True) OK
  trial  2 vars=3 clauses= 6 k=2 satisfiable=True |S|=57 |N|=13 density=0.462 opt_nodes=2 (<=k: True) OK
  trial  3 vars=4 clauses=20 k=2 satisfiable=True |S|=155 |N|=15 density=0.533 opt_nodes=2 (<=k: True) OK
  trial  4 vars=4 clauses= 6 k=2 satisfiable=True |S|=57 |N|=15 density=0.533 opt_nodes=2 (<=k: True) OK
  trial  5 vars=3 clauses=19 k=2 satisfiable=True |S|=148 |N|=13 density=0.462 opt_nodes=2 (<=k: True) OK
  trial  6 vars=3 clauses= 5 k=2 satisfiable=True |S|=50 |N|=13 density=0.462 opt_nodes=2 (<=k: True) OK
  trial  7 vars=4 clauses=18 k=2 satisfiable=True |S|=141 |N|=15 density=0.533 opt_nodes=2 (<=k: True) OK
  trial  8 vars=3 clauses= 6 k=2 satisfiable=True |S|=57 |N|=13 density=0.462 opt_nodes=2 (<=k: True) OK
  trial  9 vars=3 clauses=15 k=2 satisfiable=True |S|=120 |N|=13 density=0.462 opt_nodes=2 (<=k: True) OK
  trial 10 vars=3 clauses= 5 k=2 satisfiable=True |S|=50 |N|=13 density=0.462 opt_nodes=2 (<=k: True) OK
  trial 11 vars=4 clauses=19 k=2 satisfiable=True |S|=148 |N|=15 density=0.533 opt_nodes=2 (<=k: True) OK
  trial 12 vars=4 clauses= 5 k=2 satisfiable=True |S|=50 |N|=15 density=0.533 opt_nodes=2 (<=k: True) OK
  trial 13 vars=3 clauses=16 k=2 satisfiable=False |S|=127 |N|=13 density=0.462 opt_nodes=3 (<=k: False) OK
  trial 14 vars=4 clauses= 6 k=2 satisfiable=True |S|=57 |N|=15 density=0.533 opt_nodes=2 (<=k: True) OK
  trial 15 vars=3 clauses=16 k=2 satisfiable=False |S|=127 |N|=13 density=0.462 opt_nodes=3 (<=k: False) OK
TOTAL failures = 0, time 28.4s
