Problemet med at finde en isomorf subgraf

Problemet med at finde en isomorf undergraf er et beregningsproblem, hvor inputtet er to grafer G og H , og det er nødvendigt at bestemme, om G indeholder en undergraf , der er isomorf i forhold til grafen H . Problemet med at finde en isomorf subgraf er en generalisering af både det maksimale klikproblem og problemet med at kontrollere om grafen indeholder en Hamiltonsk cyklus og derfor er NP-komplet [1] . Problemer med at finde en isomorf subgraf med nogle slags subgrafer kan dog løses i polynomisk tid [2] [3] .

Nogle gange bruges navnet subgraph mapping for det samme problem. Dette navn understreger at finde sådanne undergrafer, ikke kun opløselighed.

Problemet med løselighed og beregningsmæssig kompleksitet

For at bevise, at problemet med at finde en isomorf subgraf er NP-komplet, skal det formuleres som et løselighedsproblem . Indgangen til løselighedsproblemet er afsnit G og H . Svaret på problemet er positivt, hvis H er isomorf for en eller anden undergraf af G , og negativ ellers.

Formel opgave:

Lad , være to grafer. Findes der en undergraf , sådan at ? De der. findes der en kortlægning sådan ?

Beviset for NP-fuldstændighed af problemet med at finde en isomorf subgraf er simpelt og bygger på reduktionen til dette problem af klikeproblemet , et NP-komplet løselighedsproblem, hvor input er en enkelt graf G og et tal k , og spørgsmålet er, om grafen G indeholder en komplet undergraf med k toppunkter. For at reducere dette problem til problemet med at finde en isomorf subgraf tager vi blot den komplette graf K k som grafen H. Så er svaret for problemet med at finde en isomorf subgraf med inputgrafer G og H lig med svaret for klikeproblemet for graf G og nummer k . Da klikeproblemet er NP-komplet, viser en sådan polynomiel reduktionsevne , at problemet med at finde en isomorf subgraf også er NP-komplet [4] .

En alternativ reduktion fra det Hamiltonske cyklusproblem kortlægger grafen G , som er testet for Hamiltonianitet, til et par grafer G og H , hvor H er en cyklus, der har samme antal hjørner som G . Da det Hamiltonske cyklusproblem er NP-komplet selv for plane grafer , viser dette, at problemet med at finde en isomorf subgraf forbliver NP-komplet selv for det plane tilfælde [5] .

Isomorphism subgraph problem er en generalisering af grafen isomorphism problem der spørger om en graf G er isomorf til en graf H - svaret på graf isomorphism problem er "ja", hvis og kun hvis graferne G og H har det samme antal hjørner og kanter, og problemet med at finde en isomorf subgraf for graferne G og H giver "ja". Status for grafisomorfiproblemet fra kompleksitetsteoriens synspunkt forbliver dog åben.

Gröger [6] viste, at hvis Aandera-Karp-Rosenberg-formodningen om kompleksiteten af ​​at forespørge monotone egenskaber af en graf holder, så har ethvert problem med at finde en isomorf subgraf forespørgselskompleksitet Ω( n 3/2 ). Det vil sige, at løsningen af ​​problemet med at finde en isomorf subgraf kræver kontrol af eksistensen eller fraværet i input Ω( n 3/2 ) af forskellige kanter af grafen [7] .

Algoritmer

Ullman [8] beskrev en rekursiv tilbagesporingsprocedure til at løse problemet med at finde en isomorf subgraf. Selvom køretiden for denne algoritme generelt er eksponentiel, kører den i polynomiel tid for enhver fast H (det vil sige, at køretiden er afgrænset af et polynomium afhængigt af valget af H ). Hvis G er en plan graf (eller mere generelt en graf med afgrænset forlængelse ), og H er fast, kan løsningstiden for det isomorfe subgrafproblem reduceres til lineær tid [2] [3] .

Ullman [9] opdaterede væsentligt algoritmen fra 1976-avisen.

Ansøgninger

Det isomorfe subgrafsøgningsproblem er blevet anvendt inden for kemoinformatik til at søge efter ligheden mellem kemiske forbindelser ved deres strukturformler. Udtrykket understruktursøgning [8] bruges ofte i dette område . Strukturen af ​​en forespørgsel defineres ofte grafisk ved hjælp af en struktureditor . SMILES- baserede databaser definerer typisk forespørgsler ved hjælp af SMARTS , en udvidelse af SMILES .

De nært beslægtede problemer med at tælle antallet af isomorfe kopier af en graf H i en større graf G bruges til mønsterdetektion i databaser [10] , i protein-protein interaktionsbioinformatik [11] og i eksponentielle tilfældige grafmetoder til den matematiske modellering af sociale netværk [12] .

Olrich, Ebeling, Gieting og Sater [13] beskrev anvendelsen af ​​det isomorfe subgrafsøgningsproblem i computerstøttet design af elektroniske kredsløb . Undergraftilpasningsopgaven er også et undertrin i graftransformation (kræver den længste udførelsestid) og leveres derfor af graftransformationsarbejdsbordet.

Opgaven er også af interesse inden for kunstig intelligens , hvor den anses for at være en del af en gruppe af grafmønstermatchende opgaver . Også overvejet i dette område er en udvidelse af problemet med at finde en isomorf graf, kendt som grafanalyse [14] .

Noter

  1. ↑ I Cooks originale papir ( Cook 1971 ), der indeholder et bevis for Cook-Levin-sætningen , blev det allerede vist, at problemet med at finde en isomorf subgraf er NP-komplet ved at reducere fra 3-SAT- problemet ved hjælp af kliker
  2. ↑ 1 2 Eppstein, 1999 , s. 1-27.
  3. ↑ 1 2 Nešetřil, Ossona de Mendez, 2012 , s. 400-401.
  4. ↑ Wegener, 2005 , s. 81.
  5. ↑ de la Higuera, Janodet, Samuel, Damiand, Solnon, 2013 , s. 76-99.
  6. ↑ Gröger, 1992 , s. 119-127.
  7. ↑ Her er Ω Omega stor .
  8. ↑ 1 2 Ullmann, 1976 , s. 31-42.
  9. ↑ Ullmann, 2010 .
  10. ↑ Kuramochi, Karypis, 2001 , s. 313.
  11. ↑ Pržulj, Corneil, Jurisica, 2006 , s. 974-980.
  12. ↑ Snijders, Pattison, Robins, Handcock, 2006 , s. 99-153.
  13. ↑ Ohlrich, Ebeling, Ginting, Sather, 1993 , s. 31-37.
  14. ↑ http://www.aaai.org/Papers/Symposia/Fall/2006/FS-06-02/FS06-02-007.pdf Arkiveret 29. august 2017 på Wayback Machine ; udvidet version på https://e-reports-ext.llnl.gov/pdf/332302.pdf Arkiveret 31. januar 2017 på Wayback Machine

Litteratur