Search

Social network users are commonly connected to hundreds or even thousands of other users. However, these ties are not all of equal strength; for example, we often are connected to good friends or family members as well as acquaintances. Inferring the tie strengths is an essential task in social network analysis. Common approaches classify the ties into strong and weak edges based on the network topology using the strong triadic closure (STC). The STC states that if for three nodes, $\textit{A}$, $\textit{B}$, and $\textit{C}$, there are strong ties between $\textit{A}$ and $\textit{B}$, as well as $\textit{A}$ and $\textit{C}$, there has to be a (weak or strong) tie between $\textit{B}$ and $\textit{C}$. Moreover, a variant of the STC called STC+ allows adding new weak edges to obtain improved solutions. Recently, the focus of social network analysis has been shifting from single-layer to multilayer networks due to their ability to represent complex systems with multiple types of interactions or relationships in multiple social network platforms like Facebook, LinkedIn, or X (formerly Twitter). However, straightforwardly applying the STC separately to each layer of multilayer networks usually leads to inconsistent labelings between layers. Avoiding such inconsistencies is essential as they contradict the idea that tie strengths represent underlying, consistent truths about the relationships between users. Therefore, we adapt the definitions of the STC and STC+ for multilayer networks and provide ILP formulations to solve the problems exactly. Solving the ILPs is computationally costly; hence, we additionally provide an efficient 2-approximation for the STC and a 6-approximation for the STC+ minimization variants. The experiments show that, unlike standard approaches, our new highly efficient algorithms lead to consistent strong/weak labelings of the multilayer network edges.

Delivering a parcel from the distribution hub to the customer's doorstep is called the \textit{last-mile delivery} step in delivery logistics. In this paper, we study a hybrid {\it truck-drones} model for the last-mile delivery step, in which a truck moves on a predefined path carrying parcels and drones deliver the parcels. We define the \textsc{online drone scheduling} problem, where the truck moves in a predefined path, and the customer's requests appear online during the truck's movement. The objective is to schedule a drone associated with every request to minimize the number of drones used subject to the battery budget of the drones and compatibility of the schedules. We propose a 3-competitive deterministic algorithm using the next-fit strategy and 2.7-competitive algorithms using the first-fit strategy for the problem with $O(\log n)$ worst-case time complexity per request, where $n$ is the maximum number of active requests at any time. We also introduce \textsc{online variable-size drone scheduling} problem (OVDS). Here, we know all the customer's requests in advance; however, the drones with different battery capacities appear online. The objective is to schedule customers' requests for drones to minimize the number of drones used. We propose a $(2\alpha + 1)$-competitive algorithm for the OVDS problem with total running time $O(n \log n)$ for $n$ customer requests, where $\alpha$ is the ratio of the maximum battery capacity to the minimum battery capacity of the drones. Finally, we address how to generate intervals corresponding to each customer request when there are discrete stopping points on the truck's route, from where the drone can fly and meet with the truck.

We investigate the black hole search problem by a set of mobile agents in a dynamic torus. Black hole is defined to be a dangerous stationary node which has the capability to destroy any number of incoming agents without leaving any trace of its existence. A torus of size $n\times m$ ($3\leq n \leq m$) is a collection of $n$ row rings and $m$ column rings, and the dynamicity is such that each ring is considered to be 1-interval connected, i.e., in other words at most one edge can be missing from each ring at any round. The parameters which define the efficiency of any black hole search algorithm are: the number of agents and the number of rounds (or \textit{time}) for termination. We consider two initial configurations of mobile agents: first, the agents are co-located and second, the agents are scattered. In each case, we establish lower and upper bounds on the number of agents and on the amount of time required to solve the black hole search problem.

Real-time analysis of graphs containing temporal information, such as social media streams, Q&A networks, and cyber data sources, plays an important role in various applications. Among them, detecting patterns is one of the fundamental graph analysis problems. In this paper, we study time-constrained continuous subgraph matching, which detects a pattern with a strict partial order on the edge set in real-time whenever a temporal data graph changes over time. We propose a new algorithm based on two novel techniques. First, we introduce a filtering technique called time-constrained matchable edge that uses temporal information for filtering with polynomial space. Second, we develop time-constrained pruning techniques that reduce the search space by pruning some of the parallel edges in backtracking, utilizing temporal information. Extensive experiments on real and synthetic datasets show that our approach outperforms the state-of-the-art algorithm by up to two orders of magnitude in terms of query processing time.

