Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have had the following problem on several occasions and I was wondering whether there is a general technique to solve this problem.

Given a list of graphs with property $P$. Is there a general technique to get a list of common substructures for the given list? Any approximations or heuristics are fine as well.

This problem arises when looking for forbidden substructures for graphs with certain properties. Up to now I usually look for forbidden substructures starting from the property $P$ and by using some intuition as to which substructures might lead to problems. Sometimes I use the information from a backtrack algorithm which detects whether a given graph has property $P$. The points at which the algorithm backtracks usually also give good information about forbidden substructures. However in some cases none of these work, and then it would be nice to have something which can give you a clue about common substructures.

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

I don't think there is a general technique. The only related situation I'm aware of is "motif detection" in biological networks, which involves exhaustively counting small subgraphs in very large sparse graphs. But I don't think it will be useful for finding missing subgraphs in lists of small graphs.

share|improve this answer
1  
This would work if "substructure" means "connected induced subgraph". Our program, NetMODE (ref: dx.doi.org/10.1371/journal.pone.0050093), runs in a terminal so a script could repeatedly call it for each graph. (Since you're not after the biological application, you'd want to use 0 comparison graphs.) –  Douglas S. Stones Jan 6 '13 at 7:59
    
This was what I was afraid for. Substructure mostly means connected induced subgraph, but it could also be less. At the moment I would need it for finding common substructures in a list of quadrangulations, so I don't know if it will be as effective there, since the graphs already have very similar structure and the embedding is also important. –  nvcleemp Jan 6 '13 at 8:22
    
@nvcleemp: What size are the graphs in your list, how long is the list, and what size of induced subgraph would be interesting? –  Brendan McKay Jan 6 '13 at 13:35
    
I am sorry. I somehow missed this reply. The largest size I have at the moment is a list of quadrangulations with 26 vertices. This list contains a few million graphs. –  nvcleemp Jan 25 '13 at 9:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.