The Complexity of Growing a Graph

Mertzios, George B, Michail, Othon ORCID: 0000-0002-6234-3960, Skretas, George, Spirakis, Paul G ORCID: 0000-0001-5396-3749 and Theofilatos, Michail (2022) The Complexity of Growing a Graph. In: International Symposium on Algorithmics of Wireless Networks (ALGOSENSORS).

Text MMSST-Algosensors-22.pdf - Author Accepted Manuscript Download (346kB) | Preview

Abstract

We study a new algorithmic process of graph growth. The process starts from a single initial vertex and operates in discrete time-steps, called slots. In every slot, the process updates the current graph instance to generate the next graph instance. The process first sets. Then, for every, it adds at most one new vertex to and adds the edge alongside any subset of the edges is at distance at most from u in, for some integer fixed in advance. The process completes slot t after removing any (possibly empty) subset of edges from. Removed edges are called excess edges is the graph grown by the process after t slots. The goal of this paper is to investigate the algorithmic and structural properties of this process of graph growth. Graph Growth Problem: Given a graph family F, we are asked to design a centralized algorithm that on any input target graph, will output such a process growing G, called a growth schedule for G. Additionally, the algorithm should try to minimize the total number of slots k and of excess edges used by the process. We show that the most interesting case is when and that there is a natural trade-off between k and K. We begin by investigating growth schedules of excess edges. On the positive side, we provide polynomial-time algorithms that decide whether a graph has growth schedules of slots. Along the way, interesting connections to cop-win graphs are being revealed. On the negative side, we establish strong hardness results for the problem of determining the minimum number of slots required to grow a graph with zero excess edges. In particular, we show that the problem (i) is NP-complete and (ii) for any, cannot be approximated within, unless P = NP. We then move our focus to the other extreme of the -spectrum, to investigate growth schedules of (poly)logarithmic slots. We 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 excess edges. We also give lower bounds on the number of excess edges, when the number of slots is fixed to n.

Item Type:	Conference or Workshop Item (Unspecified)
Uncontrolled Keywords:	Temporal graph, Cop-win graph, Graph process, Polynomial-time algorithm, Lower bound, NP-complete, Hardness result
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	31 Aug 2022 10:32
Last Modified:	01 Mar 2023 11:54
DOI:	10.1007/978-3-031-22050-0_9
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3162790