7 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…