4 papers · 1 filter
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…
Listing 4-Cycles
Amir Abboud, Seri Khoury, Oree Leibowitz +1
In this note we present an algorithm that lists all -cycles in a graph in time where is their number. Notably, this separates -cycle list…