6
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Robin Kothari Sep 5 '12 at 22:47
  • 1
    $\begingroup$ Robin: $C$ is the input. $\endgroup$ – Eli Sep 6 '12 at 0:04
  • 2
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Sep 6 '12 at 12:21
  • 3
    $\begingroup$ 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. $\endgroup$ – Robin Kothari Sep 6 '12 at 20:45
  • 2
    $\begingroup$ (I realized that I still do not follow the construction of the graph called “it,” but I will not bug you to clarify it.) $\endgroup$ – Tsuyoshi Ito Sep 7 '12 at 21:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.