Into the square: on the complexity of some quadratic-time solvable problems

DOI10.1016/J.ENTCS.2016.03.005MaRDI QIDQ737085zbMATHOpenAlexWikidataFDO

Authors Michele Borassi, Pilu Crescenzi, M. A. Habib

Publication date 5 August 2016

Full work available at URL https://arxiv.org/abs/1407.4972

zbMATH Keywords

reductionstransitive closurequadratic-time algorithmsstrong exponential-time hypothesis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: 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(m{n}^{fracomega+14})$, 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^{frac53})$ 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.

Recommendations

• Subcubic equivalences between path, matrix, and triangle problems
• On some fine-grained questions in algorithms and complexity
• Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
• On problems as hard as CNF-SAT
• Subcubic equivalences between graph centrality problems, APSP and diameter

Cites work

• scientific article; zbMATH DE number 4031953 (Why is no real title available?)
• scientific article; zbMATH DE number 3635493 (Why is no real title available?)
• A faster algorithm for betweenness centrality*
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Approximating Betweenness Centrality
• Consequences of Faster Alignment of Sequences
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Finding a Minimum Circuit in a Graph
• Finding extremal sets in less than quadratic time
• Finding orthogonal vectors in discrete structures
• Hyperbolicity and chordality of a graph
• Into the square: on the complexity of some quadratic-time solvable problems
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Modular decomposition and transitive orientation
• On computing the Gromov hyperbolicity
• On computing the diameter of real-world undirected graphs
• On the possibility of faster \textsc{SAT} algorithms
• Reducibility among combinatorial problems
• Subcubic equivalences between graph centrality problems, APSP and diameter
• Subquadratic algorithms for 3SUM
• The Structure and Function of Complex Networks
• The subset partial order: computing and combinatorics
• Threesomes, degenerates, and love triangles
• Which problems have strongly exponential complexity?

Cited in

(31)

• A note on the complexity of computing the number of reachable vertices in a digraph
• A general algorithmic scheme for combinatorial decompositions with application to modular decompositions of hypergraphs
• On computing large temporal (unilateral) connected components
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• Computing the union join and subset graph of acyclic hypergraphs in subquadratic time
• On computing large temporal (unilateral) connected components
• Fast approximation and exact computation of negative curvature parameters of graphs
• Revisiting decomposition by clique separators
• $$\alpha _i$$-Metric Graphs: Radius, Diameter and all Eccentricities
• Graph Search Trees and Their Leaves
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• \( \alpha_i\)-metric graphs: radius, diameter and all eccentricities
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• Leanness computation: small values and special graph classes
• Fast diameter computation within split graphs
• Non-inclusion and other subclasses of chordal graphs
• scientific article; zbMATH DE number 7651160 (Why is no real title available?)
• Into the square: on the complexity of some quadratic-time solvable problems
• Applying clique-decomposition for computing Gromov hyperbolicity
• A faster diameter problem algorithm for a chordal graph, with a connection to its center problem
• Getting linear time in graphs of bounded neighborhood diversity
• On Linear Recognition of Tree-Width at Most Four
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• Fast approximation and exact computation of negative curvature parameters of graphs
• Beyond Helly graphs: the diameter problem on absolute retracts
• Fast approximation of eccentricities and distances in hyperbolic graphs
• When can graph hyperbolicity be computed in linear time?
• Diameter, eccentricities and distance oracle computations on \(H\)-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
• A story of diameter, radius, and (almost) Helly property
• The diameter of AT‐free graphs
• Eccentricity queries and beyond using hub labels

This page was built for publication: Into the square: on the complexity of some quadratic-time solvable problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q737085)