We study the problem of black hole search by a set of mobile agents, where the underlying graph is a dynamic cactus. A black hole is a dangerous vertex in the graph that eliminates any visiting agent without leaving any trace behind. Key parameters that dictate the complexity of finding the black hole include: the number of agents required (termed as \textit{size}), the number of moves performed by the agents in order to determine the black hole location (termed as \textit{move}) and the \textit{time} (or round) taken to terminate. This problem has already been studied where the underlying graph is a dynamic ring \cite{di2021black}. In this paper, we extend the same problem to a dynamic cactus. We introduce two categories of dynamicity, but still the underlying graph needs to be connected: first, we examine the scenario where, at most, one dynamic edge can disappear or reappear at any round. Secondly, we consider the problem for at most $k$ dynamic edges. In both scenarios, we establish lower and upper bounds for the necessary number of agents, moves and rounds., Comment: This paper recently got accepted in WALCOM 2024

A temporal network is a dynamic graph where every edge is assigned an integer time label that indicates at which discrete time step the edge is available. We consider the problem of hierarchically decomposing the network and introduce an edge-based decomposition framework that unifies the core and truss decompositions for temporal networks while allowing us to consider the network's temporal dimension. Based on our new framework, we introduce the $(k,\Delta)$-core and $(k,\Delta)$-truss decompositions, which are generalizations of the classic $k$-core and $k$-truss decompositions for multigraphs. Moreover, we show how $(k,\Delta)$-cores and $(k,\Delta)$-trusses can be efficiently further decomposed to obtain spatially and temporally connected components. We evaluate the characteristics of our new decompositions and the efficiency of our algorithms. Moreover, we demonstrate how our $(k,\Delta)$-decompositions can be applied to analyze malicious content in a Twitter network to obtain insights that state-of-the-art baselines cannot obtain., Comment: Accepted at WSDM'25

We show how to find and efficiently maintain maximal k-edge-connected subgraphs in undirected graphs. In particular, we provide the following results. (1) A general framework for maintaining the maximal k-edge-connected subgraphs upon insertions of edges or vertices, by successively partitioning the graph into its k-edge-connected components. This defines a decomposition tree, which can be maintained by using algorithms for the incremental maintenance of the k-edge-connected components as black boxes at every level of the tree. (2) As an application of this framework, we provide two algorithms for the incremental maintenance of the maximal $3$-edge-connected subgraphs. These algorithms allow for vertex and edge insertions, interspersed with queries asking whether two vertices belong to the same maximal $3$-edge-connected subgraph. The first algorithm has $O(m\alpha(m,n) + n^2\log^2 n)$ total running time and uses $O(n)$ space, where $m$ is the number of edge insertions and queries, and $n$ is the total number of vertices inserted. The second algorithm performs the same operations in faster $O(m\alpha(m,n) + n^2\alpha(n,n))$ time in total, using $O(n^2)$ space. (3) We provide efficient constructions of sparse subgraphs that have the same maximal k-edge-connected subgraphs as the original graph. These are useful in speeding up computations involving the maximal k-edge-connected subgraphs in dense undirected graphs. (4) We give two deterministic algorithms for computing the maximal k-edge-connected subgraphs in undirected graphs, with running times $O(m+k^{O(1)}n\sqrt{n}\mathrm{polylog}(n))$ and $O(m+k^{O(k)}n\sqrt{n}\log{n})$, respectively. (5) A fully dynamic algorithm for maintaining information about the maximal k-edge-connected subgraphs for fixed k. Our update bounds are $O(n\sqrt{n}\log{n})$ worst-case time, and we achieve constant time for maximal k-edge-connected subgraph queries.

Inferring tie strengths in social networks is an essential task in social network analysis. Common approaches classify the ties as wea} and strong ties based on the strong triadic closure (STC). The STC states that if for three nodes, $A$, $B$, and $C$, there are strong ties between $A$ and $B$, as well as $A$ and $C$, there has to be a (weak or strong) tie between $B$ and $C$. A variant of the STC called STC+ allows adding a few new weak edges to obtain improved solutions. So far, most works discuss the STC or STC+ in static networks. However, modern large-scale social networks are usually highly dynamic, providing user contacts and communications as streams of edge updates. Temporal networks capture these dynamics. To apply the STC to temporal networks, we first generalize the STC and introduce a weighted version such that empirical a priori knowledge given in the form of edge weights is respected by the STC. Similarly, we introduce a generalized weighted version of the STC+. The weighted STC is hard to compute, and our main contribution is an efficient 2-approximation (resp. 3-approximation) streaming algorithm for the weighted STC (resp. STC+) in temporal networks. As a technical contribution, we introduce a fully dynamic $k$-approximation for the minimum weighted vertex cover problem in hypergraphs with edges of size $k$, which is a crucial component of our streaming algorithms. An empirical evaluation shows that the weighted STC leads to solutions that better capture the a priori knowledge given by the edge weights than the non-weighted STC. Moreover, we show that our streaming algorithm efficiently approximates the weighted STC in real-world large-scale social networks.

