Into the Square - On the Complexity of Quadratic-Time Solvable Problems

Understand

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.