Finding four-node subgraphs in triangle time

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 ω