We present an improved algorithm for computing the $4$-edge-connected components of an undirected graph in linear time. The new algorithm uses only elementary data structures, and it is simple to describe and to implement in the pointer machine model of computation., Comment: arXiv admin note: substantial text overlap with arXiv:2105.02910

We present the first linear-time algorithm that computes the $4$-edge-connected components of an undirected graph. Hence, we also obtain the first linear-time algorithm for testing $4$-edge connectivity. Our results are based on a linear-time algorithm that computes the $3$-edge cuts of a $3$-edge-connected graph $G$, and a linear-time procedure that, given the collection of all $3$-edge cuts, partitions the vertices of $G$ into the $4$-edge-connected components.

In many real datasets such as social media streams and cyber data sources, graphs change over time through a graph update stream of edge insertions and deletions. Detecting critical patterns in such dynamic graphs plays an important role in various application domains such as fraud detection, cyber security, and recommendation systems for social networks. Given a dynamic data graph and a query graph, the continuous subgraph matching problem is to find all positive matches for each edge insertion and all negative matches for each edge deletion. The state-of-the-art algorithm TurboFlux uses a spanning tree of a query graph for filtering. However, using the spanning tree may have a low pruning power because it does not take into account all edges of the query graph. In this paper, we present a symmetric and much faster algorithm SymBi which maintains an auxiliary data structure based on a directed acyclic graph instead of a spanning tree, which maintains the intermediate results of bidirectional dynamic programming between the query graph and the dynamic graph. Extensive experiments with real and synthetic datasets show that SymBi outperforms the state-of-the-art algorithm by up to three orders of magnitude in terms of the elapsed time.

In this paper we present an efficient reachability oracle under single-edge or single-vertex failures for planar directed graphs. Specifically, we show that a planar digraph $G$ can be preprocessed in $O(n\log^2{n}/\log\log{n})$ time, producing an $O(n\log{n})$-space data structure that can answer in $O(\log{n})$ time whether $u$ can reach $v$ in $G$ if the vertex $x$ (the edge~$f$) is removed from $G$, for any query vertices $u,v$ and failed vertex $x$ (failed edge $f$). To the best of our knowledge, this is the first data structure for planar directed graphs with nearly optimal preprocessing time that answers all-pairs queries under any kind of failures in polylogarithmic time. We also consider 2-reachability problems, where we are given a planar digraph $G$ and we wish to determine if there are two vertex-disjoint (edge-disjoint) paths from $u$ to $v$, for query vertices $u,v$. In this setting we provide a nearly optimal 2-reachability oracle, which is the existential variant of the reachability oracle under single failures, with the following bounds. We can construct in $O(n\log^{O(1)}{n})$ time an $O(n\log^{3+o(1)}{n})$-space data structure that can check in $O(\log^{2+o(1)}{n})$ time for any query vertices $u,v$ whether $v$ is 2-reachable from $u$, or otherwise find some separating vertex (edge) $x$ lying on all paths from $u$ to $v$ in $G$. To obtain our results, we follow the general recursive approach of Thorup for reachability in planar graphs [J.~ACM~'04] and we present new data structures which generalize dominator trees and previous data structures for strong-connectivity under failures [Georgiadis et al., SODA~'17]. Our new data structures work also for general digraphs and may be of independent interest., Comment: Full version of a SODA'21 paper

