<p>I'm looking for a reference of the complexity of the following problem.</p>

<p>Let our input $C$ be a finite set of graphs. Is there a graph $G$ such that:</p>

<ol>
<li>$G$ has a minor in $C$</li>
<li>$G$ has <strong>no</strong> subgraph in $C$?</li>
</ol>

<hr>

<p>As per Robin's suggestion, here's why I believe it's $NP$-hard and within $NP^{NP}$. This is just written out informally, I can formalize if it'd help.</p>

<hr>

<p><strong>co-NP Hardness</strong></p>

<p>Let $G = (V, E)$ be an arbitrary graph with internal and external edges, an even number of vertices, and maximum degree 3. Such graphs in general are still $NP$-hard for Hamiltonian Path.</p>

<p>First, create a subvidided claw $H$ by attaching 3 paths of lengths $|V|/2$, $|V|/2$ and $|V|$ to a central vertex. Next, make $|E|$ copies of $G$, labelled $G_1, ..., G_{|E|}$. For each $G_i$, subdivide edge $i$ once, and to this new intermediate vertex, attach a dangling path $P_i$ of length $|V|$. Finally, attach one new vertex to the second-to-last vertex in this path, so that the addition consisted of 2 external and $|V|-1$ internal edges. Finally, let $G'$ be the disjoint union of all $G_i$.</p>

