Graph Isomorphism Task

From GM-RKB
(Redirected from Subgraph Matching)
Jump to navigation Jump to search

A Graph Isomorphism Task is an Exact Graph Matching Task that requires the production of a Graph Isomorphism Function between two Graphs, if one exists.

References

2015

  • (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem#Decision_problem_and_computational_complexity Retrieved:2015-11-16.
    • To prove subgraph isomorphism is NP-complete, it must be formulated as a decision problem. The input to the decision problem is a pair of graphs G and H. The answer to the problem is positive if H is isomorphic to a subgraph of G, and negative otherwise.

      Formal question:

      Let [math]\displaystyle{ G=(V,E) }[/math] , [math]\displaystyle{ H=(V^\prime,E^\prime) }[/math] be graphs. Is there a subgraph [math]\displaystyle{ G_0=(V_0,E_0): V_0\subseteq V, E_0\subseteq E\cap(V_0\times V_0) }[/math] such that [math]\displaystyle{ G_0\cong H }[/math] ? I.e., does there exist an [math]\displaystyle{ f\colon V_0\rightarrow V^\prime }[/math] such that [math]\displaystyle{ (v_1,v_2)\in E_0\Leftrightarrow (f(v_1),f(v_2))\in E^\prime }[/math] ?

      The proof of subgraph isomorphism being NP-complete is simple and based on reduction of the clique problem, an NP-complete decision problem in which the input is a single graph G and a number k, and the question is whether G contains a complete subgraph with k vertices. To translate this to a subgraph isomorphism problem, simply let H be the complete graph Kk; then the answer to the subgraph isomorphism problem for G and H is equal to the answer to the clique problem for G and k. Since the clique problem is NP-complete, this polynomial-time many-one reduction shows that subgraph isomorphism is also NP-complete. An alternative reduction from the Hamiltonian cycle problem translates a graph G which is to be tested for Hamiltonicity into the pair of graphs G and H, where H is a cycle having the same number of vertices as G. Because the Hamiltonian cycle problem is NP-complete even for planar graphs, this shows that subgraph isomorphism remains NP-complete even in the planar case. Subgraph isomorphism is a generalization of the graph isomorphism problem, which asks whether G is isomorphic to H: the answer to the graph isomorphism problem is true if and only if G and H both have the same numbers of vertices and edges and the subgraph isomorphism problem for G and H is true. However the complexity-theoretic status of graph isomorphism remains an open question. In the context of the Aanderaa–Karp–Rosenberg conjecture on the query complexity of monotone graph properties, showed that any subgraph isomorphism problem has query complexity Ω(n3/2); that is, solving the subgraph isomorphism requires an algorithm to check the presence or absence in the input of Ω(n3/2) different edges in the graph. [1]

2010

  • (Wikipedia, 2010) ⇒ http://en.wikipedia.org/wiki/Subgraph_matching
    • In complexity theory, Subgraph-Isomorphism is a decision problem that is known to be NP-complete. The formal description of the decision problem is as follows.
      • Subgraph-Isomorphism(G1, G2)
      • Input: Two graphs G1 and G2.
      • Question: Is G1 isomorphic to a subgraph of G2?
    • Sometimes the name subgraph matching is also used for the same problem. This name puts emphasis on finding such a subgraph as opposed to the bare decision problem.
    • The proof of subgraph isomorphism being NP-complete is simple and based on reduction of the clique problem. If subgraph isomorphism were polynomial, you could use it to solve the clique problem in polynomial time. Let n be the number of edges in G: you can then run the subgraph isomorphism n-2 times (with G1 being a clique of size 3 to [math]\displaystyle{ n }[/math], and G2 being G) to find the largest clique in G.
    • Subgraph isomorphism is a generalization of the potentially easier graph isomorphism problem; if the graph isomorphism problem is NP-complete, the polynomial hierarchy collapses, so it is suspected not to be.

2009

2008

  • (Zampelli, 2008) ⇒ Stéphane Zampelli. (2008). “A Constraint Programming Approach to Subgraph Isomorphism." PhD Thesis, Ecole polytechnique de Louvain, June 2008.
    • ABSTRACT: This thesis proposes an expressive yet efficient declarative framework for graph matching in constraint programming (CP), and focuses on efficient algorithms to solve the subgraph isomorphism problem. The framework is based on graph and map variables, and specific graph morphism constraints. This allows to model and solve various graph matching problems, avoiding the tedious development of dedicated and specific algorithms. A specialized filtering algorithm is proposed for the subgraph isomorphism problem, which uses the semantic of the problem as well as the global structure of the two input graphs. It is shown that it is the state-of-the-art filtering algorithm, compared to dedicated algorithms and other CP approaches. Various search techniques from CP are also extended to the subgraph isomorphism problem. An automatic detection and exploitation of symmetries for the subgraph isomorphism problem is proposed, together with a decomposition approach of the search. The significance of this thesis lies in the fact that, even though the framework is expressive, CP can be considered as the state-of-the-art for subgraph isomorphism, outperforming the dedicated known algorithms on current benchmarks.
    • QUOTE: Subgraph Matching: A graph is a set of points where two points are joined by a line if they are related. Graphs can model, for example, the representation of the relationships inside a community where points are persons, and there is a line between two persons if they know each other. Subgraph matching is the identification of a subgraph inside a target graph that is exactly the same as a given graph. For example, one may want to extract a subgraph of an initial community graph that is exactly the same as a given graph of interest, identifying subgroups of people that share exactly the same structural relationship than another given group.

1976

  1. ↑ Here Ω invokes Big Omega notation.
Retrieved from "http://www.gabormelli.com/RKB/index.php?title=Graph_Isomorphism_Task&oldid=821884"