3
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ 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.) $\endgroup$
    – Douglas S. Stones
    Commented Jan 6, 2013 at 7:59
  • $\begingroup$ 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. $\endgroup$
    – nvcleemp
    Commented Jan 6, 2013 at 8:22
  • $\begingroup$ @nvcleemp: What size are the graphs in your list, how long is the list, and what size of induced subgraph would be interesting? $\endgroup$
    – Brendan McKay
    Commented Jan 6, 2013 at 13:35
  • $\begingroup$ 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. $\endgroup$
    – nvcleemp
    Commented Jan 25, 2013 at 9:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .