6 papers · 1 filter
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…
Worst-Case to Expander-Case Reductions
Amir Abboud, Nathan Wallheimer
In recent years, the expander decomposition method was used to develop many graph algorithms, resulting in major improvements to longstanding complexity barriers. This powerful ham…
Improved Compression of the Okamura-Seymour Metric
Shay Mozes, Nathan Wallheimer, Oren Weimann
Let be an undirected unweighted planar graph. Consider a vector storing the distances from an arbitrary vertex to all vertices of…