<p>Now, we can define $C$ as $\{G', H\}$.</p>

<p>Suppose that $G$ has a Hamiltonian Path. Then $H$ is a subgraph of some $G_i$, as the long arm fits into some $P_i$, the central vertex on the vertex added thru subdivision, and the other two arms make the path.</p>

<p>Suppoes that $H$ is a subgraph of $G'$. Well, $H$ is a simple component, and a little simple math shows that $G$ must have a Hamiltonian path.</p>

<p>OK, now we have that $H$ is a minor and subgraph of $G'$ iff $G$ has a Hamiltonian path. So consider the graph $G''$ obtained by subdividing an edge on $P_1$ a bunch of times. As this edge is internal, $G'$ is not a subgraph of $G''$. And $H$ is a subgraph of $G''$ iff $G$ has a Hamiltonian path.</p>

<hr>

<p><strong>NP to the NP</strong></p>

<p><strong>From my comment, why $G$ won't be too big:</strong> Let's consider the smallest such $G$. Let $x$ be number of edges in graph of $C$ with most edges. No graph in C can consume all of a path of length $x+1$. As $G$ has as a minor some $H \in C$, we can look at the model of $H$ in $G$. Clearly, no reason to simply add edges or vertices to $H$. So we can get from $G$ to $H$ with just contraction. No path needs to be contracted more than $x+1$ times or we could have shortened it. This gives a reasonable size bound.</p>

<p>For $NP^{NP}$: given a graph $G$ with a minor in $C$, we need to ensure that for each graph $H$ in $C$, $H$ is not a subgraph $G$. One can imagine a TM which has a computation path for every each graph and way to split its vertices, which then queries an $NP$ oracle for each graph in $C$ to see if it's not a subgraph.</p>

<hr>

<p>Any citations out there?</p>

<hr>

<p>I'm also interested in a version where either all graphs of $C$ are subcubic or <em>condition 1</em> is for topological minors instead of normal ones.</p>

CC BY-SA 3.0
2012-09-05T22:47:33.210Z
If C is a finite set not dependent on the input, then this should be in P, right? You can check if the input has any graph in C as a minor in $O(n^3)$ time. And you can check if it has any graph in C as a subgraph in $O(n^k)$ time, where k is the size of the largest graph in C.
Robin Kothari
CC BY-SA 3.0
2012-09-06T00:04:00.487Z
Robin: $C$ is the input.
Eli
CC BY-SA 3.0
2012-09-06T00:09:28.407Z
How do you get the $P^{NP}$ upper bound?
Radu Curticapean
CC BY-SA 3.0
2012-09-06T00:14:50.007Z
First, need to show that if there is a $G$ then it's small enough. Let's consider the smallest such $G$. Let $x$ be number of edges in graph of $C$ with most edges. No graph in $C$ can consume all of a path of length $x+1$. As $G$ is a minor of some graph $H \in C$, we can look at the model of $G$ in $H$. Clearly, no reason to simply add edges or vertices to $H$. So we can get from $G$ to $H$ with just contraction. No path needs to be contracted more than $x+1$ times or we could have shortened it. This gives a reasonable size bound.
Eli
CC BY-SA 3.0
2012-09-06T00:17:46.193Z
Next, we're asking if there is a graph of at most this size such that (1) it is a minor of some graph in $C$ (takes NP power), (2) it has no subgraph in $C$ (takes co-NP power). I can try to be more formal if this idea isn't enough.
Eli
CC BY-SA 3.0
2012-09-06T01:53:56.087Z
@Eli: Oh, I see. I misinterpreted the question. Might be good to point that out more clearly so that others don't make a similar mistake. Also, for the benefit of future readers, it might be a good idea to incorporate all your comments into the question so that future readers don't need to read the comments.
Robin Kothari
CC BY-SA 3.0
2012-09-06T02:06:58.857Z
Maybe also mention why the problem is NP-hard?
Robin Kothari
CC BY-SA 3.0
2012-09-06T04:16:02.140Z
Good idea, updated.
Eli
CC BY-SA 3.0
2012-09-06T12:21:38.183Z
I cannot understand your proof of membership to P^NP.  If we are given both C and G, then indeed we can decide whether G satisfies the condition or not by using two queries to NP, as you wrote (with minor corrections in wording).  But how does the algorithm work without being given G?  It looks to me that you are proving the membership to NP^NP.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-06T20:09:30.307Z
Tsuyoshi, you are correct. More is needed to show $P^{NP}$, I'm updating my answer accordingly.
Eli
CC BY-SA 3.0
2012-09-06T20:45:25.330Z
You mentioned that you're interested in the case where all the graphs in C are cubic. It seems like that case is easy. More generally, I think if C does not contain a path or subdivided claw, then such a graph $G$ must exist.
Robin Kothari
CC BY-SA 3.0
2012-09-06T22:33:16.983Z
@Robin, sorry, I meant subcubic. Obviously, we need a graph with no internal edges. We can take the disjoint union of paths and subdivided claws, too.
Eli
CC BY-SA 3.0
2012-09-07T00:51:14.687Z
I believe Robin's comment is correct.  An easier statement is that if graph in $C$ contains a cycle, $G$ must exist.  To see this, simply take a graph in $C$ and subdivide an edge until the largest cycle is larger than any cycle in any graph in $C$.  Robin's statement should follow similarly, except you need to split high-degree vertices into binary trees, if you know what I mean.
Andrew D. King
CC BY-SA 3.0
2012-09-07T01:40:09.187Z
@AndrewD.King: only in cubic graphs, which aren't particularly interesting (I typoed and meant subcubic). If every graph in $C$ contains a cycle then one can subdivide all edges in one graph an absurd number of times and of course it has no subgraph in $C$. This holds if all graphs in $C$ have internal edges, in fact. This isn't necessarily the case in a set of subcubic graphs, though.
Eli
CC BY-SA 3.0
2012-09-07T17:59:30.610Z
I also fail to follow the proof of NP-hardness.  In your reduction, I understand that if a graph G contains K as a minor, then it contains K as a subgraph.  This means that if there is any graph G that satisfies the condition, then G must contain H′ as a minor while avoiding both K and H′ as subgraph.  But how do you proceed from this?
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-07T19:50:27.833Z
@TsuyoshiIto, I updated my proof, does this make more sense now? Note that I changed around which variables meant what to more correspond with how I have previously written this proof.
Eli
CC BY-SA 3.0
2012-09-07T21:03:46.040Z
Now I follow your proof, thanks.  I think that you can try to clean it up, in particular by explicitly saying that you are proving coNP-hardness (under many-one reducibility) instead of saying NP-hardness (under Turing reducibility).  The last paragraph of the proof will be easier to read if you avoid using “it” and if you separate the case where G has a Hamiltonian path and the case where G does not.  The graph called “it” is used only in the case where G does not have a Hamiltonian path, but it is unclear from the way you wrote.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-07T21:13:17.150Z
(I realized that I still do not follow the construction of the graph called “it,” but I will not bug you to clarify it.)
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-07T22:00:05.670Z
@TsuyoshiIto, fixed "it" up a bit for you. $G''$ is just $G'$ with a subdivision where it doesn't affect $H$-subgraph-containment but ruins $G'$-subgraph-containment.
Eli
CC BY-SA 3.0
2012-09-08T19:06:16.470Z
What does it mean for a graph to have internal and external edges?
Tyson Williams
CC BY-SA 3.0
2012-09-08T23:06:44.177Z
Start at a degree-1 vertex and walk until you hit a degree 3 or higher vertex. This is a dangling path. All edges on it are external. All edges not on dangling paths are internal.
Eli
CC BY-SA 3.0
2012-09-10T20:41:31.163Z
do you definitely mean _subgraphs_ and not _induced subgraphs_? there is misc research into the latter
vzn
CC BY-SA 3.0
2012-09-11T00:53:39.977Z
I do mean just plain old _subgraphs_, but if you can characterize it with induced subgraphs, that's also interesting.
Eli
CC BY-SA 3.0
2012-09-11T18:21:48.670Z
there seems to be a lot of work on the [_forbidden subgraph problem_](http://en.wikipedia.org/wiki/Forbidden_subgraph_problem) problem which seems closely related to yours. however, on quick glance seems like you might seriously be underestimating the complexity of the problem. the issue it seems is that graphs that exclude a list of finite subgraphs can be very large...? have you heard of universal graphs? does this ref relate to your problem-- [universal graphs with forbidden graphs and algebraic closure](http://arxiv.org/pdf/math/9809202.pdf)
vzn
CC BY-SA 3.0
2012-09-11T22:14:04.820Z
vzn: my problem here is definitely in $NP^{NP}$, and probably complete for it. I've read extensively about the forbidden subgraph problem and closely related things. Note that our problem is much easier if $|C| = 1$ (in fact, it can be solved in linear time). I don't quite see a more direct connection between my problem and forbidden subgraphs.  That universal graphs paper doesn't mention minors, I'll read it over in closer detail later, though.
Eli
CC BY-SA 3.0
2012-09-12T04:14:01.683Z
you say "G is a minor of some graph H in C". dont you mean "some graph H in C is a minor of G"? or "G has some minor graph H in C"?
vzn
CC BY-SA 3.0
2012-09-12T13:21:55.457Z
Hi vzn, you are correct, I fixed some inaccuracies in my posting. Some of my early comments are uneditable and incorrect.
Eli
CC BY-SA 3.0
2012-09-12T15:43:19.053Z
ok. also, admittedly, just not following your upper bound sketch. you seem to basically assert that if a graph has a minor, there is some size limit on how large the graph is wrt the minor (relative to paths in the graph or its minor or something). [maybe a newbie question here] but isnt it true that a graph can be arbitarily much larger than one of its minors?
vzn
CC BY-SA 3.0
2012-09-12T15:54:33.640Z
reading the defn of [minor](http://en.wikipedia.org/wiki/Graph_minor), isnt every induced subgraph of a graph also a minor, because minors contract _zero_ or more edges of induced subgraphs? so the construction of rules 1,2 seems inconsistent; do you mean something else? ps here is a nice Phd thesis on [forbidding induced subgraphs](http://www.cs.mcgill.ca/~yzwols/thesis.pdf) by yori zwols, 2010
vzn
CC BY-SA 3.0
2012-09-12T22:00:09.503Z
vzn: my rules aren't inconsistent because you can have minors that aren't subgraphs. Let $G$ be a graph, $M$ be the set of minors of $G$, $I$ be the set of induced subgraphs of $G$, and $S$ be the set of subgraphs of $G$. $I \subseteq S \subseteq M$. $G$ has no internal edges iff $S = M$. For an example, let $C = \{ K_4 \}$. Consider the graph with one edge in $K_4$ subdivided once. It has no $K_4$ subgraph but it does have a $K_4$ minor.
Eli
CC BY-SA 3.0
2012-09-12T22:03:47.297Z
vzn: for my upper bound. Suppose $A$ has $B$ as a minor (using different letters from above to avoid confusion). Then you can apply a series of operations to $B$ to get a graph isomorphic to $A$. You can add a vertex, add an edge, or 'split' a vertex (opposite of contract). If you disallow adding vertices and edges, there are only so many vertices to split before any split is the same as subdivision. Since I'm looking for the smallest $G$, no reason to add edges or vertices. And no reason to perform too many subdivisions. I'll expand on this below.
Eli
CC BY-SA 3.0
2012-09-12T22:04:52.397Z
Why shouldn't we add vertices or edges? Doing so strictly makes the set of subgraphs strictly larger. Why shouldn't we subdivide arbitrarily? After a while we'll create a path that nothing can span. After this point, no reason to go farther.
Eli
CC BY-SA 3.0
2012-09-12T23:00:02.793Z
sounds like you are interested in what might be called "proper minors" that are minors but not subgraphs (maybe there is some other recognized term). is it equivalent to say that "none of the $C$ are subgraphs of $G$"? and, ?! there is nothing in the problem statement that says you're looking for the _smallest_ $G$. think you need some assertion in the form, "if G exists, it is not larger than [x] because [y]"... cant follow that in your current writeup, can anyone else?
vzn
CC BY-SA 3.0
2012-09-13T02:10:59.387Z
vzn: you are correct in that we do not care about finding the smallest $G$, we just want to know whether one exists. All that my paragraph on the size of $G$ demonstrates is that if any $G$ exists, there is some graph satisfying conditions (1) and (2) of the problem statement of a polynomial size. That's all that's important, then the remainder of my $NP^{NP}$ sketch holds. Since we have nondeterminism (and copious amounts), we can guess $G$. But only if its size is reasonable. Thus, I argue that one of reasonable size exists.
Eli
CC BY-SA 3.0
2012-09-13T19:01:52.230Z
dont think your reasoning makes sense. your writeup in the question is not fully fleshed out. not familiar with the theory enough to shoot off a quick counterexample, but how about this. from ch3 of zwols, a graph with no four-edge or five-edge path in the complement is conjectured (Erdos-Hajnal) to have exponentially large cliques. that can only happen if the graph itself is exponentially large. true?
vzn
CC BY-SA 3.0
2012-09-13T22:10:58.067Z
What statement of mine in particular do you disagree with?
Eli
<cc.complexity-theory><reference-request><graph-theory><graph-minor>
Citation request: Complexity of determining if a graph exists with a minor but no subgraph in set
Eli
# Citation request: Complexity of determining if a graph exists with a minor but no subgraph in set

(Asked by: username_0 on 2012-09-05)

I'm looking for a reference of the complexity of the following problem.

Let our input $C$ be a finite set of graphs. Is there a graph $G$ such that:

1. $G$ has a minor in $C$
2. $G$ has **no** subgraph in $C$?

---

As per Robin's suggestion, here's why I believe it's $NP$-hard and within $NP^{NP}$. This is just written out informally, I can formalize if it'd help.

---

**co-NP Hardness**

Let $G = (V, E)$ be an arbitrary graph with internal and external edges, an even number of vertices, and maximum degree 3. Such graphs in general are still $NP$-hard for Hamiltonian Path.

First, create a subvidided claw $H$ by attaching 3 paths of lengths $|V|/2$, $|V|/2$ and $|V|$ to a central vertex. Next, make $|E|$ copies of $G$, labelled $G\_1, ..., G\_{|E|}$. For each $G\_i$, subdivide edge $i$ once, and to this new intermediate vertex, attach a dangling path $P\_i$ of length $|V|$. Finally, attach one new vertex to the second-to-last vertex in this path, so that the addition consisted of 2 external and $|V|-1$ internal edges. Finally, let $G'$ be the disjoint union of all $G\_i$.

Now, we can define $C$ as $\{G', H\}$.

Suppose that $G$ has a Hamiltonian Path. Then $H$ is a subgraph of some $G\_i$, as the long arm fits into some $P\_i$, the central vertex on the vertex added thru subdivision, and the other two arms make the path.

Suppoes that $H$ is a subgraph of $G'$. Well, $H$ is a simple component, and a little simple math shows that $G$ must have a Hamiltonian path.

OK, now we have that $H$ is a minor and subgraph of $G'$ iff $G$ has a Hamiltonian path. So consider the graph $G''$ obtained by subdividing an edge on $P\_1$ a bunch of times. As this edge is internal, $G'$ is not a subgraph of $G''$. And $H$ is a subgraph of $G''$ iff $G$ has a Hamiltonian path.

---

**NP to the NP**

**From my comment, why $G$ won't be too big:** Let's consider the smallest such $G$. Let $x$ be number of edges in graph of $C$ with most edges. No graph in C can consume all of a path of length $x+1$. As $G$ has as a minor some $H \in C$, we can look at the model of $H$ in $G$. Clearly, no reason to simply add edges or vertices to $H$. So we can get from $G$ to $H$ with just contraction. No path needs to be contracted more than $x+1$ times or we could have shortened it. This gives a reasonable size bound.

For $NP^{NP}$: given a graph $G$ with a minor in $C$, we need to ensure that for each graph $H$ in $C$, $H$ is not a subgraph $G$. One can imagine a TM which has a computation path for every each graph and way to split its vertices, which then queries an $NP$ oracle for each graph in $C$ to see if it's not a subgraph.

---

Any citations out there?

---

I'm also interested in a version where either all graphs of $C$ are subcubic or *condition 1* is for topological minors instead of normal ones.

**Tags:** cc.complexity-theory, reference-request, graph-theory, graph-minor

> **Comments:**
> **username_1**: If C is a finite set not dependent on the input, then this should be in P, right? You can check if the input has any graph in C as a minor in $O(n^3)$ time. And you can check if it has any graph in C as a subgraph in $O(n^k)$ time, where k is the size of the largest graph in C.  
> **username_0**: Robin: $C$ is the input.  
> **username_2**: How do you get the $P^{NP}$ upper bound?  
> **username_0**: First, need to show that if there is a $G$ then it's small enough. Let's consider the smallest such $G$. Let $x$ be number of edges in graph of $C$ with most edges. No graph in $C$ can consume all of a path of length $x+1$. As $G$ is a minor of some graph $H \in C$, we can look at the model of $G$ in $H$. Clearly, no reason to simply add edges or vertices to $H$. So we can get from $G$ to $H$ with just contraction. No path needs to be contracted more than $x+1$ times or we could have shortened it. This gives a reasonable size bound.  
> **username_0**: Next, we're asking if there is a graph of at most this size such that (1) it is a minor of some graph in $C$ (takes NP power), (2) it has no subgraph in $C$ (takes co-NP power). I can try to be more formal if this idea isn't enough.  
> **username_1**: @username_0: Oh, I see. I misinterpreted the question. Might be good to point that out more clearly so that others don't make a similar mistake. Also, for the benefit of future readers, it might be a good idea to incorporate all your comments into the question so that future readers don't need to read the comments.  
> **username_1**: Maybe also mention why the problem is NP-hard?  
> **username_0**: Good idea, updated.  
> **username_3**: I cannot understand your proof of membership to P^NP.  If we are given both C and G, then indeed we can decide whether G satisfies the condition or not by using two queries to NP, as you wrote (with minor corrections in wording).  But how does the algorithm work without being given G?  It looks to me that you are proving the membership to NP^NP.  
> **username_0**: Tsuyoshi, you are correct. More is needed to show $P^{NP}$, I'm updating my answer accordingly.  
> **username_1**: You mentioned that you're interested in the case where all the graphs in C are cubic. It seems like that case is easy. More generally, I think if C does not contain a path or subdivided claw, then such a graph $G$ must exist.  
> **username_0**: @Robin, sorry, I meant subcubic. Obviously, we need a graph with no internal edges. We can take the disjoint union of paths and subdivided claws, too.  
> **username_4**: I believe Robin's comment is correct.  An easier statement is that if graph in $C$ contains a cycle, $G$ must exist.  To see this, simply take a graph in $C$ and subdivide an edge until the largest cycle is larger than any cycle in any graph in $C$.  Robin's statement should follow similarly, except you need to split high-degree vertices into binary trees, if you know what I mean.  
> **username_0**: @AndrewD.King: only in cubic graphs, which aren't particularly interesting (I typoed and meant subcubic). If every graph in $C$ contains a cycle then one can subdivide all edges in one graph an absurd number of times and of course it has no subgraph in $C$. This holds if all graphs in $C$ have internal edges, in fact. This isn't necessarily the case in a set of subcubic graphs, though.  
> **username_3**: I also fail to follow the proof of NP-hardness.  In your reduction, I understand that if a graph G contains K as a minor, then it contains K as a subgraph.  This means that if there is any graph G that satisfies the condition, then G must contain H′ as a minor while avoiding both K and H′ as subgraph.  But how do you proceed from this?  
> **username_0**: @TsuyoshiIto, I updated my proof, does this make more sense now? Note that I changed around which variables meant what to more correspond with how I have previously written this proof.  
> **username_3**: Now I follow your proof, thanks.  I think that you can try to clean it up, in particular by explicitly saying that you are proving coNP-hardness (under many-one reducibility) instead of saying NP-hardness (under Turing reducibility).  The last paragraph of the proof will be easier to read if you avoid using “it” and if you separate the case where G has a Hamiltonian path and the case where G does not.  The graph called “it” is used only in the case where G does not have a Hamiltonian path, but it is unclear from the way you wrote.  
> **username_3**: (I realized that I still do not follow the construction of the graph called “it,” but I will not bug you to clarify it.)  
> **username_0**: @TsuyoshiIto, fixed "it" up a bit for you. $G''$ is just $G'$ with a subdivision where it doesn't affect $H$-subgraph-containment but ruins $G'$-subgraph-containment.  
> **username_5**: What does it mean for a graph to have internal and external edges?  
> **username_0**: Start at a degree-1 vertex and walk until you hit a degree 3 or higher vertex. This is a dangling path. All edges on it are external. All edges not on dangling paths are internal.  
> **username_6**: do you definitely mean _subgraphs_ and not _induced subgraphs_? there is misc research into the latter  
> **username_0**: I do mean just plain old _subgraphs_, but if you can characterize it with induced subgraphs, that's also interesting.  
> **username_6**: there seems to be a lot of work on the [_forbidden subgraph problem_](http://en.wikipedia.org/wiki/Forbidden_subgraph_problem) problem which seems closely related to yours. however, on quick glance seems like you might seriously be underestimating the complexity of the problem. the issue it seems is that graphs that exclude a list of finite subgraphs can be very large...? have you heard of universal graphs? does this ref relate to your problem-- [universal graphs with forbidden graphs and algebraic closure](http://arxiv.org/pdf/math/9809202.pdf)  
> **username_0**: username_6: my problem here is definitely in $NP^{NP}$, and probably complete for it. I've read extensively about the forbidden subgraph problem and closely related things. Note that our problem is much easier if $|C| = 1$ (in fact, it can be solved in linear time). I don't quite see a more direct connection between my problem and forbidden subgraphs.  That universal graphs paper doesn't mention minors, I'll read it over in closer detail later, though.  
> **username_6**: you say "G is a minor of some graph H in C". dont you mean "some graph H in C is a minor of G"? or "G has some minor graph H in C"?  
> **username_0**: Hi username_6, you are correct, I fixed some inaccuracies in my posting. Some of my early comments are uneditable and incorrect.  
> **username_6**: ok. also, admittedly, just not following your upper bound sketch. you seem to basically assert that if a graph has a minor, there is some size limit on how large the graph is wrt the minor (relative to paths in the graph or its minor or something). [maybe a newbie question here] but isnt it true that a graph can be arbitarily much larger than one of its minors?  
> **username_6**: reading the defn of [minor](http://en.wikipedia.org/wiki/Graph_minor), isnt every induced subgraph of a graph also a minor, because minors contract _zero_ or more edges of induced subgraphs? so the construction of rules 1,2 seems inconsistent; do you mean something else? ps here is a nice Phd thesis on [forbidding induced subgraphs](http://www.cs.mcgill.ca/~yzwols/thesis.pdf) by yori zwols, 2010  
> **username_0**: username_6: my rules aren't inconsistent because you can have minors that aren't subgraphs. Let $G$ be a graph, $M$ be the set of minors of $G$, $I$ be the set of induced subgraphs of $G$, and $S$ be the set of subgraphs of $G$. $I \subseteq S \subseteq M$. $G$ has no internal edges iff $S = M$. For an example, let $C = \{ K_4 \}$. Consider the graph with one edge in $K_4$ subdivided once. It has no $K_4$ subgraph but it does have a $K_4$ minor.  
> **username_0**: username_6: for my upper bound. Suppose $A$ has $B$ as a minor (using different letters from above to avoid confusion). Then you can apply a series of operations to $B$ to get a graph isomorphic to $A$. You can add a vertex, add an edge, or 'split' a vertex (opposite of contract). If you disallow adding vertices and edges, there are only so many vertices to split before any split is the same as subdivision. Since I'm looking for the smallest $G$, no reason to add edges or vertices. And no reason to perform too many subdivisions. I'll expand on this below.  
> **username_0**: Why shouldn't we add vertices or edges? Doing so strictly makes the set of subgraphs strictly larger. Why shouldn't we subdivide arbitrarily? After a while we'll create a path that nothing can span. After this point, no reason to go farther.  
> **username_6**: sounds like you are interested in what might be called "proper minors" that are minors but not subgraphs (maybe there is some other recognized term). is it equivalent to say that "none of the $C$ are subgraphs of $G$"? and, ?! there is nothing in the problem statement that says you're looking for the _smallest_ $G$. think you need some assertion in the form, "if G exists, it is not larger than [x] because [y]"... cant follow that in your current writeup, can anyone else?  
> **username_0**: username_6: you are correct in that we do not care about finding the smallest $G$, we just want to know whether one exists. All that my paragraph on the size of $G$ demonstrates is that if any $G$ exists, there is some graph satisfying conditions (1) and (2) of the problem statement of a polynomial size. That's all that's important, then the remainder of my $NP^{NP}$ sketch holds. Since we have nondeterminism (and copious amounts), we can guess $G$. But only if its size is reasonable. Thus, I argue that one of reasonable size exists.  
> **username_6**: dont think your reasoning makes sense. your writeup in the question is not fully fleshed out. not familiar with the theory enough to shoot off a quick counterexample, but how about this. from ch3 of zwols, a graph with no four-edge or five-edge path in the complement is conjectured (Erdos-Hajnal) to have exponentially large cliques. that can only happen if the graph itself is exponentially large. true?  
> **username_0**: What statement of mine in particular do you disagree with?  

---

## 0 answers

