10 papers
Efficiently Listing Projected Trees, and Equivalence of Listing and Enumeration
Karl Bringmann, Nick Fischer, Yanheng Wang
The subgraph isomorphism problem and its generalizations, such as conjunctive queries where some nodes are projected, are among the most fundamental problems in graph algorithms an…
An Optimal Algorithm for Binary Closest String
Nick Fischer, Mursalin Habib
We revisit the Binary Closest String problem, which asks, given a set of binary strings , to compute a string minimizing the maximum Hamming distance to …
Node-Weighted Triangles: Faster and Simpler
Shyan Akmal, Nick Fischer
Weighted variants of triangle detection are an important object of study because of their prominence in fine-grained complexity. We revisit the Node-Weighted Triangle problem, wher…
Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses
Nick Fischer
The APSP Hypothesis states that the All-Pairs Shortest Paths (APSP) problem requires time on graphs with polynomially bounded integer edge weights. Two increasingly st…
A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection
Amir Abboud, Shyan Akmal, Nick Fischer
We present the first truly subcubic, combinatorial algorithm for detecting an induced -cycle in a graph. The running time is on -node graphs, thus separating th…
All-Pairs Shortest Paths with Few Weights per Node
Amir Abboud, Nick Fischer, Ce Jin +2
We study the central All-Pairs Shortest Paths (APSP) problem under the restriction that there are at most distinct weights on the outgoing edges from every node. For this…
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…
Faster Combinatorial k-Clique Algorithms
Amir Abboud, Nick Fischer, Yarin Shechter
Detecting if a graph contains a -Clique is one of the most fundamental problems in computer science. The asymptotically fastest algorithm runs in time , where i…
The Effect of Sparsity on -Dominating Set and Related First-Order Graph Properties
Nick Fischer, Marvin Künnemann, Mirza Redzic
We revisit -Dominating Set, one of the first problems for which a tight conditional lower bound (for ), based on SETH, was shown (Pătraşcu and Williams, SODA…
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
Amir Abboud, Nick Fischer, Zander Kelley +2
We revisit the fundamental Boolean Matrix Multiplication (BMM) problem. With the invention of algebraic fast matrix multiplication over 50 years ago, it also became known that BMM…