1
$\begingroup$

You are given two graphs G and H , and want to know if H is a subgraph of G.

You know that H has a max vertex degree K (constant integer).

What can you say about the complexity of this?

I know that Isomorphism of Graphs of Bounded Valence Can Be tested in Polynomial Time - Luks 1982, that's the best I currently have...

$\endgroup$
  • $\begingroup$ (1) What is the constraint and what is the objective function? If you want to maximize the number of vertices of the chosen subgraph while bounding the maximum degree of the chosen subgraph (as is suggested in the question), then obviously the optimal way is to choose all vertices and no edges. (2) What is “unbounded graph”? $\endgroup$ – Tsuyoshi Ito Apr 12 '12 at 11:32
  • $\begingroup$ Hi @Tsuyoshi Ito, thanks for the help, I want to know if the bounded graph is a subgraph of the unbounded graph, both graphs are given. I'll edit my question... $\endgroup$ – Liran Orevi Apr 12 '12 at 11:38
  • $\begingroup$ I see, but I do not know what you mean by “max vertex” then. Can you edit the question so that people do not have to read comments to understand the question? “Both graphs are given” is a very important piece of information which was missing from the question. $\endgroup$ – Tsuyoshi Ito Apr 12 '12 at 11:39
  • $\begingroup$ Edited, @Tsuyoshi Ito , thank you very much for the feedback, would be happy to know if further editing is needed. $\endgroup$ – Liran Orevi Apr 12 '12 at 11:51
  • 1
    $\begingroup$ Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the FAQ for more information. $\endgroup$ – Kaveh Apr 12 '12 at 17:21
9
$\begingroup$

If H is the cycle on |G| vertices (and is of maximum degree 2), then this is the Hamiltonian cycle problem. Seems like your problem is NP-hard.

$\endgroup$
4
$\begingroup$

To add to the answer from Marcin Kaminski - H could even be the complement of a complete graph (i.e., regular graph with degree = 0). So your problem is at least as hard as the independent set problem, and is thus NP-hard. The max degree of G is immaterial.

$\endgroup$
  • 2
    $\begingroup$ It is a subgraph not an induced subgraph so the independent set argument does not seem to work. $\endgroup$ – Marcin Kamiński Apr 13 '12 at 6:00
  • $\begingroup$ Although if you set a degree limit of 1 for H then the problem reduces to the independent set problem on a graph G' whose vertices are the edges of G and are connected iff they share a vertex in G, so the only tractable case is a degree limit of 0 (in which case it's just a case of checking $|H| \le |G|$). $\endgroup$ – Peter Taylor Apr 13 '12 at 7:53
  • 1
    $\begingroup$ It is the independent set problem in line graphs, and this is computationally easy. I think that if deg(H) <=1, then the subgraph problem can be solved in polynomial time. $\endgroup$ – Marcin Kamiński Apr 13 '12 at 8:48
  • $\begingroup$ @MarcinKamiński, I stand corrected. $\endgroup$ – Peter Taylor Apr 13 '12 at 14:04
  • $\begingroup$ Good point Marcin Kaminski. An argument, such as yours, where H is a Hamiltonian circuit of G, or one where H is a clique, is a correct one. $\endgroup$ – Ankur Apr 16 '12 at 18:41

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.