Scale-free spanning trees: complexity, bounds and algorithms

We introduce and study the general problem of finding a most "scale-free-like" spanning tree of a connected graph. It is motivated by a particular problem in epidemiology, and may be useful in studies of various dynamical processes in networks. We employ two possible objective functions fo...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-05
Main Authors: Orlovich, Yury, Kukharenko, Kirill, Kaibel, Volker, Skums, Pavel
Format: Article
Language:English
Subjects:
Algorithms
Computer simulation
Epidemiology
Graph theory
Graphs
Integer programming
Linear programming
Trees (mathematics)
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We introduce and study the general problem of finding a most "scale-free-like" spanning tree of a connected graph. It is motivated by a particular problem in epidemiology, and may be useful in studies of various dynamical processes in networks. We employ two possible objective functions for this problem and introduce the corresponding algorithmic problems termed \(m\)-SF and \(s\)-SF Spanning Tree problems. We prove that those problems are APX- and NP-hard, respectively, even in the classes of cubic, bipartite and split graphs. We study the relations between scale-free spanning tree problems and the max-leaf spanning tree problem, which is the classical algorithmic problem closest to ours. For split graphs, we explicitly describe the structure of optimal spanning trees and graphs with extremal solutions. Finally, we propose two Integer Linear Programming formulations and two fast heuristics for the \(s\)-SF Spanning Tree problem, and experimentally assess their performance using simulated and real data.
ISSN:2331-8422
DOI:10.48550/arxiv.2005.13703