International Journal of Combinatorics
Volume 2012 (2012), Article ID 908356, 18 pages
Research Article

A Convex Relaxation Bound for Subgraph Isomorphism

Independent Research, 7052 Trondheim, Tyholtveien 68, Norway

Received 31 August 2011; Accepted 27 December 2011

Academic Editor: Liying Kang

Copyright © 2012 Christian Schellewald. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


In this work a convex relaxation of a subgraph isomorphism problem is proposed, which leads to a new lower bound that can provide a proof that a subgraph isomorphism between two graphs can not be found. The bound is based on a semidefinite programming relaxation of a combinatorial optimisation formulation for subgraph isomorphism and is explained in detail. We consider subgraph isomorphism problem instances of simple graphs which means that only the structural information of the two graphs is exploited and other information that might be available (e.g., node positions) is ignored. The bound is based on the fact that a subgraph isomorphism always leads to zero as lowest possible optimal objective value in the combinatorial problem formulation. Therefore, for problem instances with a lower bound that is larger than zero this represents a proof that a subgraph isomorphism can not exist. But note that conversely, a negative lower bound does not imply that a subgraph isomorphism must be present and only indicates that a subgraph isomorphism can not be excluded. In addition, the relation of our approach and the reformulation of the largest common subgraph problem into a maximum clique problem is discussed.