Clever Geek Handbook
📜 ⬆️ ⬇️

The problem of finding an isomorphic subgraph

The problem of finding an isomorphic subgraph is a computational problem in which two graphs G and H are the input and it is necessary to determine if G does not contain a subgraph isomorphic to the graph H. The search for an isomorphic subgraph is a generalization of both the maximum clique problem and the problem of checking whether the graph contains a Hamiltonian cycle and is therefore NP-complete [1] . However, the problem of finding an isomorphic subgraph with some types of subgraphs can be solved in polynomial time [2] [3] .

Sometimes the name subgraph mapping is also used for the same task. This name focuses on the search for such subgraphs, and not just on solvability.

Solvability Problem and Computational Complexity

To prove that the problem of finding an isomorphic subgraph is NP-complete, it must be formulated as a solvability problem . The input to the solvability problem is a pair of graphs G and H. The answer to the problem is positive if H is isomorphic to some subgraph of G and negative otherwise.

Formal Assignment:

Let beG=(V,E) {\ displaystyle G = (V, E)}   ,H=(V′,E′) {\ displaystyle H = (V ^ {\ prime}, E ^ {\ prime})}   - two graphs. Is there a subgraphG0=(V0,E0):V0⊆V,E0⊆E∩(V0×V0) {\ displaystyle G_ {0} = (V_ {0}, E_ {0}): V_ {0} \ subseteq V, E_ {0} \ subseteq E \ cap (V_ {0} \ times V_ {0})}   such thatG0≅H {\ displaystyle G_ {0} \ cong H}   ? Those. is there a mappingf:V0→V′ {\ displaystyle f \ colon V_ {0} \ rightarrow V ^ {\ prime}}   such that(vone,v2)∈E0⇔(f(vone),f(v2))∈E′ {\ displaystyle (v_ {1}, v_ {2}) \ in E_ {0} \ Leftrightarrow (f (v_ {1}), f (v_ {2})) \ in E ^ {\ prime}}   ?

The proof of the NP-completeness of the search problem for an isomorphic subgraph is simple and based on reducing the clique problem to this problem, the NP-complete solvability problem, in which one graph G and the number k serve as an input, and the question is: does the graph G contain a complete subgraph with k vertices. To reduce this problem to the problem of finding an isomorphic subgraph, we simply take the complete graph K k as the graph H. Then the answer for the problem of finding an isomorphic subgraph with input graphs G and H is equal to the answer for the clique problem for graph G and the number k . Since the clique problem is NP-complete, such a shows that the problem of finding an isomorphic subgraph is also NP-complete [4] .

An alternative reduction from the Hamiltonian cycle problem maps a graph G , which is checked for Hamiltonianity, to a pair of graphs G and H , where H is a cycle having the same number of vertices as G. Since the Hamiltonian cycle problem is NP-complete even for planar graphs , this shows that the search for an isomorphic subgraph remains NP-complete even for the planar case [5] .

The search problem for an isomorphic subgraph is a generalization , which asks if the graph G is isomorphic to the graph H — the answer for the yes graph isomorphism problem if and only if the graphs G and H have the same number of vertices and edges and the problem of finding an isomorphic subgraph for graphs G and H gives "yes." However, the status of the graph isomorphism problem from the point of view of complexity theory remains open.

Gröger [6] showed that if the about the monotone properties of a graph is fulfilled, then any problem of finding an isomorphic subgraph has the query complexity Ω ( n 3/2 ). That is, the solution of the problem of searching for an isomorphic subgraph requires checking the existence or absence of different edges of the graph in the input Ω ( n 3/2 ) [7] .

Algorithms

Ullman [8] described a recursive return procedure for solving the problem of finding an isomorphic subgraph. Although the running time of this algorithm is generally exponential, it works in polynomial time for any fixed H (that is, the running time is limited by a polynomial depending on the choice of H ). If G is a planar graph (or, more generally, a ), and H is fixed, the time to solve the search problem for an isomorphic subgraph can be reduced to linear time [2] [3] .

Ullman [9] significantly updated the algorithm from an article in 1976.

Applications

The task of searching for an isomorphic subgraph was applied in the field of chemoinformatics to search for the similarity of chemical compounds by their structural formulas. Often in this area the term substructural search is used [8] . The structure of a query is often determined graphically using a structural editor . SMILES- based databases typically define queries using , an extension to SMILES .

The closely related problems of counting the number of isomorphic copies of graph H in the larger column G are used to detect the pattern in databases [10] , in protein-protein interactions bioinformatics [11], and in exponential random graph methods for mathematical modeling of social networks [12] .

Olrich, Ebeling, Giting, and Sater [13] described the application of the problem of searching for an isomorphic subgraph in a computer-aided design system for electronic circuits . The task of comparing a subgraph is also a substep in the (requiring the greatest execution time), and therefore is provided by the graph transformation tools.

The task is also of interest in the field of artificial intelligence , where it is considered part of the group of tasks of comparison with the sample in graphs. Also considered in this area is the extension of the search problem for an isomorphic graph, known as [14] .

