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

DOI10.1016/J.ENTCS.2016.03.005zbMATH Open1345.68170arXiv1407.4972OpenAlexW1499093134WikidataQ113317700 ScholiaQ113317700MaRDI QIDQ737085FDOQ737085

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

Publication date: 5 August 2016

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.

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

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

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)

Cites Work

• The Structure and Function of Complex Networks
• Title not available (Why is that?)
• Reducibility among Combinatorial Problems
• Modular decomposition and transitive orientation
• Which problems have strongly exponential complexity?
• Subquadratic algorithms for 3SUM
• A faster algorithm for betweenness centrality*
• Threesomes, Degenerates, and Love Triangles
• On the possibility of faster \textsc{SAT} algorithms
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Hyperbolicity and chordality of a graph
• Finding extremal sets in less than quadratic time
• Finding a Minimum Circuit in a Graph
• On computing the Gromov hyperbolicity
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• On computing the diameter of real-world undirected graphs
• Approximating Betweenness Centrality
• The Subset Partial Order: Computing and Combinatorics
• Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
• Title not available (Why is that?)
• Consequences of Faster Alignment of Sequences
• Finding orthogonal vectors in discrete structures
• Into the square: on the complexity of some quadratic-time solvable problems

Cited In (31)

• On computing large temporal (unilateral) connected components
• Fast approximation and exact computation of negative curvature parameters of graphs
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• Computing the union join and subset graph of acyclic hypergraphs in subquadratic time
• When can graph hyperbolicity be computed in linear time?
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• On Linear Recognition of Tree-Width at Most Four
• \( \alpha_i\)-metric graphs: radius, diameter and all eccentricities
• A story of diameter, radius, and (almost) Helly property
• Fast Diameter Computation within Split Graphs
• Getting linear time in graphs of bounded neighborhood diversity
• Leanness computation: small values and special graph classes
• Non-inclusion and other subclasses of chordal graphs
• Into the square: on the complexity of some quadratic-time solvable problems
• The diameter of AT‐free graphs
• On computing large temporal (unilateral) connected components
• Applying clique-decomposition for computing Gromov hyperbolicity
• A faster diameter problem algorithm for a chordal graph, with a connection to its center problem
• A note on the complexity of computing the number of reachable vertices in a digraph
• Fast approximation of eccentricities and distances in hyperbolic graphs
• Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs
• Eccentricity queries and beyond using hub labels
• Beyond Helly graphs: the diameter problem on absolute retracts
• Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• $$\alpha _i$$-Metric Graphs: Radius, Diameter and all Eccentricities
• Graph Search Trees and Their Leaves
• Title not available (Why is that?)
• Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs
• A general algorithmic scheme for combinatorial decompositions with application to modular decompositions of hypergraphs
• Revisiting Decomposition by Clique Separators

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)