  This paper will analyze several quadratic-time solvable problems, and will
classify them into two classes: problems that are solvable in truly
subquadratic time (that is, in time $O(n^{2-\epsilon})$ for some $\epsilon>0$)
and problems that are not, unless the well known Strong Exponential Time
Hypothesis (SETH) is false. In particular, we will prove that some
quadratic-time solvable problems are indeed easier than expected. We will
provide an algorithm that computes the transitive closure of a directed graph
in time $O(mn^{\frac{\omega+1}{4}})$, where $m$ denotes the number of edges in
the transitive closure and $\omega$ is the exponent for matrix multiplication.
As a side effect, we will prove that our algorithm runs in time
$O(n^{\frac{5}{3}})$ if the transitive closure is sparse. The same time bounds
hold if we want to check whether a graph is transitive, by replacing m with the
number of edges in the graph itself. As far as we know, this is the fastest
algorithm for sparse transitive digraph recognition. Finally, we will apply our
algorithm to the comparability graph recognition problem (dating back to 1941),
obtaining the first truly subquadratic algorithm. The second part of the paper
deals with hardness results. Starting from an artificial quadratic-time
solvable variation of the k-SAT problem, we will construct a graph of Karp
reductions, proving that a truly subquadratic-time algorithm for any of the
problems in the graph falsifies SETH. The analyzed problems are the following:
computing the subset graph, finding dominating sets, computing the betweenness
centrality of a vertex, computing the minimum closeness centrality, and
computing the hyperbolicity of a pair of vertices. We will also be able to
include in our framework three proofs already appeared in the literature,
concerning the graph diameter computation, local alignment of strings and
orthogonality of vectors.
