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

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

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

(43)

• Listing all fixed-length simple cycles in sparse graphs in optimal time
• Consistent query answering for primary keys in Datalog
• The fine-grained complexity of multi-dimensional ordering properties
• Improved distance sensitivity oracles with subcubic preprocessing time
• Algorithms and conditional lower bounds for planning problems
• Approximating the Longest Cycle Problem in Sparse Graphs
• Circulant association schemes on triples
• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
• From circuit complexity to faster all-pairs shortest paths
• Tensor network complexity of multilinear maps
• Consistent query answering for primary keys in logspace
• Faster algorithms for all-pairs bounded min-cuts
• 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
• Graph pattern detection: hardness for all induced patterns and faster noninduced cycles
• Optimal polynomial-time compression for Boolean Max CSP
• Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time.
• Counting Homomorphic Cycles in Degenerate Graphs
• A Lower Bound on Cycle-Finding in Sparse Digraphs
• scientific article; zbMATH DE number 7765381 (Why is no real title available?)
• Improved Merlin-Arthur protocols for central problems in fine-grained complexity
• Removing additive structure in 3SUM-based reductions
• Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
• Pattern masking for dictionary matching: theory and practice
• Faster combinatorial \(k\)-clique algorithms
• Leanness computation: small values and special graph classes
• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
• Fine-grained non-interactive key-exchange without idealized assumptions
• Conditionally optimal approximation algorithms for the girth of a directed graph
• Coverability in VASS revisited: improving Rackoff's bounds to obtain conditional optimality
• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
• Optimal polynomial-time compression for Boolean Max CSP
• Any-k algorithms for enumerating ranked answers to conjunctive queries
• Current algorithms for detecting subgraphs of bounded treewidth are probably optimal
• Constructing a distance sensitivity oracle in \(O(n^{2.5794}M)\) time
• Fully dynamic algorithms for minimum weight cycle and related problems
• Fine-grained complexity of multiple domination and dominating patterns in sparse graphs
• Faster combinatorial k-clique algorithms
• Improved girth approximation in weighted undirected graphs
• The role of regularity in (hyper-)clique detection and implications for optimizing Boolean CSPs
• Worst-case and average-case hardness of hypercycle and database problems
• On incremental approximate shortest paths in directed graphs
• Enumeration complexity of conjunctive queries with functional dependencies

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)