Fine-grained complexity for sparse graphs

DOI10.1145/3188745.3188888MaRDI QIDQ5230293zbMATH OpenOpenAlexFDO

Authors Udit Agarwal, Vijaya Ramachandran

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

graph algorithmssparse graphsminimum weight cyclefine-grained reductions

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) 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)

Abstract: We consider the fine-grained complexity of sparse graph problems that currently have $ildeO(mn)$ time algorithms, where m is the number of edges and n is the number of vertices in the input graph. This class includes several important path problems on both directed and undirected graphs, including APSP, MWC (minimum weight cycle), and Eccentricities, which is the problem of computing, for each vertex in the graph, the length of a longest shortest path starting at that vertex. We introduce the notion of a sparse reduction which preserves the sparsity of graphs, and we present near linear-time sparse reductions between various pairs of graph problems in the $ildeO(mn)$ class. Surprisingly, very few of the known nontrivial reductions between problems in the $ildeO(mn)$ class are sparse reductions. In the directed case, our results give a partial order on a large collection of problems in the $ildeO(mn)$ class (along with some equivalences). In the undirected case we give two nontrivial sparse reductions: from MWC to APSP, and from unweighted ANSC (all nodes shortest cycles) to APSP. The latter reduction also gives an improved algorithm for ANSC (for dense graphs). We propose the MWC Conjecture, a new conditional hardness conjecture that the weight of a minimum weight cycle in a directed graph cannot be computed in time polynomially smaller than mn. Our sparse reductions for directed path problems in the $ildeO(mn)$ class establish that several problems in this class, including 2-SiSP (second simple shortest path), Radius, and Eccentricities, are MWCC hard. We also identify Eccentricities as a key problem in the $ildeO(mn)$ class which is simultaneously MWCC-hard, SETH-hard and k-DSH-hard, where SETH is the Strong Exponential Time Hypothesis, and k-DSH is the hypothesis that a dominating set of size k cannot be computed in time polynomially smaller than n^k.

Recommendations

• Sparsity. Graphs, structures, and algorithms
• Algorithmic properties of sparse digraphs
• A general framework for graph sparsification
• A general framework for graph sparsification
• A Complexity Dichotomy for the Coloring of Sparse Graphs
• Resolution complexity of perfect matching principles for sparse graphs
• A New Combinatorial Approach for Sparse Graph Problems
• Problems remaining NP-complette for sparse or dense graphs
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS

Cited in

(11)

• Improved distance queries and cycle counting by Frobenius normal form
• Computing minimum weight cycle in the CONGEST model
• Approximation algorithms for min-distance problems in DAGs
• Simplifying and unifying replacement paths algorithms in weighted directed graphs
• Fine-Grained Complexity Theory (Tutorial)
• Fine-grained I/O complexity via reductions: new lower bounds, faster algorithms, and a time hierarchy
• 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
• Tight hardness for shortest cycles and paths in sparse graphs
• The fine-grained complexity of multi-dimensional ordering properties

This page was built for publication: Fine-grained complexity for sparse graphs

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