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

Abstract : 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(n2−ϵ) for some ϵ>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).
Type de document :
Article dans une revue
Electronic Notes in Theoretical Computer Science, Elsevier, 2016, 322, pp.51-67. 〈10.1016/j.entcs.2016.03.005〉
Liste complète des métadonnées

Littérature citée [39 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01390131
Contributeur : Marie-France Sagot <>
Soumis le : jeudi 10 novembre 2016 - 08:40:09
Dernière modification le : jeudi 18 janvier 2018 - 01:55:19
Document(s) archivé(s) le : mercredi 15 mars 2017 - 02:51:57

Fichier

IntoTheSquare.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Collections

Citation

Michele Borassi, Pierluigi Crescenzi, Michel Habib. Into the Square: On the Complexity of Some Quadratic-time Solvable Problems. Electronic Notes in Theoretical Computer Science, Elsevier, 2016, 322, pp.51-67. 〈10.1016/j.entcs.2016.03.005〉. 〈hal-01390131〉

Partager

Métriques

Consultations de la notice

249

Téléchargements de fichiers

70