#include <stdio.h> #define N 30 // Maximum number of vertices. Must be <= number of bits in an int variable. #define OPT 1 // If non-zero, perform optimizations by only checking certain sets of k added edges. int A[N][N]; // Adjacency matrix of G. int v[N]; // List of vertices in substructures. int dg[N]; // Number of cross edges meeting a vertex. int n1; // Number of vertices in first subgraph G_1 (if G = G_1\cup G_2 + ke). int nt; // Total number of vertices in graph. // Declare some simple graph types. // typedef enum {None=0,Path=1,Cycle=2,Cdag=3,Cplus2=4} gtype; // Types of graph. int minsize[]={0,1,3,4,4}; // Minimum number of vertices needed for each type. char* names[]={"","P_","C_","C^d_","C^+2_"}; // Short names of the types of graph. // Clear graph and entire adjacency matrix. // Must be called before addgraph() is used. // void cleargraph(){ int i,j; for(i=0;i<N;i++)for(j=0;j<N;j++)A[i][j]=0; // Zero out adjacency matrix. for(i=0;i<N;i++)dg[i]=0; // Also clear cross-degree array. n1=nt=0; // Graph now has 0 vertices. } // Add a vertex disjoint Path or Cycle to current graph. // Graph (adjacency matrix) should be zeroed first by cleargraph() as addgraph() only adds edges. // Sequence of calls should be e.g.: cleargraph(); addgraph(t1,v1); addgraph(t2,v2); // void addgraph(gtype t,int n){ int i; if(nt+n>N||nt<0){printf("Error: too many vertices in graph\n");exit(0);} if(t!=Path&&t!=Cycle){printf("Error: can only construct paths and cycles here\n");exit(0);} for(i=nt;i<nt+n-1;i++)A[i][i+1]=A[i+1][i]=1; // Add path. if(t==Cycle)A[nt][nt+n-1]=A[nt+n-1][nt]=1; // Close cycle. n1=nt;nt+=n; // Update n1,nt. } // Recursive routine to find a structure consisting of at most two subgraphs of given form in G. // v0 = index in v[] of first vertex in current subgraph. // vn = index in v[] of next vertex in current subgraph. // bm = bit mask of remaining vertices. // nr = number of remaining vertices that can be used. // ch = number of chords found (plus 1 as it counts the closing edge of the cycle as a chord). // t1,t2 = types of subgraph to find. Current subgraph is type t1. // int findr(int v0,int vn,int bm,int nr,int ch,gtype t1,gtype t2){ int vmax,u,w,c; if(v0==vn){ // If subgraph not started. if(nr<minsize[t1]+minsize[t2])return 0; // Fail if too few vertices remaining. if(t1==None){t1=t2;t2=None;} // Skip trivial graph type. if(t1==None)return 1; // Finished! for(w=0;w<nt;w++){ // Loop over possible first vertices. if((bm&(1<<w))!=0){ // Check vertex still available. v[v0]=w; // Record new vertex in v[]. if(findr(v0,v0+1,bm-(1<<w),nr-1,0,t1,t2))return 1; // Recursive call to find rest of the structure. } } return 0; // Failed for all choices of first vertex. } // Check if we have found subgraph and recursively call findr() to find second substructure if done. if(vn-v0>=minsize[t1]){ // No point checking if not enough vertices. if( (t1==Path) // We always have constructed a path v[v0]-v[vn-1]. ||(t1==Cycle && A[v[v0]][v[vn-1]]) // Need a closing edge for cycles. ||(t1==Cdag && A[v[v0]][v[vn-1]] && ch>((vn-v0==4)?1:2)) // Check enough chords for Cdag. Number of chords is ch-1. ||(t1==Cplus2&& A[v[v0]][v[vn-1]] && ch>2)){ // Check enough chords for Cplus2. Number of chords is ch-1. if(findr(vn,vn,bm,nr,0,t2,None))return 1; // Recursively find second subgraph. } } if(nr<=minsize[t2])return 0; // Run out of vertices. if(t1!=Path)vmax=v[v0]; else vmax=nt; // For efficiency, assume first vertex of cycle is largest. for(w=0;w<vmax;w++){ // Loop through possible next vertices. if((bm&(1<<w))!=0 && A[v[vn-1]][w]){ // Must be available and joined to the previous vertex. for(c=ch,u=v0;u<vn-1;u++)c+=A[v[u]][w]; // Count chords. v[vn]=w; // Record new vertex in v[]. if(findr(v0,vn+1,bm-(1<<w),nr-1,c,t1,t2))return 1; // Recursive call to find rest of the structure. } } return 0; // No structure found. } // Find number of extra edges needed to ensure no suspended path length >2 in P_* and both ends covered. // This is used in the optimization of findbetween(). If we have found substructures for all choices of cross edges // and smaller P_*, then we can assume the cross edges meet the ends of P_* and at least every other vertex along P_* // as otherwise we would have found a counterexample with smaller P_*. // int extraedges(){ int i,c,f; c=f=0; // c=extra edges needed, f=1 if last vertex covered. for(i=n1;i<nt;i++){ // Loop through P_*. if(dg[i])f=1; // If vertex covered, we are OK for this and the next vertex. else if(f)f--; // If last vertex covered, we are still OK. else {c++;f=1;} // Need an extra edge, but then we would be OK for the next vertex. } return c; } // Optimization check. Returns 0 if current subset of edges does not need to be checks. // t = Type of graph (either 2 paths or 2 cycles) // k = Number of remaining edges to be added. // j = Vertex in G_2 that is incident to last edge added. // int optimization(gtype t,int k, int j){ if(t==Path)return extraedges()<=k; // For paths, need every other vertex of P_* covered. if(t==Cycle && j<nt-1){ // For cycles, require last vertex to have max degree. // Edges are found in reverse order in the vertex j, so if j<nt-1 the vertex nt-1 already has its final degree // and vertices <j have zero degree in cross-edges. return dg[j]<=dg[nt-1] && (j-n1+1)*dg[nt-1]-dg[j]>=k; // Degree of j OK and enough room for remaining edges. } return 1; } // Recursive routine to find structure for all k-sets of edges between G_1 and G_2. // k = number of remining edges to add. // l = last edge added (we optimize by assuming edges are chosen in reverse order). // t1,t2 = structures of subgraph(s) to find. // nr = max number of vertices these structures can use. // If f=1 then we make sure the endvertices and at least every other vertex in the path G_2 is covered by cross edges. // Edges from vertex i<n1 to j>=n1 are sorted by value of i+n1*(j-n1). // Routine assumes no edges originially exist between G_1 and G_2. // int findbetween(int k,int l,gtype t1,gtype t2,int nr,gtype t){ int e,i,j; if(findr(0,0,(1<<nt)-1,nr,0,t1,t2))return 1; // Substructure exists. if(k==0)return findr(0,0,(1<<nt)-1,nr,0,t1,t2); // No further edges allowed, so fails. for(e=k-1;e<l;e++){ // Loop over feasible choices of the next edge. i=e%n1; j=e/n1; // Endvertices of e are i and j+n1. A[i][j+n1]=A[j+n1][i]=1; // Add edge to adjacency matrix. dg[j+n1]++; // Record the degree of cross-edges to G_2. if(OPT==0||optimization(t,k-1,j+n1)){ // Filter out unnecessary checks if OPT=1 if(!findbetween(k-1,e,t1,t2,nr,t))return 0; // Recursively check that it is always OK to include this edge. } A[i][j+n1]=A[j+n1][i]=0; // Remove edge from adjacency matrix. dg[j+n1]--; // Return the degree of cross-edges to original value. } return 1; // Was always OK. } // If k edges are added between two graphs of type t of orders v1 and v2, // can we always find vertex disjoint graphs of types t1 and t2. // If s=1 then we must not use all vertices. // int between(gtype t,int v1,int v2,int k,gtype t1,gtype t2,int s){ int i,j; printf("%s%d + %s%d + %de",names[t],v1,names[t],v2,k); // Print the type of graph we are constructing. if(s)printf(" > "); else printf(" >= "); // Can we use all the vertices? printf("%s*",names[t1]); // Substructure to find. if(t2!=None)printf(" + %s*",names[t2]); cleargraph(); // Construct base graph without added edges. addgraph(t,v1); addgraph(t,v2); #if OPT // As an extra optimization, we can always assume one edge goes to last vertex of G_2. // (For paths: if not, then taking the redundant vertices at the end of the path G_2 // and adding them on at the beginning of G_2 can never hurt us when looking for cyclic substructures.) // For cycles we can also assume this comes from last vertex of G_1. // For paths we can only assume this comes from the second half of G_1. // Note that the largest edge in our ordering can be assumed to be this edge. j=n1+v2-1; // Last vertex of G_2. dg[j]=1; // Record cross-degree of this vertex. if(t==Path)i=v1/2; else i=v1-1; // Middle or last vertex of G_1. for(;i<v1;i++){ // For all choices of largest edge. A[i][j]=A[j][i]=1; // Add edge to adjacency matrix if(!findbetween(k-1,i+n1*(j-n1),t1,t2,nt-s,t)){ // Find structure for all choices of remaining k-1 edges printf(" No\n");return 0; // Failed. } A[i][j]=A[j][i]=0; // Remove edge from adjacency matrix. } printf(" Yes\n");return 1; // Always succeeded. #else // Unoptimized version. if(findbetween(k,v1*v2,t1,t2,nt-s,t)){ // Find structure for all choices of k edges printf(" Yes\n");return 1; // Always succeeded. } else {printf(" No\n");return 0;} // Failed. #endif } // Recursive routine to find substructure for all k-sets of chords within G (assumed to be cycle). // k = number of remining edges to add. // l = last edge added (we optimize by assuming edges are chosen in reverse order). // t1,t2 = structures of subgraph(s) to find. // nr = max number of vertices these substructures can use. // Edges from vertex i to j are sorted as nt*j+i, i<j. // We could add some optimizations on the set of chords added, but the routine is fast enough as it is. // int findwithin(int k,int l,gtype t1,gtype t2,int nr){ int i,j; if(findr(0,0,(1<<nt)-1,nr,0,t1,t2))return 1; // Substructure exists. if(k==0)return 0; // No further edges allowed, so fails. for(j=0;nt*j<l;j++){ // Loop over choices of the next edge. for(i=0;i<j&&nt*j+i<l;i++){ if(!A[i][j]){ // Don't add edge if it already exists. A[i][j]=A[j][i]=1; // Add edge to adjacency matrix. if(!findwithin(k-1,nt*j+i,t1,t2,nr))return 0; // Recursively check that it is always OK to include this edge. A[i][j]=A[j][i]=0; // Remove edge from adjacency matrix. } } } return 1; // Always succeeded. } // If k chords are added to a cycle of order v1 can we always find a subgraph of type t1. // If s=1 then must not use all vertices. // int within(int v1,int k,gtype t1,int s){ printf("C_%d + %de",v1,k); // Print description of graph. if(s)printf(" > "); else printf(" >= "); // Can we use all the vertices. printf("%s*",names[t1]); // Substructure to find. cleargraph(); // Construct base graph without added edges. addgraph(Cycle,v1); if(findwithin(k,v1*v1,t1,None,nt-s)){ // See if substructure always exists. printf(" Yes\n");return 1; // Always succeeded. } else {printf(" No\n");return 0;} // Failed. } main(){ int n,m,k; if(sizeof(int)*8<N){printf("Error: maximum size of graph (N) too big\n");exit(0);} if(OPT)printf("Optimizations On\n\n"); else printf("Optimizations Off\n\n"); printf("Lemma 5\n"); for(n=5;n<=8;n++){ for(k=2;;k++)if(within(n,k,Cdag,1))break; for(;;k++)if(within(n,k,Cplus2,1))break; // no point looking for C^+2 if no C^\dag printf("\n"); } printf("Lemma 9\n"); // Note that wlog P_* has at most 2k-1 vertices. Indeed, if there were a subtended subpath of P_* // between endvertices of the added edges, we can safely shorten it to length 2 without // creating any additional C^\dag_*'s. As an extra optimization (if OPT set), we insist that // the endvertices and every other vertex of P_* meet cross-edges, as otherwise we would find // a counterexample with smaller size of P_*. for(n=1;n<=5;n++){ for(k=2;;k++)if(between(Path,n,2*k-1,k,Cdag,None,0))break; // We do the hard case m=2k-1 first. for(m=2*k-2;m>=1;m--){ for(;;k++)if(between(Path,n,m,k,Cdag,None,0))break; // Then we check the smaller m's. } printf("P_%d + P_* + %de >= C^d_* OK\n\n",n,k); // Summary statement of results. for(;;k++)if(between(Path,n,2*k-1,k,Cdag,None,1))break; // no point looking for > if not >=. for(m=2*k-2;m>=1;m--){ for(;;k++)if(between(Path,n,m,k,Cdag,None,1))break; // Check smaller m's. } printf("P_%d + P_* + %de > C^d_* OK\n\n",n,k); // Summary statement of results. } printf("Lemma 10\n"); for(m=3;m<=4;m++){ for(k=8;;k++)if(between(Cycle,4,m,k,Cycle,Cycle,1))break; printf("\n"); } for(n=4;n<=7;n++){ for(m=3;m<=n;m++)if(m+n>=8){ for(k=9;;k++)if(between(Cycle,n,m,k,Cdag,Cycle,1))break; printf("\n"); } } // This last section takes a long time to run, especially n=7. printf("Lemma 11\n"); for(n=5;n<=7;n++){ for(m=4;m<=n;m++){ for(k=13;;k++)if(between(Cycle,n,m,k,Cdag,Cdag,1))break; printf("\n"); } } printf("Finished\n"); }