3
$\begingroup$

How to solve the induced sub-graph isomorphism problem?

$\endgroup$
  • $\begingroup$ Are your graphs of a particular type, e.g. planar? $\endgroup$ – reinierpost Sep 10 '16 at 17:56
  • $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Jan 4 '17 at 21:48
3
$\begingroup$

To answer the updated question, yes, it can be solved with a SAT solver. The problem is NP-complete, so it is in NP, so therefore it can be reduced to SAT, i.e., expressed in CNF-SAT (see What is the definition of P, NP, NP-complete and NP-hard?). Then you can use an off-the-shelf SAT solver to solve here.

For general techniques, take a look at Converting (math) problems to SAT instances and NP to SAT. How does it works?.

Here are some questions that might also be useful:

$\endgroup$
4
$\begingroup$

This is the induced subgraph isomorphism problem, which was one of the problems proven NP-complete in Cook's original paper on NP-completeness. For a quick way to see that it's NP-complete, you can let $G$ be a complete graph on $k$ vertices to solve CLIQUE on $G'$. Unless you can restrict the form of $G$ and/or $G'$, you're probably out of luck in your quest for a good algorithm.

The problem seems to be easier if you insist that $G$ and $G'$ have the same number of vertices. In this case, you have the graph isomorphism problem. This is generally thought not to be NP-complete and, in December 2015, Babai announced an subexponential-time algorithm, which runs in time $\exp\exp(\tilde{O}(\sqrt{\log n}))$, where $\tilde{O}$ denotes hidden factors of $O(\log\log n)$. This is faster than $O(\mathrm{e}^{n^\epsilon})$ for all $\epsilon>0$. (The algorithm was originally announced as having quasipolynomial running time but an error in the analysis came to light in January 2017.)

$\endgroup$
  • 1
    $\begingroup$ Babai retracted the claim of quasipolynomial runtime. Apparently there was an error in the analysis. $\endgroup$ – Raphael Jan 4 '17 at 21:48
  • $\begingroup$ @Raphael Aww, crap. That's a shame. $\endgroup$ – David Richerby Jan 4 '17 at 22:12
  • 1
    $\begingroup$ Yup. But a useful reminder that we should be more careful when posting about unknowns on websites... *sigh* Had to post that comment a couple of times. ;D $\endgroup$ – Raphael Jan 4 '17 at 22:22

Your Answer

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

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