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:
- $G$ has a minor in $C$
- $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.
