Finding four-node subgraphs in triangle time

Virginia Vassilevska Williams, Joshua R. Wang, Ryan Williams, Huacheng Yu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

43 Scopus citations

Abstract

We present new algorithms for finding induced four-node subgraphs in a given graph, which run in time roughly that of detecting a clique on three nodes (i.e., a triangle). The best known algorithms for triangle finding in an n-node graph take O (nω) time, where ω< 2.373 is the matrix multiplication exponent. We give a general randomized technique for finding any induced four-node subgraph, except for the clique or independent set on 4 nodes, in O (nω) time with high probability. The algorithm can be derandomized in some cases: we show how todetect a diamond (or its complement) in deterministic O (nω) time. Our approach substantially improves on prior work. For instance, the previous best algorithm for C4 detection ran in O (n3.3) time, and for diamond detection in O (n3) time. For sparse graphs with m edges, the best known triangle finding algorithm runs in O (m2ω/ ( ω+1)) ≤ O (m1.14) time. We give a randomized O (m2ω/ ( ω+1)) time algorithm (analogous to the best known for triangle finding) for finding any induced four-node subgraph other than C4, K4 and their complements. In the case of diamond detection, we also design a deterministic O (m2ω/ ( ω+1)) time algorithm. For C4 or its complement, we give randomized O (m(4ω-1)/ (2ω+1))≥O (m1.48)tjme findjng algorithms. These algorithms substantially improve on prior work. For instance, the best algorithm for diamond detection ran in 0 (m1.5) time.

Original languageEnglish (US)
Title of host publicationProceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015
PublisherAssociation for Computing Machinery
Pages1671-1680
Number of pages10
EditionJanuary
ISBN (Electronic)9781611973747
DOIs
StatePublished - 2015
Externally publishedYes
Event26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 - San Diego, United States
Duration: Jan 4 2015Jan 6 2015

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
NumberJanuary
Volume2015-January

Other

Other26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015
Country/TerritoryUnited States
CitySan Diego
Period1/4/151/6/15

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Finding four-node subgraphs in triangle time'. Together they form a unique fingerprint.

Cite this