0
$\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...

Improve this question
$\endgroup$
6
  • $\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
    Commented Apr 12, 2012 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
    Commented Apr 12, 2012 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
    Commented Apr 12, 2012 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
    Commented Apr 12, 2012 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
    Commented Apr 12, 2012 at 17:21

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
0
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.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ It is a subgraph not an induced subgraph so the independent set argument does not seem to work. $\endgroup$
    – Marcin Kamiński
    Commented Apr 13, 2012 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
    Commented Apr 13, 2012 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
    Commented Apr 13, 2012 at 8:48
  • $\begingroup$ @MarcinKamiński, I stand corrected. $\endgroup$
    – Peter Taylor
    Commented Apr 13, 2012 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
    Commented Apr 16, 2012 at 18:41

Your Answer

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

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