Notes

  1. ↑ In the original Cook article ( Cook 1971 ), containing the proof of the Cook - Levin theorem , it was already shown that the problem of finding an isomorphic subgraph is NP-complete by reducing from the 3-SAT problem using clicks
  2. ↑ 1 2 Eppstein, 1999 , p. 1–27.
  3. ↑ 1 2 Nešetřil, Ossona de Mendez, 2012 , p. 400-401.
  4. ↑ Wegener, 2005 , p. 81.
  5. ↑ de la Higuera, Janodet, Samuel, Damiand, Solnon, 2013 , p. 76–99.
  6. ↑ Gröger, 1992 , p. 119-127.
  7. ↑ Here, Ω is Omega large .
  8. ↑ 1 2 Ullmann, 1976 , p. 31–42.
  9. ↑ Ullmann, 2010 .
  10. ↑ Kuramochi, Karypis, 2001 , p. 313.
  11. ↑ Pržulj, Corneil, Jurisica, 2006 , p. 974–980.
  12. ↑ Snijders, Pattison, Robins, Handcock, 2006 , p. 99-153.
  13. ↑ Ohlrich, Ebeling, Ginting, Sather, 1993 , p. 31–37.
  14. ↑ http://www.aaai.org/Papers/Symposia/Fall/2006/FS-06-02/FS06-02-007.pdf ; expanded version at https://e-reports-ext.llnl.gov/pdf/332302.pdf

Literature

  • SA Cook. Proc. 3rd ACM Symposium on Theory of Computing . - 1971. - DOI : 10.1145 / 800157.805047 .
  • Colin de la Higuera, Jean-Christophe Janodet, Émilie Samuel, Guillaume Damiand, Christine Solnon. Polynomial algorithms for open plane graph and subgraph isomorphisms // Theoretical Computer Science. - 2013 .-- T. 498 . - DOI : 10.1016 / j.tcs.2013.05.05.026 . Since the mid 70's it is known that the problem of finding an isomorphic subgraph is solvable in polynomial time for planar graphs. However, it was noted that the problem of searching for a subisomorphism remains NP-complete, in particular, since the problem of the Hamiltonian cycle is NP-complete for planar graphs.
  • Ingo Wegener. Complexity Theory: Exploring the Limits of Efficient Algorithms . - Springer, 2005 .-- ISBN 9783540210450 .
  • David Eppstein Subgraph isomorphism in planar graphs and related problems // Journal of Graph Algorithms and Applications . - 1999. - T. 3 , no. 3 . - DOI : 10.7155 / jgaa.00014 . - arXiv : cs.DS / 9911003 .
  • Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness . - WH Freeman, 1979. - ISBN 0-7167-1045-5 . . A1.4: GT48, p. 202.
  • Hans Dietmar Gröger. On the randomized complexity of monotone graph properties // Acta Cybernetica. - 1992. - T. 10 , no. 3 . .
  • Michihiro Kuramochi, George Karypis. 1st IEEE International Conference on Data Mining. - 2001. - ISBN 0-7695-1119-8 . - DOI : 10.1109 / ICDM.2001.989534 . .
  • Miles Ohlrich, Carl Ebeling, Eka Ginting, Lisa Sather. Proceedings of the 30th international Design Automation Conference. - 1993. - ISBN 0-89791-577-1 . - DOI : 10.1145 / 157485.164556 .
  • Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms. - Springer, 2012.- T. 28. - (Algorithms and Combinatorics). - ISBN 978-3-642-27874-7 . - DOI : 10.1007 / 978-3-642-27875-4 . .
  • N. Pržulj, DG Corneil, I. Jurisica. Efficient estimation of graphlet frequency distributions in protein – protein interaction networks // Bioinformatics. - 2006. - T. 22 , no. 8 . - DOI : 10.1093 / bioinformatics / btl030 . - PMID 16452112 .
  • TAB Snijders, PE Pattison, G. Robins, MS Handcock. New specifications for exponential random graph models // Sociological Methodology. - 2006. - T. 36 , no. 1 . - DOI : 10.1111 / j.1467-9531.2006.00176.x .
  • Julian R. Ullmann. An algorithm for subgraph isomorphism // Journal of the ACM . - 1976. - T. 23 , no. 1 . - DOI : 10.1145 / 321921.321925 .
  • Hasan Jamil. 26th ACM Symposium on Applied Computing. - 2011. - S. 1058-1063. .
  • Julian R. Ullmann. Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism // Journal of Experimental Algorithmics . - 2010 .-- T. 15 . - DOI : 10.1145 / 1671970.1921702 .
Source - https://ru.wikipedia.org/w/index.php?title= Task to search for isomorphic subgraph&oldid = 98650769


More articles:

  • Belozerskaya street (Moscow)
  • Stockholm Marathon
  • Snare Drum
  • Miron Kyzic
  • Efendieva, Adavie
  • 1985 Avoriaz Film Festival
  • Novocherkassk Meat Processing Plant
  • Car / Listings / Ferrari Car List
  • Studitsky, Fedor Dmitrievich
  • Ryazhskaya, Olga G.

All articles

Clever Geek | 2019