# Complexity of finding if a degree bounded graph H is a subgraph of an unbounded graph G

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...

• (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”? – Tsuyoshi Ito Apr 12 '12 at 11:32
• 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... – Liran Orevi Apr 12 '12 at 11:38
• 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. – Tsuyoshi Ito Apr 12 '12 at 11:39
• Edited, @Tsuyoshi Ito , thank you very much for the feedback, would be happy to know if further editing is needed. – Liran Orevi Apr 12 '12 at 11:51
• 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. – Kaveh Apr 12 '12 at 17:21

• 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|$). – Peter Taylor Apr 13 '12 at 7:53