Tight hardness for shortest cycles and paths in sparse graphs

zbMATH Open1403.68168arXiv1712.08147MaRDI QIDQ4607968FDOQ4607968

Authors: Andrea Lincoln, Virginia Vassilevska Williams, Ryan Williams 

Publication date: 15 March 2018

Full work available at URL: https://arxiv.org/abs/1712.08147

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

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)

Cited In (29)

• Faster algorithms for all-pairs bounded min-cuts
• Title not available (Why is that?)
• Counting Homomorphic Cycles in Degenerate Graphs
• Improved distance sensitivity oracles with subcubic preprocessing time
• Title not available (Why is that?)
• Leanness computation: small values and special graph classes
• A Lower Bound on Cycle-Finding in Sparse Digraphs
• Improved Merlin-Arthur protocols for central problems in fine-grained complexity
• Tensor network complexity of multilinear maps
• Graph pattern detection: hardness for all induced patterns and faster noninduced cycles
• Consistent query answering for primary keys in Datalog
• 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
• Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time.
• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
• Algorithms and conditional lower bounds for planning problems
• Circulant association schemes on triples
• Approximating the Longest Cycle Problem in Sparse Graphs
• Enumeration complexity of conjunctive queries with functional dependencies
• Fine-grained non-interactive key-exchange without idealized assumptions
• Listing all fixed-length simple cycles in sparse graphs in optimal time
• 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
• Title not available (Why is that?)
• Pattern masking for dictionary matching: theory and practice
• Faster combinatorial \(k\)-clique algorithms
• The fine-grained complexity of multi-dimensional ordering properties

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)