On the Complexity of Telephone Broadcasting: From Cacti to Bounded Pathwidth Graphs

Abstract

In Telephone Broadcasting, the goal is to disseminate a message from a given source vertex of an input graph to all other vertices in the minimum number of rounds, where at each round, an informed vertex can send the message to at most one of its uninformed neighbors. We study the problem in cactus graphs and graphs of bounded pathwidth. Despite many previous efforts, the complexity of the problem in cactus graphs remained open. We settle this question by establishing the NP-completeness of broadcasting in cactus graphs and graphs of pathwdith 2. On the positive side, we present constant-factor approximation algorithms for the studied families of graphs, namely, an algorithm with an approximation factor of 2 for cactus graphs and an approximation factor of O(1) for graphs of constant pathwidth.