"""Enumeration for hypothesis (G2) of Theorem C.6 (`thm:is`), proved in Appendix C.9 (`app:is-g2`) of the paper. For every lazy 2-separator configuration H = G[C u {y, z}] of bounded size (Appendix C.9 of the paper), the script computes lower bounds on the branching vectors of three candidate branchings, on y, on z and on x, and checks that at least one of them satisfies 2^-a + 2^-b <= 1 (Section 5.4: the hybrid rule; Lemma 11: the bounds). Each branch is evaluated exactly on H (deletion, folding of C, clean-up of vertices of degree at most 1), and the large components outside H contribute dw_D per lost edge when no vertex outside H is deleted (Lemmas 8' and 11) and min(w2, dw_D) per lost edge in the branches G - N[y], G - N[z], where vertices outside H are deleted. The second branch of the y- and z-branchings also uses the monotone bound (first branch) + o_y w2. In section 1 the potential psi is subtracted from every component (the indicator of the new instance may be 1). Configurations: x of degree Delta; y, z in N(x) or not; the core N[x] \\ {y, z}; the degrees of y and z are enumerated independently of the type, so the configurations are a superset of the class (the worst-case tables are restricted to the configurations whose actual type of x is admissible, and every configuration is tested); up to EXTRA further vertices of C+ (Delta = 4), in C or in other components of G - {y, z}; optionally one further small component {c} with N(c) = {y, z}. Exact rationals for the bounds; the test 2^-a + 2^-b <= 1 uses the decimal module with 40 digits and a margin. Standard library only. Run from the repository root (arguments: EXTRA, default 2; DMAX, default 5; BEXTRA, the further vertices of C+ in part B, default 0): python3 -I experiments/algorithmic-consequences/g2_enumeration.py python3 -I experiments/algorithmic-consequences/g2_enumeration.py 2 6 python3 -I experiments/algorithmic-consequences/g2_enumeration.py 0 5 1 """ from decimal import Decimal, getcontext from fractions import Fraction as Fr from itertools import combinations_with_replacement as cwr, combinations import sys import time getcontext().prec = 40 EXTRA = int(sys.argv[1]) if len(sys.argv) > 1 else 2 # further vertices in C at Delta = 4 DMAX = int(sys.argv[2]) if len(sys.argv) > 2 else 5 # largest maximum degree in part B (6 takes about an hour per weight set) BEXTRA = int(sys.argv[3]) if len(sys.argv) > 3 else 0 # further vertices of C+ in part B (Delta >= 5) SECTIONS = { 1: ((Fr("0.0052182"), Fr("0.176755"), Fr("0.3360004")), Fr("0.0061458")), 2: ((Fr("0.0536473"), Fr("0.176755"), Fr("0.2875713")), Fr(0)), 3: ((Fr("0.0708019"), Fr("0.1796141"), Fr("0.2761349")), Fr(0)), 4: ((Fr("0.089188"), Fr("0.1857428"), Fr("0.2700062")), Fr(0)), 5: ((Fr("0.10766765"), Fr("0.19366265"), Fr("0.26736625")), Fr(0)), } GROUP = {(2, 2, 2, 2): 1, (2, 2, 2, 3): 1, (2, 2, 2, 4): 1, (2, 2, 3, 3): 1, (2, 2, 3, 4): 1, (2, 2, 4, 4): 1, (2, 3, 3, 3): 2, (2, 3, 3, 4): 3, (2, 3, 4, 4): 3, (2, 4, 4, 4): 3, (3, 3, 3, 3): 3, (3, 3, 3, 4): 3, (3, 3, 4, 4): 4, (3, 4, 4, 4): 4, (4, 4, 4, 4): 5} HIGH = { "poly (eq:is-general-weights)": [Fr(0), Fr(0), Fr("0.1136655"), Fr("0.1986263"), Fr("0.2673669"), Fr("0.295498"), Fr("0.3034362")], "exp (eq:is-exp-weights)": [Fr(0), Fr(0), Fr("0.1103289"), Fr("0.1932144"), Fr("0.2500011"), Fr("0.2867833"), Fr("0.296828"), Fr("0.2970601")], } def graphs(residual, attach_ok): """Graphs on vertices 1..m plus attachments to Y and Z realizing the residual degrees (vertex 0 is x).""" m = len(residual) - 1 edges, jy, jz, res = [], [0] * (m + 1), [0] * (m + 1), list(residual) def rec(i): if i > m: yield list(edges), list(jy), list(jz) return opts = [j for j in range(i + 1, m + 1) if res[j] > 0] + (["Y", "Z"] if attach_ok else []) need = res[i] if need > len(opts): return for S in combinations(opts, need): for s in S: if s == "Y": jy[i] = 1 elif s == "Z": jz[i] = 1 else: res[s] -= 1 edges.append((i, s)) res[i] = 0 yield from rec(i + 1) res[i] = need for s in S: if s == "Y": jy[i] = 0 elif s == "Z": jz[i] = 0 else: res[s] += 1 edges.pop() yield from rec(1) def comps(adj, verts): seen, out = set(), [] for s in verts: if s in seen: continue c, st = set(), [s] while st: u = st.pop() if u in c: continue c.add(u) st.extend(v for v in adj[u] if v in verts and v not in c) seen |= c out.append(c) return out def branch_bound(adj, ext, deleted, w, D, psi, rest_deleted=False): """Lower bound on the decrease of the measure for the branch that deletes `deleted` (a set of H-vertices); ext = external edge counts of Y and Z. Clean-up on H, large components by Lemma 8 / min(w2, dw_D).""" dwD = w[D] - w[D - 1] alive = set(adj) - set(deleted) full = {v: len(adj[v]) + ext.get(v, 0) for v in adj} deg = {v: len(adj[v] & alive) + ext.get(v, 0) for v in alive} stack = [v for v in alive if deg[v] <= 1] while stack: v = stack.pop() if v not in alive: continue alive.discard(v) for u in adj[v]: if u in alive: deg[u] -= 1 if deg[u] <= 1: stack.append(u) dec = sum(w[full[v]] for v in adj if v not in alive) + sum(w[full[v]] - w[deg[v]] for v in alive) lost = sum(ext[v] for v in ext if v not in alive) dec += lost * (min(w[2], dwD) if rest_deleted else dwD) if psi: dec -= psi return dec def valid(a, b): """2^-a + 2^-b <= 1, floats with a margin, decided by 40-digit decimals in the doubtful band.""" s = 2.0 ** -float(a) + 2.0 ** -float(b) if s < 1 - 1e-9: return True, s if s > 1 + 1e-9: return False, s d = Decimal(2) ** (Decimal(-a.numerator) / Decimal(a.denominator)) + Decimal(2) ** (Decimal(-b.numerator) / Decimal(b.denominator)) return d <= Decimal(1) - Decimal("1e-30"), float(d) def candidates(adj, ext, m_core, w, D, psi): """Vectors (lower bounds) of the three candidate branchings; C = all H-vertices other than Y, Z.""" C = set(adj) - {"Y", "Z"} out = {} for name, v in (("y", "Y"), ("z", "Z")): a = branch_bound(adj, ext, {v} | C, w, D, psi) b = max(a + ext[v] * w[2], branch_bound(adj, ext, ({v} | adj[v] | C), w, D, psi, rest_deleted=True)) out[name] = (a, b) out["x"] = (branch_bound(adj, ext, {0}, w, D, psi), branch_bound(adj, ext, {0} | adj[0], w, D, psi)) return out def enumerate_delta(Delta, w, D, admissible, psi, extra_max, label, pendant_ok=True): t0 = time.time() count, count_adm, fails, worst = 0, 0, [], {} types = [t for t in cwr(range(2, Delta + 1), Delta) if admissible(t)] for T in types: pos = [(None, None)] + [(i, None) for i in range(Delta) if T[i] >= 3] + [(None, i) for i in range(Delta) if T[i] >= 3] pos += [(i, j) for i in range(Delta) for j in range(Delta) if i != j and T[i] >= 3 and T[j] >= 3] seen_pos = set() for (iy, iz) in pos: key = (T[iy] if iy is not None else 0, T[iz] if iz is not None else 0) if key in seen_pos: continue seen_pos.add(key) core = [T[i] for i in range(Delta) if i not in (iy, iz)] for ne in range(0, extra_max + 1): for dE in cwr(range(2, Delta + 1), ne): dC = [Delta] + core + list(dE) m = len(dC) - 1 residual = [0] + [d - 1 for d in core] + list(dE) for edges, jy, jz in graphs(residual, True): adj = {i: set() for i in range(m + 1)} adj.update({"Y": set(), "Z": set()}) for i in range(1, len(core) + 1): adj[0].add(i); adj[i].add(0) if iy is not None: adj[0].add("Y"); adj["Y"].add(0) if iz is not None: adj[0].add("Z"); adj["Z"].add(0) for a, b in edges: adj[a].add(b); adj[b].add(a) for i in range(1, m + 1): if jy[i]: adj[i].add("Y"); adj["Y"].add(i) if jz[i]: adj[i].add("Z"); adj["Z"].add(i) Cset = set(range(m + 1)) if any(not (adj["Y"] & c) or not (adj["Z"] & c) for c in comps(adj, Cset)): continue # every component of C+ has a neighbor of y and one of z (Section 5.1) if any(not (comp & {"Y", "Z"}) for c in range(m + 1) for comp in comps(adj, (Cset | {"Y", "Z"}) - {c})): continue for pendant in ((0, 1) if pendant_ok else (0,)): adj2 = {k: set(v) for k, v in adj.items()} if pendant: adj2["p"] = {"Y", "Z"}; adj2["Y"].add("p"); adj2["Z"].add("p") for yz in (0, 1): if yz: adj2["Y"].add("Z"); adj2["Z"].add("Y") ey, ez = len(adj2["Y"]), len(adj2["Z"]) for oy in range(max(1, 3 - ey), Delta - ey + 1): # d(y) = ey + oy >= 3 for oz in range(max(1, 3 - ez), Delta - ez + 1): count += 1 tact = list(T) # the actual type of x if iy is not None: tact[iy] = ey + oy if iz is not None: tact[iz] = ez + oz tact = tuple(sorted(tact)) adm = admissible(tact) # else outside the class (superset) count_adm += adm vecs = candidates(adj2, {"Y": oy, "Z": oz}, len(core), w, D, psi) oks = {nm: valid(*ab) for nm, ab in vecs.items()} best = min(s for _, s in oks.values()) desc = (tact, (ey + oy, ez + oz), tuple(dC), sorted(edges), tuple(jy[1:]), tuple(jz[1:]), pendant, yz, oy, oz) if not any(ok for ok, _ in oks.values()): fails.append((best, desc, {k: (float(a), float(b)) for k, (a, b) in vecs.items()})) for nm in vecs: if adm and (nm not in worst or oks[nm][1] > worst[nm][0]): worst[nm] = (oks[nm][1], desc) if yz: adj2["Y"].discard("Z"); adj2["Z"].discard("Y") print(" %s: %d configurations (%d with the type of x admissible), %.1f s; configurations with no valid candidate: %d" % (label, count, count_adm, time.time() - t0, len(fails)), flush=True) for nm in ("y", "z", "x"): print(" worst sum for branching on %s over admissible configurations: %.5f at %s" % (nm, worst[nm][0], worst[nm][1])) for best, desc, vecs in sorted(fails)[:6]: print(" FAIL best sum %.5f: %s; vectors %s" % (best, desc, vecs)) return fails # ------------------------------------------------------------------ C. counterexample to (G2) as worded (section 2) def counterexample(m, j): """The graph G(m): a cycle of m blocks (a_i, a'_i of degree 4 and c_i of degree 2 on the cycle, b_i1, b_i2, b_i3 of degree 3 attached to a_i, a'_i, b_i1 matched with b_(i+1)1 for even i), where the degree-2 vertex c_j (j even) is replaced by the lazy configuration x, u1, u2, y, z, r, s1, s2, s3 and the matching edge of block j by the edges s2 b_j1, s3 b_(j+1)1. Every vertex of degree 4 has neighbor degrees (2, 3, 3, 4).""" adj = {} def add(a, b): adj.setdefault(a, set()).add(b) adj.setdefault(b, set()).add(a) for i in range(m): a, ap, b1, b2, b3 = ("a", i), ("a'", i), ("b1", i), ("b2", i), ("b3", i) for e in ((a, ap), (a, b1), (a, b2), (ap, b2), (ap, b3), (b1, b3), (b2, b3)): add(*e) if i != j: add(ap, ("c", i)) add(("c", i), ("a", (i + 1) % m)) if i % 2 == 0 and i != j: add(b1, ("b1", i + 1)) for e in ((("a'", j), "r"), ("r", "y"), ("y", "x"), ("y", "u2"), ("x", "u1"), ("x", "u2"), ("u1", "u2"), ("x", "z"), ("z", "s1"), ("s1", ("a", (j + 1) % m)), ("z", "s2"), ("z", "s3"), ("s2", "s3"), ("s2", ("b1", j)), ("s3", ("b1", j + 1))): add(*e) return adj def core2(adj, deleted): alive = {u for u in adj if u not in deleted} deg = {u: len(adj[u] & alive) for u in alive} stack = [u for u in alive if deg[u] <= 1] while stack: u = stack.pop() if u not in alive: continue alive.discard(u) for v in adj[u]: if v in alive: deg[v] -= 1 if deg[v] <= 1: stack.append(v) return alive def small_cut_part(adj, alive, Km): """Whether G[alive] has a cut vertex with a component of at most Km vertices (the multiplier reduction).""" for c in alive: cc = comps(adj, alive - {c}) if len(cc) > 1 and min(len(p) for p in cc) <= Km: return True return False def mu_sections(adj, alive): """(mu^(k)(G[alive]))_k with the potential psi in section 1; the indicator is 1 iff all degrees are 2 or 4 and no two vertices of degree 4 are adjacent.""" deg = {u: len(adj[u] & alive) for u in alive} ind = all(d in (2, 4) for d in deg.values()) and not any(deg[u] == 4 and deg[v] == 4 for u in alive for v in adj[u] if v in alive) out = {} for k, ((w2, w3, w4), psi) in SECTIONS.items(): w = [Fr(0), Fr(0), w2, w3, w4] out[k] = sum(w[d] for d in deg.values()) + (psi if ind and k == 1 else 0) return out def dec_sum(a, b): return Decimal(2) ** (Decimal(-a.numerator) / Decimal(a.denominator)) + Decimal(2) ** (Decimal(-b.numerator) / Decimal(b.denominator)) def part_c(K=65, m=80, j=0): fails = [] adj = counterexample(m, j) V = set(adj) n = len(V) degs = {u: len(adj[u]) for u in V} deg4_types = {tuple(sorted(degs[v] for v in adj[u])) for u in V if degs[u] == 4} cut = [c for c in V if len(comps(adj, V - {c})) > 1] sep = comps(adj, V - {"y", "z"}) small = [c for c in sep if len(c) <= K] pre = {"n > 7K + 2": n > 7 * K + 2, "min degree 2": min(degs.values()) == 2, "max degree 4": max(degs.values()) == 4, "connected": len(comps(adj, V)) == 1, "no cut vertex": not cut, "every degree-4 vertex has type (2,3,3,4)": deg4_types == {(2, 3, 3, 4)}, "{y,z} lazy for x": degs["y"] >= 3 and degs["z"] >= 3 and len(sep) >= 2 and small == [{"x", "u1", "u2"}]} print("C. Counterexample to (G2) as worded: G(%d), n = %d, K = %d" % (m, n, K)) print(" preconditions: %s" % pre) if not all(pre.values()): fails.append("C preconditions") muG = mu_sections(adj, V) kG = min(muG, key=lambda k: (muG[k], k)) mu4G = muG[kG] print(" mu^(k)(G) = %s; minimizing section %d; average degree %.5f" % ({k: "%.4f" % float(v) for k, v in muG.items()}, kG, sum(degs.values()) / n)) C = {"x", "u1", "u2"} branchings = {"y (the lazy rule)": ({"y"} | C, {"y"} | adj["y"] | C), "z": ({"z"} | C, {"z"} | adj["z"] | C), "x": ({"x"}, {"x"} | adj["x"])} sums = {} for name, (X1, X2) in branchings.items(): vec = [] for X in (X1, X2): alive = core2(adj, X) mu = mu_sections(adj, alive) k = min(mu, key=lambda kk: (mu[kk], kk)) vec.append((mu4G - mu[k], k, len(V - alive), small_cut_part(adj, alive, 6 * K + 1))) s = dec_sum(vec[0][0], vec[1][0]) sums[name] = s print(" branching on %s: decreases %.7f, %.7f (minimizing sections %d, %d; %d and %d vertices removed;" " multiplier reduction applicable afterwards: %s, %s); 2^-a + 2^-b = %.7f" % (name, float(vec[0][0]), float(vec[1][0]), vec[0][1], vec[1][1], vec[0][2], vec[1][2], vec[0][3], vec[1][3], s)) # all lazy pairs for x under the reading of Section 1.1, both orientations, exact decreases after the clean-up nx = adj["x"] | {"x"} cand = sorted((u for u in V if degs[u] >= 3), key=str) pairs, viol, worst_other, big = 0, [], None, 0 for p, q in combinations(cand, 2): cc = comps(adj, V - {p, q}) if len(cc) < 2: continue rest = nx - {p, q} small = [c for c in cc if len(c) <= K] if not any(rest <= c for c in small): continue pairs += 1 Cp = set().union(*small) big = max(big, len(Cp - nx)) for a, b in ((p, q), (q, p)): vec = [] for X in ({a} | Cp, {a} | adj[a] | Cp): mu = mu_sections(adj, core2(adj, X)) vec.append(mu4G - min(mu.values())) s = dec_sum(vec[0], vec[1]) if s > 1: viol.append((a, b, float(s))) elif worst_other is None or s > worst_other[0]: worst_other = (s, a, b) print(" lazy pairs for x under the reading of Section 1.1: %d (%d oriented branchings); violating the condition: %s;" " largest |C+ \\ N[x]| over these pairs: %d; largest sum among the other oriented branchings: %.3e (branch on %s, fold at %s)" % (pairs, 2 * pairs, viol, big, worst_other[0], worst_other[1], worst_other[2])) if viol != [("y", "z", float(sums["y (the lazy rule)"]))]: fails.append("C: lazy pairs") if not sums["y (the lazy rule)"] > 1: fails.append("C: the lazy branching satisfies the condition") if not (sums["z"] <= 1 and sums["x"] <= 1): fails.append("C: no alternative branching") return fails if __name__ == "__main__": total = 0 print("A. Maximum degree 4, the five sections (EXTRA = %d)" % EXTRA, flush=True) for k, ((w2, w3, w4), psi) in SECTIONS.items(): total += len(enumerate_delta(4, [Fr(0), Fr(0), w2, w3, w4], 4, lambda t, k=k: GROUP[t] >= k, psi, EXTRA, "section %d" % k)) print("B. Maximum degree 5 to %d (BEXTRA = %d further vertices of C+, plus an optional p)" % (DMAX, BEXTRA), flush=True) for name, w in HIGH.items(): for Delta in range(5, min(DMAX, len(w) - 1) + 1): total += len(enumerate_delta(Delta, w, len(w) - 1, lambda t, Delta=Delta: any(d < Delta for d in t), Fr(0), BEXTRA, "%s, Delta = %d" % (name, Delta))) total += len(part_c()) print("TOTAL CONFIGURATIONS WITHOUT A VALID CANDIDATE OR FAILED CHECKS: %d" % total) sys.exit(1 if total else 0)