Given an undirected graph $G=(V,E)$ and a vertex $v\in V$, is there some algorithms to enumerate all induced subgraphs $G_s=(V_s,E_s)$, such that $v \in V_s$? It's preferred the algorithm doesn't enumerate duplicated subgraphs.

  • 2
    $\begingroup$ Do the subgraphs have to be connected? If not, including vertex $v$ is almost no restriction. By duplicate, do you mean up to isomorphism, and should $s$ be regarded as a distinguished vertex, if so (e.g., are the paths $asb$ and $abs$ different)? $\endgroup$ Sep 7, 2015 at 15:35
  • $\begingroup$ Thanks. A subgraph is connected, otherwise it's trivial. A subgraph duplicates another if they have the same vertices. Direction of paths are not considered $\endgroup$
    – yliueagle
    Sep 7, 2015 at 15:39
  • 1
    $\begingroup$ So you're looking for induced subgraphs? Please edit the question so all these points are clear without people needing to read the comments. Thanks. $\endgroup$ Sep 7, 2015 at 16:05
  • $\begingroup$ In addition, please tell us in the question what you've tried and what you are stuck on. This looks like a straightforward programming question, so I'm having a hard time understanding what you find puzzling -- if you can help us understand that, it might help get you better answers. Have you looked at other questions tagged enumeration? $\endgroup$
    – D.W.
    Sep 7, 2015 at 17:04


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.