A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection
Shyan Akmal (Max Planck Institute for Informatics)
Monday, November 3rd 2025, 2-3pm
Abstract:
One of the most basic questions about detecting patterns in data is the Induced Subgraph Detection problem. Here we are given a small pattern graph and a large host graph, and are tasked with determining if the host contains the pattern as an induced subgraph. A dream goal of fine-grained complexity and graph algorithms is to fully classify those patterns for which Induced Subgraph Detection is easy to solve, and those for which it becomes difficult. In this talk, we present some recent, surprising progress on this classification question, centered around a particularly suspicious pattern known as the 4-cycle.