# minimal_triples.sage
# Written by Stephen Hartke and Mike Barrus, August 20, 2013.
# This program determines all of the minimal DSF triples.
import time
def binom2(x):
return x*(x-1)/2
def is_EdgeConditionSatisfied(EdgeVertPairs):
# EdgeVertPairs is a list of 3 pairs [e,n] denoting the number of edges and vertices in each graph.
# We verify the edge condition and the edge condition for the complement.
size=sorted(EdgeVertPairs)
if ( size[1][0]> size[0][0]+2*size[0][1] or
size[2][0]>max(size[0][0]+2*size[0][1],
size[1][0]+2*size[1][1]) ):
return False # these are not the parameters of a valid triple
# We now verify the edge condition for the set of complements.
comp=[]
for pair in size:
e,n=pair[0],pair[1]
comp.append([binom2(n)-e,n])
comp.sort()
if ( comp[1][0]> comp[0][0]+2*comp[0][1] or
comp[2][0]>max(comp[0][0]+2*comp[0][1],
comp[1][0]+2*comp[1][1]) ):
return False # these are not the parameters of a valid triple
return True # the edge conditions are satisfied
def Phase1():
# We generate a list of candidate triples of graphs, where each triple satisfies all 6 classes of graphs, as well as some other necessary conditions, such as the vertex and edge bounds.
candidate_triples=[]
# We are choosing a triple {F1,F2,F3}, where F1 is in B and F2 is in Bc.
# The choice of F3 depends on which graph classes are already covered by F1 and F2.
# We will keep track of which classes F_i satisfies.
K=[False]*4 # disjoint union of complete graphs, at most one nontrivial
Kc=[False]*4 # complements
S=[False]*4 # forest of stars
Sc=[False]*4 # complements
# Note: we are 1-indexing the graphs here; ie, K[1] is whether F1 is in K.
for n1 in [4..18]: # the number of vertices in F1
print "Considering n1=%d" % n1
# We choose F1 to be complete bipartite K_{a1,a2} with 0<=a1<=a2 and have at least 4 vertices.
for a1 in [1..n1//2]: # note that a_1>=1 by Lemma 3.8
a2=n1-a1
e1=a1*a2 # number of edges of F1
F1=graphs.CompleteBipartiteGraph(a1,a2)
string1="K_"+str(a1)+","+str(a2)
# determine the properties of F1
K [1]=(a1==0) # this cannot occur
Kc[1]=(a1<=2)
S [1]=(a1<=1)
Sc[1]=(a1==a2==2)
for n2 in [4..18]: # the number of vertices in F2
# We choose F2 to be the complement of a complete bipartite graph.
# So F2 is a disjoint union of cliques K_b1+K_b2 with 0<=b1<=b2 and has at least 4 vertices.
for b1 in [1..n2//2]: # note that b_1>=1 by Lemma 3.8
b2=n2-b1
e2=binom2(b1)+binom2(b2) # number of edges of F2
F2=graphs.CompleteGraph(b1).disjoint_union(graphs.CompleteGraph(b2))
string2="K_"+str(b1)+"+K_"+str(b2)
# determine the properties of F2
K [2]=(b1<=2)
Kc[2]=(b1==0) # this cannot occur
S [2]=(b1==b2==2)
Sc[2]=(b1<=1)
# If F1 and F2 already satisfy all 6 classes, then F1 and F2 have a specific form, as described in Lemma 3.7.
# By Lemma 3.8 and 3.9, there is no F3 that will complete a DSF set.
if (a1<=1 and b1<=1) or (a1==a2==b1==b2==2):
continue # don't need to consider F3
# If neither S nor Sc is satisfied, then one graph F3 cannot satisfy both classes.
if not (S[1] or S[2] or Sc[1] or Sc[2]):
continue
for n3 in [4..18]: # the number of vertices in F3
# By Theorem 2.2 and Corollary 2.7, there are constraints on the number of vertices in a DSF triple.
order=sorted([n1,n2,n3])
if not (order[0]<=14 and order[1]<=16 and # By Corollary 2.7
order[1]-order[0]<=2 and order[2]-order[1]<=2): # By Theorem 2.2
continue # this is not a valid choice for n3
#####################################################################
# Make the choice of F3
#####################################################################
if not (K[1] or K[2]):
# We choose F3 to be in K: K_c3 + c2 K_2 + c1 K_1, c3 not equal to 1 or 2.
for c3 in [0..n3]:
if c3==1 or c3==2:
continue # c3 cannot be 1 or 2
for c2 in [0..(n3-c3)//2]:
c1=n3-c3-2*c2
e3=binom2(c3) + c2
if e3==0 or e3==binom2(n3): # F3 has no edges or is complete, which is ruled out by Lemma 3.8 (we may apply Lemma 3.8 since we know F2 is complement of bipartite, and F3 is playing the role of F1)
continue
# test the size (number of edges) conditions
if not is_EdgeConditionSatisfied([[e1,n1],[e2,n2],[e3,n3]]):
continue # these are not a valid triple
# determine the properties of F3
K [3]=True
Kc[3]=((c3==c2==0) or (c2==c1==0))
S [3]=(c3==0)
Sc[3]=(c1<=1 and c2==0)
if ( (K[1] or K[2] or K[3]) and (Kc[1] or Kc[2] or Kc[3]) and
(S[1] or S[2] or S[3]) and (Sc[1] or Sc[2] or Sc[3]) ): # all 6 classes satisfied
F3=graphs.CompleteGraph(c3)
for i in range(c2):
F3=F3.disjoint_union(graphs.CompleteGraph(2))
F3=F3.disjoint_union(graphs.CompleteGraph(c1).complement())
string3="K_"+str(c3)+"+"+str(c2)+"K_2+"+str(c1)+"K_1"
candidate_triples.append([[F1,F2,F3],string1+"; "+string2+"; "+string3])
elif not (Kc[1] or Kc[2]):
# We choose F3 to be in Kc: complement of (K_c3 + c2 K_2 + c1 K_1), c3 not equal to 1 or 2
for c3 in [0..n3]:
if c3==1 or c3==2:
continue # c3 cannot be 1 or 2
for c2 in [0..(n3-c3)//2]:
c1=n3-c3-2*c2
# test the size (number of edges) conditions
e3=binom2(c1) + 2*c2^2-c2 + c1*c3 + c1*2*c2 + c3*2*c2
if e3==0 or e3==binom2(n3): # F3 has no edges or is complete, which is ruled out by Lemma 3.8
continue
if not is_EdgeConditionSatisfied([[e1,n1],[e2,n2],[e3,n3]]):
continue # these are not a valid triple
# determine the relevant properties of F3
#K [3]=?? # One of F1 or F2 satisfies K, or else in previous case
Kc[3]=True
S [3]=(c1<=1 and c2==0)
Sc[3]=(c3==0)
if ( (K[1] or K[2] or K[3]) and (Kc[1] or Kc[2] or Kc[3]) and
(S[1] or S[2] or S[3]) and (Sc[1] or Sc[2] or Sc[3]) ): # all 6 classes satisfied
F3=graphs.CompleteGraph(c3)
for i in range(c2):
F3=F3.disjoint_union(graphs.CompleteGraph(2))
F3=F3.disjoint_union(graphs.CompleteGraph(c1).complement())
F3=F3.complement()
string3="K_"+str(c1)+"v("+str(c2)+"K_2)^c v"+str(c3)+"K_1"
candidate_triples.append([[F1,F2,F3],string1+"; "+string2+"; "+string3])
elif not (S[1] or S[2]):
# We choose F3 to be a forest of stars
for s in Partitions(n3): # sizes of stars in F3
# test the size (number of edges) conditions
e3=sum(i-1 for i in s)
if e3==0 or e3==binom2(n3): # F3 has no edges or is complete, which is ruled out by Lemma 3.8
continue
if not is_EdgeConditionSatisfied([[e1,n1],[e2,n2],[e3,n3]]):
continue # these are not a valid triple
# determine the relevant properties of F3
S [3]=True
# One of F1 or F2 must satisfy Sc.
if ( (K[1] or K[2] or K[3]) and (Kc[1] or Kc[2] or Kc[3]) and
(S[1] or S[2] or S[3]) and (Sc[1] or Sc[2] or Sc[3]) ): # all 6 classes satisfied
F3=graphs.EmptyGraph()
string3=""
for i in s:
F3=F3.disjoint_union(graphs.CompleteBipartiteGraph(1,i-1))
string3+="+K_1,"+str(i-1)
candidate_triples.append([[F1,F2,F3],string1+"; "+string2+"; "+string3])
elif not (Sc[1] or Sc[2]):
# We choose F3 to be a complement of a forest of stars
for s in Partitions(n3): # sizes of stars in complement of F3
e3=binom2(n3) - sum(i-1 for i in s)
if e3==0 or e3==binom2(n3): # F3 has no edges or is complete, which is ruled out by Lemma 3.8
continue
if not is_EdgeConditionSatisfied([[e1,n1],[e2,n2],[e3,n3]]):
continue # these are not a valid triple
# determine the properties of F3
# Don't need to worry about K, Kc, or S since already satisfied by F1 and F2.
Sc[3]=True
if ( (K[1] or K[2] or K[3]) and (Kc[1] or Kc[2] or Kc[3]) and
(S[1] or S[2] or S[3]) and (Sc[1] or Sc[2] or Sc[3]) ): # all 6 classes satisfied
F3=graphs.EmptyGraph()
string3=""
for i in s:
F3=F3.disjoint_union(graphs.CompleteBipartiteGraph(1,i-1))
string3+="+K_1,"+str(i-1)
F3=F3.complement()
string3+=" ^c"
candidate_triples.append([[F1,F2,F3],string1+"; "+string2+"; "+string3])
return candidate_triples # the end of Phase I
def contains_induced_subgraph(G,H):
# Tests if G contains a copy of H as an induced subgraph.
# NOTE: We assume that H is already presented as its canonical label.
if H.order()>G.order() or H.size()>G.size():
return False
for V in Subsets(G.vertices(),H.order()):
J=G.subgraph(V) # induced subgraph, since edges not specified
if J.canonical_label()==H: # We don't need to use "J.is_isomorphic(H):" since H is already canonically labeled.
return True
return False
breaking_pairs=[] # global variable to keep track of breaking pairs found for the candidate_triples
import exceptions
class BreakingPairFound(exceptions.Exception):
def __init__(self,H,Hp):
self.H=H
self.Hp=Hp
return
def __str__(self):
# save the graph6 strings of the canonical labels of this pair in a list.
Hstr=self.H.canonical_label().graph6_string()
Hpstr=self.Hp.canonical_label().graph6_string()
if (Hstr,Hpstr) not in breaking_pairs:
breaking_pairs.append((Hstr,Hpstr))
return "breaking pair: H>"+Hstr+"< Hp>"+Hpstr+"<"
# the one DSF pair with each graph having at least 4 vertices
C4=graphs.CycleGraph(4)
K2K2=C4.complement()
dsf_pair=[C4.canonical_label(),K2K2.canonical_label()]
def FindBreakingPair(graph_triple,string):
# Sort the graphs by number of vertices, then by number of edges.
# Also, replace each with its canonical label to speed up subgraph testing.
graph_set=[i[2].canonical_label() for i in sorted([[H.order(),H.size(),H] for H in graph_triple])]
# Test if the graph_set is minimal in the sense that no subgraph is induced in any other.
if (contains_induced_subgraph(graph_set[1],graph_set[0]) or
contains_induced_subgraph(graph_set[2],graph_set[0]) or
contains_induced_subgraph(graph_set[2],graph_set[1]) ):
print "not induced minimal:",string
return
# test if graph_set contains a DSF pair (by construction, does not have a DSF singleton)
# Since we are restricting to graphs with at least 4 vertices, we only need to check [2K2,C4].
for G in dsf_pair:
for F in graph_set:
if F.canonical_label()==G: # we assume G is presented with its canonical label
break
else: # G was not found in the graph_set
break
else: # all G in dsf_pair were found in the graph_set
print "not minimal, contains dsf pair [2K2,C4] in",string
return
y=20; z=21 # new vertices to add
try:
for F in graph_set:
# add one vertex to F
for e in F.edges():
for v in F.vertices():
if v==e[0] or v==e[1]: continue
for u,w in [(e[0],e[1]),(e[1],e[0])]:
if not F.has_edge(u,v):
V=[x for x in F.vertices() if x!=w and x!=v] # okay for y to be adj to u
for N in Subsets(V): # the neighborhood of the new vertex
# so uv is a nonedge, and uw is an edge.
# The 2-switch will be: (uw,vy) -> (uv,wy)
Hp=copy(F)
Hp.add_edge(u,v)
Hp.delete_edge(e)
Hp.add_vertex(y)
Hp.add_edge(w,y)
Hp.add_edges([(x,y) for x in N])
for J in graph_set:
if contains_induced_subgraph(Hp,J):
break
else:
H=copy(F)
H.add_vertex(y)
H.add_edges([(x,y) for x in N])
H.add_edge((v,y))
raise BreakingPairFound(H,Hp)
# add two vertices to F
for (u,v) in Subsets(F.vertices(),2):
Vy=[x for x in F.vertices() if x!=u]
Vz=[x for x in F.vertices() if x!=v]
for Ny in Subsets(Vy):
for Nz in Subsets(Vz):
Hp=copy(F)
Hp.add_vertices([y,z])
Hp.add_edges([(x,y) for x in Ny])
Hp.add_edges([(x,z) for x in Nz])
if F.has_edge(u,v):
Hp.delete_edge(u,v)
Hp.add_edges([(u,y),(v,z)])
else: # u,v are not an edge
Hp.add_edges([(u,v),(y,z)])
for J in graph_set:
if contains_induced_subgraph(Hp,J):
break
else:
H=copy(F)
H.add_vertices([y,z])
H.add_edges([(x,y) for x in Ny])
H.add_edges([(x,z) for x in Nz])
if F.has_edge(u,v):
H.add_edge((y,z))
else: # u,v are not an edge
H.add_edges([(u,y),(v,z)])
raise BreakingPairFound(H,Hp)
break
# we have not found a breaking pair, so this triple is a DSF set
print "DSF:",string
except BreakingPairFound as e:
graph6=""
for J in graph_set:
graph6+=">"+J.graph6_string()+"< "
print "broken:",string,graph6,str(e)
if __name__=="__main__":
start=time.clock()
print "Running Phase 1 (generating candidate triples)...."
candidate_triples=Phase1()
print "# candidate triples=",len(candidate_triples)
print
middle=time.clock()
print "Running Phase 2 (testing triples)...."
for i,s in enumerate(candidate_triples):
print "triple #%d" % i,
FindBreakingPair(s[0],s[1])
print
print "Number of distinct breaking pairs used=",len(breaking_pairs)
print
end=time.clock()
total_time=middle-start
minutes=int(total_time/60)
seconds=total_time-minutes*60
print "Phase I computation took %d minutes %.2f seconds." % (minutes,seconds)
total_time=end-middle
minutes=int(total_time/60)
seconds=total_time-minutes*60
print "Phase II computation took %d minutes %.2f seconds." % (minutes,seconds)
total_time=end-start
minutes=int(total_time/60)
seconds=total_time-minutes*60
print "Total computation took %d minutes %.2f seconds." % (minutes,seconds)