2
$\begingroup$

It is well known that the subgraph isomorphism problem is NP-complete. And so a polynomial-time algorithm for solving it would mean P = NP. Thus I'm interested in whether a bounded version of the problem has a polynomial time algorithm that is known about. Many applications of graphs don't require more than say 50 incident edges per node. For example in visualizations involving commutative diagrams of mathematics, rarely is there a need for anywhere close to that number of connections. This is because as the graph complexity grows, the diagram becomes more useless as a mnemonic for studying math.

So, my question is: if we constrain our nodes to have maximally a constant number of incident edges, then does the subgraph isomorphism problem become polynomial-time solvable?

That is, both the query graph $G$ and the large graph $H$ have bounded incident edges, such that you're trying to find an isomorphism of $G \xrightarrow{\sim} H' \subset H$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The problem is still NP-hard. You can show a polynomial-time reduction from the Hamiltonian path problem on graphs of degree at most $3$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ What about a bounded number of nodes in $G$ as well as bounded incident edges on both graphs? $\endgroup$
    – D Left Adjoint to U
    Sep 24, 2021 at 4:23
  • 1
    $\begingroup$ Yeah but $n$ choose some constant quantity $c$ is $n^c$ only. So polynomial time it is. $\endgroup$
    – D G
    Sep 24, 2021 at 4:26
  • $\begingroup$ Could you explain that more? $\endgroup$
    – D Left Adjoint to U
    Sep 24, 2021 at 4:26
  • $\begingroup$ Any way to do that in less time? Since $G$ will typically contain 1-100 nodes, and $|V_H|^{100}$ is too big. $\endgroup$
    – D Left Adjoint to U
    Sep 24, 2021 at 4:30
  • 1
    $\begingroup$ @SmokenSieEinBitteChebaHitBits Yes, it is possible to do better. Suppose the degree of $H$ is at most $d$ and number of nodes in $G$ are at most $k$. Then, once you map a vertex of $G$ to a certain vertex $v$ in $H$; there are only $d$ choices for the second vertex, and $d^2$ choices for third vertex and so on. Thus the running time will be $O(d^k \cdot n)$. $\endgroup$
    – D G
    Sep 24, 2021 at 4:56

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.