Let $G=(V,E)$ be an $n$-vertex directed acyclic graph (DAG). A lowest common ancestor (LCA) of two vertices $u$ and $v$ is a common ancestor $w$ of $u$ and $v$ such that no descendant of $w$ has the same property. In this paper, we consider the problem of computing an LCA, if any, for all pairs of vertices in a DAG. The fastest known algorithms for this problem exploit fast matrix multiplication subroutines and have running times ranging from $O(n^{2.687})$ [Bender et al.~SODA'01] down to $O(n^{2.615})$ [Kowaluk and Lingas~ICALP'05] and $O(n^{2.569})$ [Czumaj et al.~TCS'07]. Somewhat surprisingly, all those bounds would still be $\Omega(n^{2.5})$ even if matrix multiplication could be solved optimally (i.e., $\omega=2$). This appears to be an inherent barrier for all the currently known approaches, which raises the natural question on whether one could break through the $O(n^{2.5})$ barrier for this problem. In this paper, we answer this question affirmatively: in particular, we present an $\tilde O(n^{2.447})$ ($\tilde O(n^{7/3})$ for $\omega=2$) algorithm for finding an LCA for all pairs of vertices in a DAG, which represents the first improvement on the running times for this problem in the last 13 years. A key tool in our approach is a fast algorithm to partition the vertex set of the transitive closure of $G$ into a collection of $O(\ell)$ chains and $O(n/\ell)$ antichains, for a given parameter $\ell$. As usual, a chain is a path while an antichain is an independent set. We then find, for all pairs of vertices, a \emph{candidate} LCA among the chain and antichain vertices, separately. The first set is obtained via a reduction to min-max matrix multiplication. The computation of the second set can be reduced to Boolean matrix multiplication similarly to previous results on this problem. We finally combine the two solutions together in a careful (non-obvious) manner.

The Massive Parallel Computing (MPC) model gained popularity during the last decade and it is now seen as the standard model for processing large scale data. One significant shortcoming of the model is that it assumes to work on static datasets while, in practice, real-world datasets evolve continuously. To overcome this issue, in this paper we initiate the study of dynamic algorithms in the MPC model. We first discuss the main requirements for a dynamic parallel model and we show how to adapt the classic MPC model to capture them. Then we analyze the connection between classic dynamic algorithms and dynamic algorithms in the MPC model. Finally, we provide new efficient dynamic MPC algorithms for a variety of fundamental graph problems, including connectivity, minimum spanning tree and matching., Comment: Accepted to the 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2019)

In this paper we study the dynamic versions of two basic graph problems: Minimum Dominating Set and its variant Minimum Connected Dominating Set. For those two problems, we present algorithms that maintain a solution under edge insertions and edge deletions in time $O(\Delta\cdot \text{polylog}~n)$ per update, where $\Delta$ is the maximum vertex degree in the graph. In both cases, we achieve an approximation ratio of $O(\log n)$, which is optimal up to a constant factor (under the assumption that $P \ne NP$). Although those two problems have been widely studied in the static and in the distributed settings, to the best of our knowledge we are the first to present efficient algorithms in the dynamic setting. As a further application of our approach, we also present an algorithm that maintains a Minimal Dominating Set in $O(min(\Delta, \sqrt{m}))$ per update.

The All-Pairs Min-Cut problem (aka All-Pairs Max-Flow) asks to compute a minimum $s$-$t$ cut (or just its value) for all pairs of vertices $s,t$. We study this problem in directed graphs with unit edge/vertex capacities (corresponding to edge/vertex connectivity). Our focus is on the $k$-bounded case, where the algorithm has to find all pairs with min-cut value less than $k$, and report only those. The most basic case $k=1$ is the Transitive Closure (TC) problem, which can be solved in graphs with $n$ vertices and $m$ edges in time $O(mn)$ combinatorially, and in time $O(n^{\omega})$ where $\omega<2.38$ is the matrix-multiplication exponent. These time bounds are conjectured to be optimal. We present new algorithms and conditional lower bounds that advance the frontier for larger $k$, as follows: (i) A randomized algorithm for vertex capacities that runs in time $O((nk)^{\omega})$. (ii) Two deterministic algorithms for edge capacities (which is more general) that work in DAGs and further reports a minimum cut for each pair. The first algorithm is combinatorial (does not involve matrix multiplication) and runs in time $O(2^{O(k^2)}\cdot mn)$. The second algorithm can be faster on dense DAGs and runs in time $O((k\log n)^{4^k+o(k)} n^{\omega})$. (iii) The first super-cubic lower bound of $n^{\omega-1-o(1)} k^2$ time under the $4$-Clique conjecture, which holds even in the simplest case of DAGs with unit vertex capacities. It improves on the previous (SETH-based) lower bounds even in the unbounded setting $k=n$. For combinatorial algorithms, our reduction implies an $n^{2-o(1)} k^2$ conditional lower bound. Thus, we identify new settings where the complexity of the problem is (conditionally) higher than that of TC.

We present a decremental data structure for maintaining the SPQR-tree of a planar graph subject to edge contractions and deletions. The update time, amortized over $\Omega(n)$ operations, is $O(\log^2 n)$. Via SPQR-trees, we give a decremental data structure for maintaining $3$-vertex connectivity in planar graphs. It answers queries in $O(1)$ time and processes edge deletions and contractions in $O(\log^2 n)$ amortized time. This is an exponential improvement over the previous best bound of $O(\sqrt{n}\,)$ that has stood for over 20 years. In addition, the previous data structures only supported edge deletions.

