The radius and diameter are fundamental graph parameters, with several natural definitions
for directed graphs. Each definition is well-motivated in a variety of applications. All versions …

Due to the lack of unconditional polynomial lower bounds, it is now in fashion to prove
conditional lower bounds in order to advance our understanding of the class P. The vast …

We introduce the Nondeterministic Strong Exponential Time Hypothesis (NSETH) as a
natural extension of the Strong Exponential Time Hypothesis (SETH). We show that both …

We present KADABRA, a new algorithm to approximate betweenness centrality in directed
and undirected graphs, which significantly outperforms all previous approaches on real …

Network science methodology is increasingly applied to a large variety of real-world
phenomena, often leading to big network data sets. Thus, networks (or graphs) with millions …

We develop a new technique for constructing sparse graphs that allow us to prove near-
linear lower bounds on the round complexity of computing distances in the CONGEST …

Recently, hardness results for problems in P were achieved using reasonable complexity-
theoretic assumptions such as the Strong Exponential Time Hypothesis. According to these …

Abstract The Orthogonal Vectors problem (OV) asks: given n vectors in {0, 1} O (log n), are
two of them orthogonal? OV is easily solved in O (n 2 log n) time, and it is a central problem …

Given a connected graph G=(V, E), where V denotes the set of nodes and E the set of edges
of the graph, the length (that is, the number of edges) of the shortest path between two …

Properties definable in first-order logic are algorithmically interesting for both theoretical and
pragmatic reasons. Many of the most studied algorithmic problems, such as Hitting Set and …