We initiate the study of combinatorial algorithms for Triangle Detection in H-free graphs. The goal is to decide if a graph that forbids a fixed pattern H as a subgraph contains a triangle, using only "combinatorial" methods that notably exclude fast matrix multiplication. Our work aims to classify which patterns admit a subcubic speedup, working towards a dichotomy theorem.
On the lower bound side, we show that if H is not 3-colorable or contains more than one triangle, the complexity of the problem remains unchanged, and no combinatorial speedup is likely possible. Conversely, we hypothesize that all remaining patterns admit a combinatorial speedup, and we provide a strongly subcubic algorithm for a rich class of "embeddable patterns" which are characterized by admitting a special type of 3-coloring. Our results confirm the dichotomy hypothesis for all patterns of size up to 8.
Finally, we extend this main result by proving that our dichotomy hypothesis is equivalent to its counterpart in the much broader setting of induced H-free graphs — a scenario that a priori seems significantly more challenging. The main ingredient in the proof is a reduction from the induced H-free case to the non-induced H'-free case, where H' preserves the structural properties of H that are relevant for the dichotomy, namely 3-colorability and triangle count. A key technical ingredient is a self-reduction to Unique Triangle Detection that preserves the induced H-freeness property, via a new color coding-like reduction.
Joint work with Amir Abboud and Ron Safier.