3 papers
cs.DS2026
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…
cs.DS2025
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…
cs.DS2024
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…