För en mönstergraf H på k noder, anser vi problemen med att hitta och räkna antalet (inte nödvändigtvis inducerade) kopior av H i en given stor graf G på n noder, samt att hitta minsta vikt kopior i både nod viktade och kantviktade grafer. Våra resultat inkluderar: • Antalet kopior av ett H med en oberoende uppsättning storlek s kan beräknas exakt i O * (2 s n k‐s+3 ) tid. En minsta viktkopia av ett sådant H (med godtyckliga reella vikter på noder och kanter) finns i O(4 s+o(s) n k‐s+3 ) tid. (O * notation utelämnar poly(k) faktorer.) Dessa algoritmer är beroende av snabba algoritmer för beräkning av permanent för en k × n-matris, över ringar och halvringar. • Antalet kopior av alla H som har minsta (eller högsta) nodvikt (med godtyckliga verkliga vikter på noder) kan hittas i O(n -k/3 + n 2k/3+o(1) ) tid, där - < 2.4 är matrisen multiplikation exponenten och k är delbart med 3. Liknande resultat håller för andra värden av k. Dessutom, antalet kopior som har exakt en föreskriven vikt kan hittas inom denna tid. Dessa algoritmer utökar tekniken för Czumaj och Lingas (SODA 2007) och ger en ny (algoritmisk) tillämpning av multipartskommunikation komplexitet. • Att hitta en kantviktad vikttriangel exakt 0 i allmänna grafer kräver tid för alla ε > 0, om inte 3SUM problem på N nummer kan lösas i O(N 2−ε ) tid. Detta tyder på att det kantviktade problemet är mycket svårare än dess nodviktade version.
Vassilevska och Williams REF studerade problemet med att hitta och räkna enskilda icke-inducerade subgrafer.
Finding, minimizing, and counting weighted subgraphs
{'venue': "STOC '09", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}