In this paper, we present new incremental algorithms for maintaining data structures that represent all connectivity cuts of size one in directed graphs (digraphs), and the strongly connected components that result by the removal of each of those cuts. We give a conditional lower bound that provides evidence that our algorithms may be tight up to sub-polynomial factors. As an additional result, with our approach we can also maintain dynamically the $2$-vertex-connected components of a digraph during any sequence of edge insertions in a total of $O(mn)$ time. This matches the bounds for the incremental maintenance of the $2$-edge-connected components of a digraph., Comment: Accepted to the 13th Latin American Theoretical INformatics Symposium (LATIN 2018)

We present a data structure that can maintain a simple planar graph under edge contractions in linear total time. The data structure supports adjacency queries and provides access to neighbor lists in $O(1)$ time. Moreover, it can report all the arising self-loops and parallel edges. By applying the data structure, we can achieve optimal running times for decremental bridge detection, 2-edge connectivity, maximal 3-edge connected components, and the problem of finding a unique perfect matching for a static planar graph. Furthermore, we improve the running times of algorithms for several planar graph problems, including decremental 2-vertex and 3-edge connectivity, and we show that using our data structure in a black-box manner, one obtains conceptually simple optimal algorithms for computing MST and 5-coloring in planar graphs.

In this paper we show a new algorithm for the decremental single-source reachability problem in directed planar graphs. It processes any sequence of edge deletions in $O(n\log^2{n}\log\log{n})$ total time and explicitly maintains the set of vertices reachable from a fixed source vertex. Hence, if all edges are eventually deleted, the amortized time of processing each edge deletion is only $O(\log^2 n \log \log n)$, which improves upon a previously known $O(\sqrt{n})$ solution. We also show an algorithm for decremental maintenance of strongly connected components in directed planar graphs with the same total update time. These results constitute the first almost optimal (up to polylogarithmic factors) algorithms for both problems. To the best of our knowledge, these are the first dynamic algorithms with polylogarithmic update times on general directed planar graphs for non-trivial reachability-type problems, for which only polynomial bounds are known in general graphs.

Connectivity related concepts are of fundamental interest in graph theory. The area has received extensive attention over four decades, but many problems remain unsolved, especially for directed graphs. A directed graph is 2-edge-connected (resp., 2-vertex-connected) if the removal of any edge (resp., vertex) leaves the graph strongly connected. In this paper we present improved algorithms for computing the maximal 2-edge- and 2-vertex-connected subgraphs of a given directed graph. These problems were first studied more than 35 years ago, with $\widetilde{O}(mn)$ time algorithms for graphs with m edges and n vertices being known since the late 1980s. In contrast, the same problems for undirected graphs are known to be solvable in linear time. Henzinger et al. [ICALP 2015] recently introduced $O(n^2)$ time algorithms for the directed case, thus improving the running times for dense graphs. Our new algorithms run in time $O(m^{3/2})$, which further improves the running times for sparse graphs. The notion of 2-connectivity naturally generalizes to k-connectivity for $k>2$. For constant values of k, we extend one of our algorithms to compute the maximal k-edge-connected in time $O(m^{3/2} \log{n})$, improving again for sparse graphs the best known algorithm by Henzinger et al. [ICALP 2015] that runs in $O(n^2 \log n)$ time., Comment: Revised version of SODA 2017 paper including details for k-edge-connected subgraphs

We introduce a new dynamic data structure for maintaining the strongly connected components (SCCs) of a directed graph (digraph) under edge deletions, so as to answer a rich repertoire of connectivity queries. Our main technical contribution is a decremental data structure that supports sensitivity queries of the form "are $ u $ and $ v $ strongly connected in the graph $ G \setminus w $?", for any triple of vertices $ u, v, w $, while $ G $ undergoes deletions of edges. Our data structure processes a sequence of edge deletions in a digraph with $n$ vertices in $O(m n \log{n})$ total time and $O(n^2 \log{n})$ space, where $m$ is the number of edges before any deletion, and answers the above queries in constant time. We can leverage our data structure to obtain decremental data structures for many more types of queries within the same time and space complexity. For instance for edge-related queries, such as testing whether two query vertices $u$ and $v$ are strongly connected in $G \setminus e$, for some query edge $e$. As another important application of our decremental data structure, we provide the first nontrivial algorithm for maintaining the dominator tree of a flow graph under edge deletions. We present an algorithm that processes a sequence of edge deletions in a flow graph in $O(m n \log{n})$ total time and $O(n^2 \log{n})$ space. For reducible flow graphs we provide an $O(mn)$-time and $O(m + n)$-space algorithm. We give a conditional lower bound that provides evidence that these running times may be tight up to subpolynomial factors., Comment: Accepted to the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)