The complexity of growing a graph

Mertzios, George; Michail, Othon; Skretas, George; Spirakis, Paul G.; Theofilatos, Michail

Abstract

We study a new algorithmic process of graph growth which starts from a single initial vertex and operates in discrete time-steps, called slots. In every slot, the graph grows via two operations (i) vertex generation and (ii) edge activation. The process completes at the last slot where a (possibly empty) subset of the edges of the graph are removed. Removed edges are called excess edges. The main problem investigated in this paper is: Given a target graph G, design an algorithm that outputs a process that grows G, called a growth schedule. Additionally, we aim to minimize the total number of slots k and of excess edges ℓ used by the process. We provide both positive and negative results, with our main focus being either schedules with sub-linear number of slots or with no excess edges.

Citation

Mertzios, G., Michail, O., Skretas, G., Spirakis, P. G., & Theofilatos, M. (2025). The complexity of growing a graph. Journal of Computer and System Sciences, 147, Article 103587. https://doi.org/10.1016/j.jcss.2024.103587

• Journal Article Type: Article
• Acceptance Date: Sep 13, 2024
• Online Publication Date: Sep 27, 2024
• Publication Date: 2025-02
• Deposit Date: Oct 2, 2024
• Publicly Available Date: Oct 3, 2024
• Journal: Journal of Computer and System Sciences
• Print ISSN: 0022-0000
• Electronic ISSN: 1090-2724
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 147
• Article Number: 103587
• DOI: https://doi.org/10.1016/j.jcss.2024.103587
• Public URL: https://durham-repository.worktribe.com/output/2941671