Into the Square On the Complexity of Some Quadratic-time Solvable Problems

被引:47
作者
Borassi, Michele [1 ]
Crescenzi, Pierluigi [2 ]
Habib, Michel [3 ]
机构
[1] IMT Inst Adv Studies, Lucca, Italy
[2] Univ Florence, Dipartimento Ingn Informaz, Florence, Italy
[3] Univ Paris Diderot, LIAFA, Paris, France
关键词
Quadratic-time algorithms; reductions; Strong Exponential Time Hypothesis; transitive closure;
D O I
10.1016/j.entcs.2016.03.005
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We analyze several quadratic-time solvable problems, and we show that these problems are not solvable in truly subquadratic time (that is, in time O(n(2-epsilon)) for some epsilon > 0), unless the well known Strong Exponential Time Hypothesis (in short, SETH) is false. In particular, we start from an artificial quadratic-time solvable variation of the k-Sat problem (already introduced and used in the literature) and we will construct a web of Karp reductions, proving that a truly subquadratic-time algorithm for any of the problems in the web falsifies SETH. Some of these results were already known, while others are, as far as we know, new. The new problems considered are: computing the betweenness centrality of a vertex (the same result was proved independently by Abboud et al.), computing the minimum closeness centrality in a graph, computing the hyperbolicity of a graph, and computing the subset graph of a collection of sets. On the other hand, we will show that testing if a directed graph is transitive and testing if a graph is a comparability graph are subquadratic-time solvable (our algorithm is practical, since it is not based on intricate matrix multiplication algorithms).
引用
收藏
页码:51 / 67
页数:17
相关论文
共 41 条
[1]  
Abboud A., 2015, P 26 ANN ACM SIAM S, P1681
[2]  
Abboud A., 2014, ICALP
[3]   Popular conjectures imply strong lower bounds for dynamic problems [J].
Abboud, Amir ;
Williams, Virginia Vassilevska .
2014 55TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2014), 2014, :434-443
[4]  
[Anonymous], 1987, HYPERBOLIC GROUPS
[5]  
Bader DA, 2007, LECT NOTES COMPUT SC, V4863, P124
[6]  
Bang-Jensen J, 2009, SPRINGER MONOGR MATH, P1, DOI 10.1007/978-1-84800-998-1_1
[7]   Subquadratic algorithms for 3SUM [J].
Baran, Ilya ;
Demaine, Erik D. ;
Patrascu, Mihai .
ALGORITHMICA, 2008, 50 (04) :584-596
[8]  
Bavelas A., 1950, J ACOUST SOC AM, V22, P725, DOI [DOI 10.1121/1.1906679, 10.1121/1.1906679]
[9]  
Borassi M., 2014, SQUARE COMPLEXITY SO
[10]   A faster algorithm for betweenness centrality [J].
Brandes, U .
JOURNAL OF MATHEMATICAL SOCIOLOGY, 2001, 25 (02) :163-177