English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This paper will analyze several quadratic-time solvable problems, and willclassify them into two classes: problems that are solvable in trulysubquadratic time (that is, in time $O(n^{2-\epsilon})$ for some $\epsilon>0$)and problems that are not, unless the well known Strong Exponential TimeHypothesis (SETH) is false. In particular, we will prove that somequadratic-time solvable problems are indeed easier than expected. We willprovide an algorithm that computes the transitive closure of a directed graphin time $O(mn^{\frac{\omega+1}{4}})$, where $m$ denotes the number of edges inthe 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 boundshold if we want to check whether a graph is transitive, by replacing m with thenumber of edges in the graph itself. As far as we know, this is the fastestalgorithm for sparse transitive digraph recognition. Finally, we will apply ouralgorithm to the comparability graph recognition problem (dating back to 1941),obtaining the first truly subquadratic algorithm. The second part of the paperdeals with hardness results. Starting from an artificial quadratic-timesolvable variation of the k-SAT problem, we will construct a graph of Karpreductions, proving that a truly subquadratic-time algorithm for any of theproblems in the graph falsifies SETH. The analyzed problems are the following:computing the subset graph, finding dominating sets, computing the betweennesscentrality of a vertex, computing the minimum closeness centrality, andcomputing the hyperbolicity of a pair of vertices. We will also be able toinclude in our framework three proofs already appeared in the literature,concerning the graph diameter computation, local alignment of strings andorthogonality of vectors.

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