When can graph hyperbolicity be computed in linear time?

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Review text

The paper discusses the graph hyperbolicity problem and proposes practical algorithms for a host of special cases. Additionally, it provides interesting lower bounds on the efficiency of algorithms for some cases. The problem of computing the hyperbolicity of a graph is an important one, because of its wide applications. Simply put, the hyperbolicity of a graph is a measure of how close a graph is to a tree. Hyperbolicity is a metric measure as opposed to tree-width which is a non-metric measure. If the hyperbolicity of a graph is 0, then it is a tree. The importance of hyperbolicity stems from the fact that as per existing literature, several real-world graphs are tree-like from a distance metric point of view. The hyperbolicity problem is simultaneously easy from the conceptual perspective and difficult from the perspective of empirical considerations. On the positive side, there is a straightforward brute-force algorithm that runs in $O(n^4)$ time, where $n$ is the number of vertices in the graph. Deterministically, it has been shown that the worst-case running time can be improved to $O(n^{3.69})$; however, this result relies on some results in matrix multiplication which are widely considered impractical. Existing literature also provides quadratic lower bounds on this problem. The paper provides linear-time parameterized algorithms for the hyperbolicity problem when the following quantities are small (bounded): covering path number, feedback edge number, number of $\ge 3$-degree vertices, vertex cover number and distance to cographs. Furthermore, the authors use the Strong Exponential Time Hypothesis (SETH) to prove lower bounds on any algorithm whose running time is parameterized by the vertex cover number. The paper is extremely well-written and well-organized. The ideas are clearly explained. The proofs of theorems are easy to follow. What is truly interesting is the breadth of ideas that the authors have used to arrive at the results. It is also noteworthy that they have fleshed out proofs of certain theorems which were first described in other papers. This paper will serve as the cornerstone for future papers in this field.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: When can graph hyperbolicity be computed in linear time?

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