Fine-Grained Complexity and Conditional Hardness for Sparse Graphs
Fine-Grained Complexity and Conditional Hardness for Sparse Graphs
复制标题
稀疏图的细粒度复杂性和条件硬度
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
V. Ramachandran
中科院分区：
文献类型：
--
作者：
U. Agarwal;V. Ramachandran
我们考虑当前具有$ \ tilde {o}（mn）$ time算法的稀疏图问题的细粒度复杂性，其中m是边缘的数量，n是输入图中的顶点数。该课程包括有针对性和无向图上的几个重要路径问题，包括APSP，MWC（最小重量周期）和偏心率，这是计算的问题，对于图中的每个顶点来说，是计算问题的问题，是最长的最短路径的长度那个顶点。
我们介绍了稀疏减少的概念，该概念保留了图形的稀疏性，并在$ \ tilde {o}（Mn）$类中的各个图形问题之间的线性时间稀疏减少附近。令人惊讶的是，在$ \ tilde {o}（Mn）$类中问题之间的已知非平地降低是稀疏的减少。在指示情况下，我们的结果给出了$ \ tilde {o}（Mn）$ class（以及一些等价）中大量问题的部分顺序。在不方向的情况下，我们给出了两个非平凡的稀疏减少：从MWC到APSP，从未加权的ANSC（所有节点最短的节点）到APSP。后者还原还为ANSC（对于密集图）提供了改进的算法。
我们提出了MWC猜想，这是一种新的条件硬度猜想，即在有向图中最小重量循环的重量不能以多个百货感小于MN计算。我们在$ \ tilde {o}（Mn）$类中针对有向路径问题的稀疏减少，确定此类中的几个问题，包括2-SISP（第二个简单的最短路径），半径和偏心率，这是MWCC硬。我们还将偏心率视为$ \ tilde {o}（mn）$类中的关键问题，该类别是MWCC-HARD，SETH-HARD和K-DSH-HARD，SETH是强大的指数时间假设，K-是强大的。 DSH是一个假设，即不能在多个数字小于n^k的时间内计算出一个主导的大小k。
We consider the fine-grained complexity of sparse graph problems that currently have $\tilde{O}(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 $\tilde{O}(mn)$ class. Surprisingly, very few of the known nontrivial reductions between problems in the $\tilde{O}(mn)$ class are sparse reductions. In the directed case, our results give a partial order on a large collection of problems in the $\tilde{O}(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 $\tilde{O}(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 $\tilde{O}(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.
影响因子：
2.5
作者：
Gronlund, Allan;Pettie, Seth
通讯作者：
Pettie, Seth