direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

When can Graph Hyperbolicity be computed in Linear Time?

Till Fluschnik (TU Berlin)

Hyperbolicity measures, in terms of (distance) metrics, how close a given graph is to being a tree. Due to its relevance in modeling real-world networks, hyperbolicity has seen intensive research over the last years. Unfortunately, the best known practical algorithms for computing the hyperbolicity number of a \(n\)-vertex graph have running time \(O(n^4)\). Exploiting the framework of parameterized complexity analysis, we explore possibilities for “linear-time FPT” algorithms to compute hyperbolicity. For instance, we show that hyperbolicity can be computed in time \(2^{O(k)} + O(n + m)\) (\(m\) being the number of graph edges, \(k\) being the size of a vertex cover) while at the same time, unless the SETH fails, there is no \(2^{o(k)} n^{(2-\epsilon)}\)-time algorithm.

This is joint work with Christian Komusiewicz, George B. Mertzios, André Nichterlein, Rolf Niedermeier, and Nimrod Talmon.

Till Fluschnik
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras