A convex relaxation bound for subgraph isomorphism
type: Item
instance of: scholarly article
title: A convex relaxation bound for subgraph isomorphism
zbMATH Open document ID: 1236.05133
DOI: 10.1155/2012/908356
author: Christian Schellewald
published in: International Journal of Combinatorics
publication date: 2012-03-08T00:00:00Z
review text: Summary: 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.
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 6013086
zbMATH Keywords: combinatorial optimization problem, Error-correcting graph matching
cites work: Benchmarks for Optimization Software
cites work: An Algorithm for Subgraph Isomorphism
cites work: Subgraph isomorphism, matching relational structures and maximal cliques
cites work: Subgraph Isomorphism in Planar Graphs and Related Problems
cites work: A distance measure between attributed relational graphs for pattern recognition
cites work: Handbook of semidefinite programming. Theory, algorithms, and applications
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Q4449678
cites work: Graph-Based Representations in Pattern Recognition
cites work: Q3145799
cites work: Q4198056
cites work: Quadratic programming with one negative eigenvalue is NP-hard
cites work: CSDP, A C library for semidefinite programming
cites work: Q4464638
cites work: Q3812479
cites work: Q4382667
cites work: An independent benchmarking of SDP and SOCP solvers
cites work: An Interior-Point Method for Semidefinite Programming
cites work: CSDP 2.3 user's guide
cites work: Exact bounds on the order of the maximum clique of a graph.
cites work: Maxima for Graphs and a New Proof of a Theorem of Turán
cites work: Q4218487
describes a project that uses: Benchmarks for Optimization Software
describes a project that uses: PENNON
describes a project that uses: CSDP
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2012/908356
OpenAlex ID: W1966242563
Wikidata QID: Q58703379
description: scientific article; zbMATH DE number 6013086