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

CC BY-SA 3.0
2012-04-13T06:00:10.470Z
It is a subgraph not an induced subgraph so the independent set argument does not seem to work.
Marcin Kamiński
CC BY-SA 3.0
2012-04-13T07:53:27.097Z
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
CC BY-SA 3.0
2012-04-13T08:48:44.313Z
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.
Marcin Kamiński
CC BY-SA 3.0
2012-04-13T14:04:29.297Z
@MarcinKamiński, I stand corrected.
Peter Taylor
CC BY-SA 3.0
2012-04-16T18:41:57.760Z
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.
Ankur
CC BY-SA 3.0
2012-04-12T17:44:11.900Z
2012-04-12T17:44:11.900Z
Ankur
<p>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. </p>

CC BY-SA 3.0
2012-04-12T12:08:11.110Z
2012-04-12T12:08:11.110Z
Marcin Kamiński
<p>You are given two graphs G and H , and want to know if H is a subgraph of G.</p>

<p>You know that H has a max vertex degree K (constant integer).</p>

<p>What can you say about the complexity of this?</p>

<p>I know that 
<a href="http://ix.cs.uoregon.edu/~luks/iso.pdf" rel="nofollow">Isomorphism of Graphs of Bounded Valence Can Be tested in Polynomial Time - Luks 1982</a>,
that's the best I currently have...</p>

CC BY-SA 3.0
2012-04-12T11:32:27.943Z
(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
CC BY-SA 3.0
2012-04-12T11:38:12.007Z
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
CC BY-SA 3.0
2012-04-12T11:39:36.513Z
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
CC BY-SA 3.0
2012-04-12T11:51:21.083Z
Edited, @Tsuyoshi Ito , thank you very much for the feedback, would be happy to know if further editing is needed.
Liran Orevi
CC BY-SA 3.0
2012-04-12T17:21:52.360Z
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
CC BY-SA 3.0
2012-04-12T17:22:25.493Z
For non-research level questions please use [cs.se].
Kaveh
<cc.complexity-theory><graph-theory><graph-isomorphism><bounded-degree>
Complexity of finding if a degree bounded graph H is a subgraph of an unbounded graph G
Liran Orevi
# Complexity of finding if a degree bounded graph H is a subgraph of an unbounded graph G

(Asked by: username_0 on 2012-04-12)

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](http://ix.cs.uoregon.edu/~luks/iso.pdf),
that's the best I currently have...

**Tags:** cc.complexity-theory, graph-theory, graph-isomorphism, bounded-degree

> **Comments:**
> **username_1**: (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”?  
> **username_0**: Hi @username_1, 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...  
> **username_1**: 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.  
> **username_0**: Edited, @username_1 , thank you very much for the feedback, would be happy to know if further editing is needed.  
> **username_2**: 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.  
> **username_2**: For non-research level questions please use [cs.se].  

---

## 2 answers

### Answer by username_4 on 2012-04-12. Score: 9 | Accepted answer

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.


---

### Answer by username_3 on 2012-04-12. Score: 4

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.

> **Comments:**
> **username_4**: It is a subgraph not an induced subgraph so the independent set argument does not seem to work.  
> **username_5**: 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|$).  
> **username_4**: 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.  
> **username_5**: @MarcinKamiński, I stand corrected.  
> **username_3**: 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.  

---

