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.



Search for common substructures in list of graphs
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.


