Tight hardness for shortest cycles and paths in sparse graphs

MaRDI QIDQ4607968zbMATH OpenFDO

Authors Andrea Lincoln, Virginia Vassilevska Williams, Ryan Williams

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1712.08147, http://dl.acm.org/citation.cfm?id=3175350

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Paths and cycles (05C38)

Recommendations

• Fine-grained complexity for sparse graphs
• On the difficulty of some shortest path problems
• scientific article; zbMATH DE number 1962826
• Approximating the girth
• Approximating the girth

Cited in

(29)

• Faster algorithms for all-pairs bounded min-cuts
• scientific article; zbMATH DE number 7651202 (Why is no real title available?)
• Counting Homomorphic Cycles in Degenerate Graphs
• Improved distance sensitivity oracles with subcubic preprocessing time
• scientific article; zbMATH DE number 7765381 (Why is no real title available?)
• Leanness computation: small values and special graph classes
• A Lower Bound on Cycle-Finding in Sparse Digraphs
• Tensor network complexity of multilinear maps
• Improved Merlin-Arthur protocols for central problems in fine-grained complexity
• Consistent query answering for primary keys in Datalog
• Graph pattern detection: hardness for all induced patterns and faster noninduced cycles
• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
• A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
• Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction
• Algorithms and conditional lower bounds for planning problems
• Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time.
• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
• Circulant association schemes on triples
• Approximating the Longest Cycle Problem in Sparse Graphs
• Enumeration complexity of conjunctive queries with functional dependencies
• Listing all fixed-length simple cycles in sparse graphs in optimal time
• Fine-grained non-interactive key-exchange without idealized assumptions
• Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
• Removing additive structure in 3SUM-based reductions
• From circuit complexity to faster all-pairs shortest paths
• scientific article; zbMATH DE number 7561483 (Why is no real title available?)
• The fine-grained complexity of multi-dimensional ordering properties
• Pattern masking for dictionary matching: theory and practice
• Faster combinatorial \(k\)-clique algorithms

This page was built for publication: Tight hardness for shortest cycles and paths in sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4607968)