Vi presenterar nya algoritmer för att hitta inducerade fyranode subgraphs i en given graf, som körs i tiden ungefär som att upptäcka en klick på tre noder (dvs. en triangel). • De mest kända algoritmer för triangelfynd i en nnode graf ta tid O (n), där  på < 2.373 är matris multiplikation exponenten. Vi ger en generell randomiserad teknik för att hitta någon inducerad fyra-node subgraph, med undantag för klick eller oberoende inställd på 4 noder, iñ O (n) tid med hög sannolikhet. Algoritmen kan avrandomiseras i vissa fall: vi visar hur man detekterar en diamant (eller dess komplement) i deterministisk Õ(n) tid. Vårt tillvägagångssätt förbättras avsevärt när det gäller tidigare arbete. Till exempel, den tidigare bästa algoritmen för C 4 detektion kördes i O(n 3.3 ) tid, och för diamant detektion i O(n 3 ) tid. • För glesa grafer med m-kanter körs den mest kända algoritmen för att hitta triangeln i O(m 2 och/(+1) ) ≤ O(m 1,41 ) tid. Vi ger en randomiserad Õ(m 2 och/(+1) ) tid algoritm (analog till den mest kända för triangelfynd) för att hitta någon inducerad fyranode subgraph andra än C 4, K 4 och deras komplement. När det gäller diamantdetektion utformar vi också en deterministisk Õ (m 2 och/( och +1) ) tidsalgoritm. För C 4 eller dess komplement, ger vi randomiserade O (m (40-1)/(2-+1) ) ≤ O (m 1,48 ) tid att hitta algoritmer. Dessa algoritmer förbättras avsevärt på tidigare arbete. Till exempel, den bästa algoritmen för diamant detektion kördes i O (m 1.5 ) tid.
Williams, Wang, Williams, och Yu REF gav O (n) tid algoritmer för den inducerade subgraph isomorfism problem för fyra vertex mönster grafer, utom I 4 och K 4.
Finding Four-Node Subgraphs in Triangle Time
{'venue': 'SODA', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}