13
$\begingroup$

Consider the following problem -

Given maximal planar graphs $G_1$ and $G_2$, find the graph $G$ with maximum number of edges such that there is a subgraph (not necessarily induced) in both $G_1$ and $G_2$ that is isomorphic to $G$.

Can this be done in polynomial time? If yes, then how?

It's known that if $G_1$ and $G_2$ are general graphs, then the problem is NP-complete (because $G_1$ could be a clique). It's also known that if $G_1$ and $G_2$ are trees, or bounded degree partial k-trees, then the problem can be solved in polynomial time. So what about the maximal planar case? Does anyone know this? Graph isomorphism on two maximal planar graphs is polynomial. Perhaps this helps somehow?

$\endgroup$
  • $\begingroup$ “Graph isomorphism on two maximal planar graphs is polynomial. Perhaps this helps somehow?” It is at least related (you probably already know it): existence of an efficient algorithm for deciding isomorphism is definitely a necessary condition for existence of an efficient algorithm for finding the largest common subgraph. $\endgroup$ – Tsuyoshi Ito Apr 15 '11 at 13:47
  • $\begingroup$ Yes, sure. And it's probably not sufficient. I am not too sure, but I think there are graph classes for which isomorphism is polynomial but finding the largest common subgraph is not? $\endgroup$ – Vinayak Pathak Apr 15 '11 at 21:35
  • $\begingroup$ It seems the problem is $NP$-complete. $G$ could be the largest common cycle and it is known that the Hamiltonian cycle problem is $NP$-complete on maximal planar graphs. math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W82a/tech298.pdf $\endgroup$ – Mohammad Al-Turkistany Apr 24 '11 at 12:02
5
$\begingroup$

It's NP-complete, via a modified version of the reduction Wigderson used to prove that Hamiltonicity of maximal planar graphs is NP-complete.

Careful examination of Wigderson's 1982 NP-completeness proof of hardness for Hamiltonian cycles in maximal planar graphs (http://www.math.ias.edu/avi/node/820) shows that the instances produced by his reduction have the property that there exists an edge $e$ such that either there exists a Hamiltonian cycle through $e$ or there does not exist any Hamiltonian cycle at all. For instance, $e$ can be chosen to be one of the edges in one of Wigderson's $M$-gadgets.

Let $G$ be a hard instance constructed in this way, and embed $G$ so that the edge $e$ belongs to the outer triangle of the embedding. Connect many copies of this embedded graph so that their $e$-edges form a cycle, and make the result maximal planar again by adding two more vertices, one on each side of this cycle, connected to all the exposed vertices of the copies of $G$. Let the number of copies be $c$, and call the resulting graph $H$. Let $n$ be the number of vertices in $G$.

Our hard instance for the largest common subgraph will be the pair $(H,B)$ where $B$ is a bipyramid with the same number of vertices as $H$. Thus, an optimal common subgraph will have to pair all of the vertices. If we make $c$ large enough, the subgraph will necessarily pair the apexes of the bipyramid with the two added vertices in $H$, because their degrees ($c$ and $2c$) will be sufficiently higher than every other vertex in $H$, so that adding these degrees to the solution size will make up for any disruption elsewhere caused by this pairing.

If $G$ is Hamiltonian, then the common subgraph formed by matching the Hamiltonian cycle (minus $e$) in the copies of $G$ to the equator of the bipyramid will have $c(n+2)$ edges, $c(n-1)$ for the equator and $3c$ for the apexes. If $G$ is not Hamiltonian, then (for large enough choices of $c$ that the optimal solution pairs the apexes correctly) any common subgraph will have fewer edges: still $3c$ at the apexes but fewer than $c(n-1)$ elsewhere. So testing whether the common subgraph of $H$ and $B$ has at least $c(n+2)$ edges is NP-complete.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.