13
$\begingroup$

I am looking for any related work to the following problem. Say you have a large directed graph $G$ and you want to find rare (or unique) subgraphs of minimal size that are not isomorphic to any other subgraph of $G$. I assume this problem is NP-hard but is there any work on it? For example, exact algorithms for sparse, planar etc. graphs or approximation algorithms or even heuristics. Just to fix ideas, every node or edge connected pair of nodes will be isomorphic to some other subgraph so the minimum size this could ever be in a non-trivial graph would be of size $3$ nodes.

There is a very nice bibliography as of 1995 of the subgraph isomorphism problem linked from David Eppstein's publication page . Is there anything more relevant to my problem?

Improve this question
$\endgroup$
4
  • $\begingroup$ if they are "small size", seems hard to imagine algorithm that works better than brute force enumeration/checking... if they are small enough below some limit, wrt the size of the graph, the problem would even be in P, right? $\endgroup$
    – vzn
    Aug 17, 2012 at 22:35
  • $\begingroup$ It's not obvious to me even in the case of Erdos-Renyi graphs. I don't think there is any chance for worst case dense graphs but many real world graphs are not like that. $\endgroup$
    – Simd
    Aug 19, 2012 at 10:18
  • $\begingroup$ You might want to make the question more specific; it is hard to provide an answer because it is not clear if a possible answer relates to the question or not. Given a digraph $G$, do you want to find a digraph $H$ which occurs as a subgraph (presumably not induced), but so that there are no other copies of $H$ in $G$, and so that every proper subgraph of $H$ occurs as a subgraph of $G$? Or are you looking for the globally smallest subgraph which occurs uniquely? Are you happy with some constant bound $c>1$ on the number of distinct copies? Or do you actually want induced subgraphs? $\endgroup$
    – András Salamon
    Aug 19, 2012 at 13:51
  • $\begingroup$ I am really trying to explore the landscape of tractable variants which seems rather barren at present. Both maximal and maximum rare subgraphs are interesting as are any approximation algorithms (in terms for example of outputting too many or too few subgraphs). I would even be interested in results on random graphs. $\endgroup$
    – Simd
    Aug 21, 2012 at 17:07

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.