%0 Journal Article
%T A Convex Relaxation Bound for Subgraph Isomorphism
%A Christian Schellewald
%J International Journal of Combinatorics
%D 2012
%I Hindawi Publishing Corporation
%R 10.1155/2012/908356
%X 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. 1. Introduction The subgraph isomorphism problem is a well-known combinatorial optimization problem and often involves the problem of finding the appropriate matching too. It is also of particular interest in computer vision where it can be exploited to recognise objects. For example, if an object in an image is represented by a graph, the object could be identified as subgraph within a possibly larger scene graph. Several approaches have been proposed to tackle the subgraph isomorphism problem and we refer to a few [1¨C4] and their references therein. Error-correcting graph matching [5]¡ªalso known as error-tolerant graph matching¡ªis a general approach to calculate an assignment between the nodes of two graphs. It is based on the minimisation of graph edit costs which result from some predefined edit operations when one graph is turned exactly into the other. Commonly introduced graph edit operations are deletion, insertion, and substitution of nodes and edges. Each graph-edit operation has a cost assigned to it which is application dependent. The minimal graph edit cost defines the so-called edit distance between two graphs. The idea to define such a distance for graph matching goes back to Sanfeliu and Fu [6] in 1983. Before that, the edit distance was mainly used for string matching. Several approaches for error correcting graph matching have been
%U http://www.hindawi.com/journals/ijcom/2012/908356/