Witness-Sensitive Detection of Induced Diamonds

Keren Censor-Hillel, Tomer Even, Virginia Vasillevska Williams +1

We provide a fast \emph{witness-sensitive} algorithm for detecting an induced diamond (a $K_4$ minus an edge) in an $n$-vertex graph containing $t$ induced diamonds. Our algorithm…