Acquaintance time of a graph

DOI10.1137/130930078MaRDI QIDQ3192163zbMATH OpenOpenAlexFDO

Authors Itai Benjamini, Igor Shinkar, Gilad Tsur

Publication date 26 September 2014

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

NP-completenessrouting via matchingssocial network graph algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Social networks; opinion dynamics (91D30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We define the following parameter of connected graphs. For a given graph $G$ we place one agent in each vertex of $G$. Every pair of agents sharing a common edge is declared to be acquainted. In each round we choose some matching of $G$ (not necessarily a maximal matching), and for each edge in the matching the agents on this edge swap places. After the swap, again, every pair of agents sharing a common edge become acquainted, and the process continues. We define the emph{acquaintance time} of a graph $G$, denoted by $AC(G)$, to be the minimal number of rounds required until every two agents are acquainted. We first study the acquaintance time for some natural families of graphs including the path, expanders, the binary tree, and the complete bipartite graph. We also show that for all positive integers $n$ and $kleq{n}^{1.5}$ there exists an $n$-vertex graph $G$ such that $AC(G)=Theta(k)$. We also prove that for all $n$-vertex connected graphs $G$ we have $AC(G)=Oleft(frac{n}^{2}log(n)/loglog(n)ight)$, improving the $O(n^2)$ trivial upper bound achieved by sequentially letting each agent perform depth-first search along a spanning tree of $G$. Studying the computational complexity of this problem, we prove that for any constant $tgeq1$ the problem of deciding that a given graph $G$ has $AC(G)leqt$ or $AC(G)geq2t$ is $mathcalNP$-complete. That is, $AC(G)$ is $mathcalNP$-hard to approximate within multiplicative factor of 2, as well as within any additive constant factor. On the algorithmic side, we give a deterministic algorithm that given a graph $G$ with $AC(G)=1$ finds a $lceiln/cceil$-rounds strategy for acquaintance in time $n^{c+O(1)}$. We also design a randomized polynomial time algorithm that given a graph $G$ with $AC(G)=1$ finds with high probability an $O(log(n))$-rounds strategy for acquaintance.

Recommendations

• A tight upper bound on acquaintance time of graphs
• A note on the acquaintance time of random graphs
• Acquaintance time of random graphs near connectivity threshold
• The acquaintance time of (percolated) random geometric graphs
• Rapid social connectivity

Cited in

(5)

• The acquaintance time of (percolated) random geometric graphs
• Acquaintance time of random graphs near connectivity threshold
• A tight upper bound on acquaintance time of graphs
• A note on the acquaintance time of random graphs
• Collision-free network exploration

This page was built for publication: Acquaintance time of a graph

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