4 papers · 1 filter
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…