4 papers
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 minus an edge) in an -vertex graph containing induced diamonds. Our algorithm…
Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs
Amir Abboud, Ron Safier, Nathan Wallheimer
A recent paper by the authors (ITCS'26) initiates the study of the Triangle Detection problem in graphs avoiding a fixed pattern H as a subgraph and proposes a dichotomy hypothesis…
Triangle Detection in H-Free Graphs
Amir Abboud, Ron Safier, Nathan Wallheimer
We initiate the study of combinatorial algorithms for Triangle Detection in -free graphs. The goal is to decide if a graph that forbids a fixed pattern as a subgraph contain…
Recognizing Sumsets is NP-Complete
Amir Abboud, Nick Fischer, Ron Safier +1
Sumsets are central objects in additive combinatorics. In 2007, Granville asked whether one can efficiently recognize whether a given set is a sumset, i.e. whether there is a s…