The Complexity of Growing a Graph



Mertzios, George B, Michail, Othon ORCID: 0000-0002-6234-3960, Skretas, George ORCID: 0000-0003-2514-8004, Spirakis, Paul G ORCID: 0000-0001-5396-3749 and Theofilatos, Michail ORCID: 0000-0002-3699-0179
(2021) The Complexity of Growing a Graph. [Preprint]

[img] Text
2107.14126v1.pdf - Submitted Version

Download (1MB) | Preview

Abstract

We study a new algorithmic process of graph growth. The process starts from a single initial vertex u_0 and operates in discrete time-steps, called \emph{slots}. In every slot t\geq 1, the process updates the current graph instance to generate the next graph instance G_t, according to the following vertex and edge update rules. The process first sets G_t = G_{t-1}. Then, for every u\in V(G_{t-1}), it adds at most one new vertex u' to V(G_{t}) and adds the edge uu' to E(G_{t}) alongside any subset of the edges {vu' | v\in V(G_{t-1}) is at distance at most d-1 from u in G_{t-1}}, for some integer d\geq 1 fixed in advance. The process completes slot t after removing any (possibly empty) subset of edges from E(G_{t}). Removed edges are called \emph{excess edges}. Graph Growth Problem: Given a graph family F, we are asked to design a \emph{centralized} algorithm that on any input \emph{target graph} G\in F, will output such a process growing G, called a \emph{growth schedule} for G. Additionally, the algorithm should try to minimize the total number of slots k and of excess edges \ell used by the process. We show that the most interesting case is when d = 2 and that there is a natural trade-off between k and \ell. On the positive side, we provide polynomial-time algorithms that decide whether a graph has growth schedules of k=\log n or k=n-1 slots. Along the way, interesting connections to cop-win graphs are being revealed. On the negative side, we establish strong hardness results for determining the minimum number of slots required to grow a graph with zero excess edges. We then show that trees can be grown in a polylogarithmic number of slots using linearly many excess edges, while planar graphs can be grown in a logarithmic number of slots using O(n\log n) excess edges. We also give lower bounds on the number of excess edges, when the number of slots is fixed to \log n.

Item Type: Preprint
Additional Information: 27 pages
Uncontrolled Keywords: cs.DS, cs.DS, cs.CC
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 09 Aug 2021 08:36
Last Modified: 10 Aug 2022 16:10
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3132584