1 Introduction↩︎

Broadcasting is a fundamental communication problem that models the dissemination of information through a network. Given a graph and a source vertex initially possessing a message, the objective is to inform every vertex of the graph in as few rounds as possible, under the restriction that each informed vertex may transmit the message to at most one neighbor in every round. Despite its simple formulation, the problem captures an important trade-off between the underlying network topology and the limited communication capacity of individual vertices. Variants of the broadcasting problem have been studied in distributed computing, communication networks, and parallel algorithms, where efficient information dissemination is a central objective.

The broadcasting problem is computationally challenging on general graphs, motivating the search for efficient algorithms on restricted graph classes and under suitable parameterizations. During the past two decades, parameterized complexity has emerged as a successful framework for designing algorithms whose running time depends primarily on a structural parameter of the input rather than its overall size. Numerous graph problems that remain intractable in general admit fixed-parameter tractable algorithms when parameterized by measures such as treewidth, vertex cover number, feedback vertex set, or cluster deletion number.

Literature. The Telephone Broadcast problem was introduced by Slater et al.[2] in 1981 and showed that it is NP-complete in general but can be solved in poly-time when the graph is a tree. Later, Elkin and Kortsarz[3] found that approximating it within a factor of \(3-f(x)\) for any \(x > 0\) is NP-hard, which rules out good polynomial-time approximations and motivates the search for exact and parameterized approaches.

On general graphs, Fomin et al.[1] gave an exact exponential algorithm for the problem via dynamic programming over connected vertex subsets, which runs in time \(3^n\cdot n^{\mathcal{O}(1)}\). This improves the earlier brute-force approach that checks all vertex permutations, obtaining a running time of \(n! \cdot n^{\mathcal{O}(1)}\).

Fomin, Fraigniaud, and Golovach[1] were the first to study the Telephone Broadcast problem from the perspective of parameterized complexity. They showed that the problem is fixed-parameter tractable (FPT) when parameterized by the size of a feedback edge set, the size of a vertex cover, or by \(k=n-t\), where \(t\) is the broadcast deadline. Their algorithm for the vertex cover parameter is based on two simple structural observations: the time needed to inform the vertex cover and the number of vertices outside the vertex cover that can be informed within a given number of rounds. They further asked whether the problem remains FPT when parameterized by treewidth, noting that no NP-hardness result was known even for treewidth at most two.

This question was negatively answered by two independent and closely related works. First, Tale[4] showed that the straightforward brute-force algorithm is essentially optimal. Since the number of informed vertices can at most double in each round, the algorithm runs in \(2^{2^{O(t)}} \cdot n^{\mathcal{O}(1)}\) time when parameterized by the broadcast deadline \(t\). Tale[5] further proved that, assuming the ETH, no algorithm can achieve a significantly better dependence on \(t\), establishing a tight double-exponential lower bound.

Egami et al.[6] further strengthened these hardness results by proving that the problem remains NP-complete on graphs of bounded tree-depth and on cactus graphs that can be transformed into a forest of paths by deleting a single vertex. In response to these hardness results, they studied the problem under other structural parameters. They obtained FPT algorithms parameterized by vertex integrity, extending the earlier result for vertex cover, and by distance to a clique. They also designed FPT approximation algorithms parameterized by clique cover number and cluster vertex deletion.

Beyond vertex cover, related work has looked at whether even smaller structural parameters could still lead to efficient algorithms. One natural candidate is the size of a minimum dominating set, since requiring a graph to have a small dominating set is less restrictive than requiring a small vertex cover. Therefore, an FPT algorithm parameterized by the dominating set number would significantly extend the known results. However, Tale [5] showed that this is not always possible. In particular, the problem is para-NP-hard when parameterized by several smaller structural parameters, including the feedback vertex set number and treewidth. As a result, these parameterizations do not admit XP algorithms unless (\(\mathrm{P}=\mathrm{NP}\)), answering an open question posed by Fomin et al. [1]. As we show in this work, the same phenomenon also holds for the dominating set number.

Polar graphs were introduced by Tyshkevich and Chernyak [7]as a generalization of split graphs, as well as bipartite and co-bipartite graphs, by allowing one side of the partition to induce a disjoint union of cliques rather than a single clique. Although recognizing whether a graph is polar is NP-complete, once a polar partition is given, the graph has sufficient structure to be exploited algorithmically. To the best of our knowledge, no broadcast-specific algorithm has previously been developed for polar graphs. In this paper, we present the first polynomial-time algorithm for the broadcasting problem in this graph class.

On the hardness side, recent work has shown that the boundary between tractable and intractable cases extends to very sparse, path-like graphs. Aminian et al. [8] proved that the problem is NP-hard on cactus graphs of pathwidth two, while Egami et al. [6] showed that it remains NP-complete even on cactus graphs that can be transformed into a disjoint union of paths by deleting just one vertex. These results suggest that the broadcasting problem remains hard even on graphs that are very close to paths. This naturally motivates studying graph parameters that measure such closeness, such as the vertex distance to a path, which we investigate in this paper.

Our Contributions↩︎

In this paper, we study the Telephone Broadcasting problem and advance the state of the art along several complementary axes: exact/approximate algorithms on general graphs, parameterized exact and approximate algorithms, polynomial-time solvability on a structured graph class, and hardness results. Our contributions can be summarized as follows.

A constant additive approximation on general graphs. We design an algorithm that achieves a constant additive \(x\) approximation to the optimum broadcast time on general graphs, running in \(\mathcal{O^*}({3-f(x)})^n)\) time, where \(f(x)>0\) when \(x>0\). The key algorithmic idea is a round-splitting technique: instead of allowing a single round to inform an arbitrarily large set of uninformed vertices from the currently informed set, we show that it suffices to break a constant number of rounds into several sequential sub-rounds, each of which informs only a restricted subset of vertices. This restructuring shrinks the search space that needs to be explored, while provably costing only an additive constant number of extra rounds, yielding the improved runtime bound.

An improved \(poly(n)\) time algorithm with parameter vertex integrity. We give a \(poly(n)\) tractable approximation algorithm with ad additive factor \(+2k\), when the modulator \(S\) is connected and, \(k\) is the vertex integrity of the input graph. This improves upon the previously best-known FPT runtime \(2^{({vi}^2log{(vi)})}.n^{O(1)}\) for this parameterization due to  [9].

Parameterized approximation by distance to clique. We study the problem from a parameterized-approximation perspective and provide an algorithm that achieves an additive \(2\)-approximation to the optimum number of rounds when parameterized by the distance to a clique. Compared to the algorithm of Egami et al. [6], our algorithm offers a substantially improved running time, at the cost of a mild relaxation in the approximation guarantee on the number of rounds.

An XP approximation algorithm parameterized by distance to path. We also provide a \(2\)-approximation XP algorithm for the problem parameterized by the distance to a path, extending efficient approximation algorithms to this structural parameter.

Hardness results. On the negative side, we show that the problem remains para-NP-hard when parameterized by (i) the vertex cover number above maximum matching size, (ii) the minimum dominating set size, and (iii) the diameter of the graph. These results delineate the boundary of tractability and indicate that it is unlikely to yield even XP algorithms when parameterized by these parameters, thereby complementing our positive algorithmic results.

Polynomial-time solvability on polar graphs. We identify a graph class which we call polar graphs in which the vertex set can be partitioned into an induced cluster subgraph and a single isolated (apex-like) vertex, with arbitrary edges permitted between the two parts. We show that Telephone Broadcasting is solvable in polynomial time on this class. This case is of natural practical relevance: it models settings with a single informer vertex disseminating information to entities that are themselves organized into tightly-knit communities (clusters).

Together, these results paint a fairly complete picture of the parameterized and approximation landscape of Telephone Broadcasting, improving on prior work in both exact parameterized complexity and approximation guarantees, while also identifying new tractable structural classes and sharpening the known hardness frontier.

2 Preliminaries and Notations↩︎

Graphs. We follow standard graph-theoretic notation and terminology, referring to the textbook of Diestel[10] for any undefined notions. Unless stated otherwise, all graphs considered are finite and undirected. We write \(V(G)\) and \(E(G)\) for the vertex and edge sets of a graph \(G\). For a set of vertices \(X\), the induced subgraph \(G[X]\) keeps exactly the vertices of \(X\) and the edges of \(G\) with both endpoints inside \(X\); we abbreviate \(G - X = G[V(G) \setminus X]\). The neighborhood of a vertex \(v\) is \(N(v) = \{u : \{u,v\} \in E(G)\}\), and its degree is \(|N(v)|\).

A clique is a set of pairwise adjacent vertices, and an independent set is a set of pairwise non-adjacent ones. A matching is a set of edges no two of which share an endpoint, and we say a matching saturates a set \(A\) if every vertex of \(A\) is the endpoint of one of its edges. Matchings are the natural language for a single round of broadcasting informing a fresh batch of vertices in one step is precisely matching each new vertex to a distinct informer and this is the connection Observation 1 makes explicit. Finally, the diameter of \(G\) is the largest shortest-path distance between any two of its vertices. A vertex cover is a set of vertices that contains at least one endpoint of every edge. The size of a minimum vertex cover is denoted by \(\text{vc}(G)\). Since each edge in a matching must be covered by a different vertex, the maximum matching number \(\text{mm}(G)\) satisfies \(\text{mm}\le \text{vc}\). We study the parameter VC-MM(vertex cover over maximum matching) which measures the gap between these two quantities. A dominating set is a set \(D\) such that every vertex outside \(D\) has a neighbor in \(D\). Its minimum size is denoted by \(\text{dom}(G)\). Since every vertex cover is also a dominating set in graphs without isolated vertices, \(\text{dom}(G)\le \text{vc}(G)\).

We also consider graph parameters defined by a modulator, that is, a set of vertices whose removal leaves the graph in a simpler graph class. If \(G-M\) is a path, then \(|M|\) is called the distance to a path. Similarly, if \(G-M\) is a clique, then \(|M|\) is called the distance to a clique. In both cases, the parameter \(k=|M|\) measures how far the graph is from the corresponding graph class.

Twins and polar graphs. Two vertices in an independent set are called twins if they have the same neighborhood. Therefore, if \(S\) is a vertex cover, the independent set can be partitioned into at most \(2^{|S|}\) neighborhood types. A graph is polar if its vertex set can be partitioned into two parts, one inducing a disjoint union of cliques and the other an independent set. Such a partition is called a polar partition. Polar graphs generalize several well-known graph classes, including split, bipartite, and co-bipartite graphs[7]. Since recognizing polar graphs is NP-complete, we assume that a polar partition is given as part of the input in Section 7. Throughout, \(\log\) means the base-\(2\) logarithm, and \([p]\) stands for \(\{1, 2, \dots, p\}\) for \(p\in \mathbb{N}\).

The broadcasting model. Let \(G\) be a connected graph and let \(s \in V(G)\) be a distinguished source vertex that initially holds a single piece of information (equivalently, a message). Information is spread in a sequence of rounds. In each round, an informed vertex may inform at most one uninformed neighbor, and an uninformed vertex can receive the information from at most one informed neighbor. It also can be represented by a sequence of informed sets \(S_0 \subseteq S_1 \subseteq \cdots \subseteq S_\tau\), where \(S_i\) is the set of vertices informed by the end of round \(i\). Initially, \(S_0=\{s\}\) and finally \(S_\tau=V(G)\). For every \(i\), the newly informed vertices \(S_{i+1}\setminus S_i\) must be matchable to distinct vertices in \(S_i\) by a matching in the bipartite graph induced by \((S_i,\, S_{i+1}\setminus S_i)\). Similarly, each vertex in \(S_{i+1}\setminus S_i\) is informed by a distinct vertex in \(S_i\), reflecting the telephone broadcasting rule.

The second picture is a broadcast tree: a spanning tree rooted at \(s\) in which each vertex, once informed, hands the message to its children one per round in some chosen order. We formally define, a broadcasting protocol is a pair \(\bigl(T, \{C(v) \mid v \in V(T)\}\bigr)\), where \(T\) is a spanning tree of \(G\) rooted at \(s\), and for each \(v \in V(T)\), \(C(v)\) is an ordered set of the children of \(v\) in \(T\). As soon as \(v\) receives the message, it starts sending it to its children in \(T\) in the order defined by \(C(v)\).

The length of a broadcasting protocol is the number of rounds it uses. The minimum number of rounds required to inform all vertices from a source vertex \(s\) is called the broadcast time of \(G\) from \(s\), denoted by \(b(G,s)\). A protocol that achieves this minimum is called an optimal broadcasting protocol. We write \(T_{opt}\) for \(b(G,s)\) when the source is clear from the context. If the source vertex is not fixed, we consider the worst-case broadcast time, defined as \(b(G)=\max_{u\in V(G)} b(G,u)\). Since each informed vertex can inform at most one new vertex in a round, the number of informed vertices can at most double in every round. Therefore, \(b(G,s)\ge \left\lceil\log_2 n\right\rceil.\) This bound is tight, as it is achieved by complete graphs.

The decision problem we study packages this up as follows.

Telephone Broadcast. Given a connected graph \(G\), a source \(s\), and an integer \(t\), decide whether the message can reach every vertex within \(t\) rounds, that is, whether \(b(G,s)\le t\).

We call such an instance a YES-instance if the deadline can be met, and a NO-instance otherwise. There is also a source-free version that asks whether \(b(G,s) \le t\). Both are NP-complete on general graphs [2], although they become easy on trees; worse, even approximating the broadcast time within a factor \(3 - f(x)\) is NP-hard for every \(x > 0\) [3], which is a large part of why parameterized and structural approaches are so appealing here.

Parameterized complexity. We use parameterized complexity in the usual way (see [1] for its use on broadcasting). An instance carries both a size and a parameter \(k\), and the question is how the difficulty scales with \(k\) rather than with the whole input. A problem is fixed-parameter tractable (FPT) if it can be solved in time \(f(k) \cdot n^{O(1)}\) for some computable function \(f\) depending only on \(k\) [11]. We write \(O^*(\cdot)\) when hiding polynomial factors keeps the expression readable. A problem belongs to the class \(\mathrm{XP}\) if it can be solved in time \(n^{f(k)}\), where \(k\) is the parameter. Thus, for every fixed value of \(k\), the algorithm runs in polynomial time. On the other hand, a problem is para-NP-hard if it remains NP-hard even when the parameter is fixed to a constant. Consequently, such a problem can’t admit an \(\textsf{XP}\) algorithm unless \(\mathrm{P}=\mathrm{NP}\).

Parameters. Throughout this paper, we consider several well-studied structural graph parameters that capture different aspects of a graph’s complexity. These parameters play a central role in our algorithmic and hardness results and are related by well-known inequalities. We briefly define the parameters used in this work and summarize the relationships between them.

3 Approximation Algorithm for the Broadcasting Problem on General Graph↩︎

In this section, we present an exact algorithm for the Broadcasting problem that runs in time \((3-f(x))^n\) for some \(x > 0\). This improves upon the previously best known algorithm due to [1], which solves the Broadcasting problem exactly in time \(3^n\). Before we describe the algorithm, we discuss the overall idea and make the following observation which will be used crucially in the construction.

3.1 A Brief Overview↩︎

For a given instance of the Broadcasting problem \((G, s, t)\), we construct a new directed graph \(G' = (V', E')\) such that each vertex \(v_S \in V'\) corresponds to a subset \(S \subseteq V(G)\). Recall that in the Broadcasting problem, we wish to broadcast information from the source \(s\) to all vertices of \(G\) within time \(t\). This is equivalent to finding an optimal sequence \(\{S_1, S_2, \ldots, S_t\}\) of subsets of \(V(G)\), where \(S_1 = \{s\}\), \(S_t = V(G)\), and \(S_i \subsetneq S_j\) for all \(i < j\), such that every vertex \(v \in S_i\) has received the information by round \(i\).

The key intuition behind the construction of \(G'\) is to think of each vertex \(v_S \in V'\) as a state, representing the set of vertices that have been informed so far. We connect these states in such a way that reaching state \(v_{S_i}\) at step \(i\) implies that all vertices in \(S_i\) have received the information within round \(i\). Therefore, finding an optimal broadcasting sequence for \(G\) reduces to finding a shortest path in \(G'\) from the initial state \(v_{\{s\}}\) to the final state \(v_{V(G)}\).

As we will show, this approach yields an \(+x\) approximation algorithm, running in time strictly less than \((3-f(x))^n\) (for some positive increasing function \(f(x)\) w.r.t. the constant \(x\)). This gives us our main theorem, which we prove in the remainder of this section.

3.2 The Algorithm↩︎

Before we explain our algorithm in two parts, we make the following observation 1.

1. Construction of \(G'\): For a given instance \(G\) with \(n\) vertices, we consider all possible subsets of \(V(G)\). For each subset \(S \subseteq V(G)\), we introduce a vertex \(v_S\) in \(G'\). Thus \(G'\) has exactly \(2^n\) vertices in total, and we think of each vertex \(v_S\) as a state representing the set \(S\) of informed vertices. For each ordered pair of subsets \((S, S')\), we add a directed arc from \(v_S\) to \(v_{S'}\) in \(G'\) if and only if the following three conditions are satisfied.

• \(S \subset S'\).

• Either \(|S| \leq n/x\), or \(|S' \setminus S| \leq n/x\).

• There exists a matching saturating \(S' \setminus S\) in the bipartite graph with bipartition \((S, S' \setminus S)\) whose edge set is induced by \(G\).

We briefly justify each condition. In the Broadcasting problem, at every intermediate round \(t' \leq t\), there is always at least one new vertex that receives the information in round \(t'\) but not in round \(t' - 1\). Condition (C1) ensures that the set of informed vertices is strictly increasing across any two consecutive rounds. Condition (C2) is imposed to bound the total number of arcs in \(G'\), which in turn controls the running time of the algorithm, as we will analyze later. By Observation 1, condition (C3) ensures that adding an arc from \(v_S\) to \(v_{S'}\) is valid, in the sense that it is actually possible to broadcast from the state \(v_S\) (where all vertices in \(S\) are informed) to the state \(v_{S'}\) (where all vertices in \(S'\) are informed) in exactly one round.

2. Finding the Shortest Path in \(G'\): In the second part of the algorithm, we find a shortest path in \(G'\) from the initial state \(v_{\{s\}}\) to the final state \(v_{V(G)}\) using the Breadth First Search (BFS) algorithm. Since BFS runs in time proportional to the number of vertices and edges of the graph it is applied to, this step runs in time \(|V(G')|+|E(G')|\).

3.3 Proof of Theorem 1.1↩︎

Towards proving the main result of this section, we establish the following two lemmas.

4 A \(\mathrm{OPT}+2k\) Approximation for Broadcast under Vertex Integrity↩︎

4.0.0.1 Vertex integrity modulator.

A set \(S\subseteq V(G)\) is a modulator of order \(k\) if \(|S|+\max_{C}|C|\le k\), where \(C\) ranges over the connected components of \(G-S\). Write \(a=|S|\) and let \(b=\max_{C}|C|\), so \(a+b\le k\) (hence \(a\le k\) and \(b\le k\)). Let \(C_1,\dots,C_m\) be the components of \(G-S\), and let \(C_0\) denote the one containing \(s\) (if \(s\in S\), there is no \(C_0\)).

4.0.0.2 Standing assumptions.

\(G\) is connected and \(S\) is connected.

The Algorithm↩︎

The schedule runs in three phases.

Phase 1(Inform \(S\)). Route the message from \(s\) to \(S\) and flood \(S\).

Phase 2 (Seed the components). Compute the smallest integer \(t\) for which there is an assignment \(\phi\) sending each non-source component \(C_i\) to an adjacent vertex of \(S\), with no vertex of \(S\) receiving more than \(t\) components. (Binary-search on \(t\); feasibility for a fixed \(t\) is a bipartite \(b\)-matching, solvable by max-flow.) Then, over \(t\) rounds, each vertex \(v\in S\) calls the components assigned to it, one per round, planting one informed vertex in each.

Phase 3(Fill the components). Inside each component, flood from its seed.

All three phases run in polynomial time.

Remark. Phase 2 seeds only the non-source components, since \(C_0\) already contains an informed vertex and is filled in Phase 3.

As shown earlier in the paper [1], the Broadcasting problem is fixed-parameter tractable (FPT) when parameterized by the minimum vertex cover size. This naturally raises the question of whether an FPT algorithm exists for parameters slightly smaller than the vertex cover size. Here, we answer this negatively by presenting two para-NP-hardness proofs, each obtained via a reduction from a general Broadcasting graph instance to a Broadcasting instance with a constant value of, respectively, vertex cover above maximum matching and dominating set size, as well as diameter of the graph.

4.1 Para-NP-hardness w.r.t. VC over MM↩︎

Since the problem is FPT when parameterized by the vertex cover number of the graph, we consider a smaller related parameter, namely the vertex cover number above the maximum matching (\(VC-MM\)). For this choice of parameter, we show that the problem is XP-intractable, which is to say, for a fixed value of the parameter, finding a polynomial time algorithm is impractical.

We do this by a polynomial reduction of an arbitrary (NP-hard) instance of the Telephone Broadcasting to another related instance of the Telephone Broadcasting where \(VC-MM=1\). Any XP algorithms for the later therefore imply a polynomial algorithm for the former (which would violate the NP-hardness). We now start with the reduction.

Construction. Consider a decision version of the Telephone Broadcasting problem-\((G,s,t)\) where \(G\) is the input graph, \(s\) is the unique vertex that has the information at the beginning and \(t\) is the time (number of rounds) required to inform all the vertices in the graph. \((G,s,t)\) is a “YES" instance of the problem if it is possible to disseminate the piece of information from \(s\) to all the vertices in \(G\) within \(t\) rounds and a”NO"-instance otherwise.

From \((G,s,t)\), we construct another instance \((G',s,t')\) of the Telephone Broadcasting problem as follows

1. \(V(G')=V(G)\cup V'\) where \(V'\) is a copy of \(V(G)\setminus \{s\}\). We call the copy of a vertex \(v\in V(G)\) as \(v'\in V'\subset {V(G')}\).

2. \(E(G')=E(G)\cup \{(v,v'):v\in V(G)\setminus \{s\}\}\), i.e, each vertex in \(V(G)\) except the source \(s\) is adjacent to a unique copy of itself in \(V'\).

3. \(t'=t+1\)

Now, the only property left to check is that the reduction [newinstance] is indeed a valid polynomial reduction. To this end, we mention the following lemma

Therefore, the reduction is indeed a valid polynomial reduction, and we have the following hardness result.

4.2 Para-NP-hardness w.r.t. Dominating set and Diameter↩︎

Our second choice of parameter is dominating set size. Again with the same idea we show that the problem is W-hard to solve by showing a polytime reduction from an arbitrary (or general) Broadcasting instance, as it is maintained earlier that, it is NP-hard to decide a general broadcast instance \(G(V, E,s,t)\) is a yes instance or not. Here we construct a new broadcasting instance with dominating set size \(1\).

Construction: Given an instance \(G(V,E,s,t)\) of the Broadcasting problem, we construct a new instance \(G'(V',E',s,s_1,t+1)\) as follows: \[V' = V \cup \{s_1\} \cup \{s_{11}, s_{12}, \dots, s_{1t}\}\] \[E' = E \cup \{(s_1,v) \mid \forall v \in V'\setminus\{s_1\}\}\] That is, we introduce \(t+1\) many new vertices: a vertex \(s_1\) and \(t\) degree one many vertices \(s_{11}, s_{12}, \dots, s_{1t}\). The vertex \(s_1\) is made adjacent to every other vertex in \(V'\) (i.e., \(s_1\) is a universal/globally connected vertex), while each \(s_{1i}\), for \(1 \le i \le t\), is connected only to \(s_1\). Since \(|V'| = |V| + t + 1\) and \(|E'| = |E| + |V| + t\), the construction can clearly be made in polynomial time. Also, notice \(s_1\) is adjacent to every other vertex of \(G'\), the singleton set \(\{s_1\}\) is a dominating set of \(G'\). Hence, the domination number of \(G'\) is \(1\).

Further, note that the diameter of the constructed graph is bounded by \(2\), therefore, we have-

5 An XP Algorithm Parameterized by (vertex) Distance to Path↩︎

Here in this section we have a modulator set of \(M\) of atmost \(k\) many vertices and a path \(P\) of \(n\) many vertices. We build an algorithm sequentially for this special graph structure. Initially, for the exposition, we provide a clear algorithm for the case when \(k\) (size of the path modulator) is 1 and then use this algorithm (essentially a \(\mathsf{DP}\) procedure to solve the general case in XP time). Note that, we provide these algorithms for the case when the information initially resides with a modulator vertex, finally in the end we argue why the other case is not drastically different from this.

Throughout this section, we use \(P=\{p_1,p_2,\cdots, p_{|P|}\}\) to denote the path that results when we delete all the modulator vertices and \(M\) to denote all the modulator vertices. Hence \(E(G)=\{(u,v)|u,v \in M\} \cup \{(u,v)|u,v \in P\} \cup \{(u,v)|u \in M, v \in P\}\) and \(V(G)=V(M)\cup V(P)\).

5.1 Case 1(\(k=1\))↩︎

Given \(M=\{v\}\) and a path \(P\) of \(n\) vertices. We need to find an optimal broadcasting protocol for \(G[M \cup P]\). Since we have a path and an additional vertex \(v\) (that is adjacent to some of the vertices in the path), we may assume that whenever a vertex of the path is informed from \(v\) (assuming \(v\) as the source vertex), it transmits the information in the next step to an adjacent uninformed vertex on the path .

Covering Analogy: Note that informing a vertex in the path at a step \(i\), will help to transmit the information to the \(t-i\) vertices on one side and the \(t-i-1\) vertices on the other. Therefore, the problem of asking if the entire path can be informed in \(t\) many steps is same as asking if the entire path can be covered by paths of length \(1,2,4,6,8,\cdots 2t-2\) by placing their central vertex at one of the neighbors of \(v\).
Roughly this covering analogy is what we follow for the rest of the results in this section.

To give a 2-factor approximation algorithm, first note-

Therefore, we have, from the previous observations, that the entire path can be covered by informing some vertices in the first \(t\) steps out of the total \(2t\) steps. To find the exact vertices who are informed in the first \(t\) steps, we use a simple greedy procedure.
We proceed by placing a path of length \(2t-1\) centered at the rightmost neighbor of \(v\) that allows for all the uninformed vertices to the left of \(v\) to lie within \(t-1\) vertex distance. We do this iteratively by placing at most \(t\) many paths of length \(2t-1\). This completes our greedy algorithm.

We now argue that this greedy procedure is correct and that it achieves the claimed factor. Let \(T_{\text{opt}}\) be the optimal broadcast time, i.e. the fewest steps in which \(v\) can inform the whole path. By Observations 3 and 4, we may assume every path we use in the covering has length \(2T_{\text{opt}}-1\). In other words, once a neighbor of \(v\) is informed, it can reach up to \(t^\ast\) vertices on each side.

The key point is that greedy choice is always safe.

We now sketch how this idea can be extended when the path modulator size is \(k\). For this, we provide an XP-algorithm. Essentially in the extra “XP" time, we guess”how" the modulator vertices are informed. Once this is done, we provide a similarity sketch between the case where \(k=1\) and when \(k\) is arbitrary.

5.2 Case 2(\(k\ge 2\))↩︎

In this section, we use the same analogy of covering the path using subpaths as in the previous case. Further, for the case where \(k=1\), the center of all the subpaths were informed only through the single modulator vertex. However, in the case where \(k\geq 2\), the sub paths can belong to different vertices in the modulator depending on who informed the center vertex of the sub paths. To distinguish a sub path belonging to a vertex \(m_i\) in the modulator from a sub path belonging to a vertex \(m_j\) in the modulator, we use the notation - \(SP(m_i)\) to mean all the sub paths that belong to \(m_i\) (i.e. resulting from \(m_i\) informing a vertex in the path \(P\) which becomes the center vertex in the corresponding sub path).

In this case, an information can be transmitted from modulator to path vertices or from a path to modulator vertices. This is the crucial difference between the two cases (otherwise, the algorithm would have been “almost" identical). This now forces us to consider some paths that are centered at a vertex and is used to cover a vertex in the path that will in turn transmit the information to a modulator vertex. This change forces us not to assume that all the paths are of the same length \(2t-1\). However, note that there can be at most \(k\) many such paths (possibly belonging to different vertices in the modulator). Even an exhaustive search over all the cases of placement of these”type” of paths would be bounded by \(n^{f(k)}\), i.e. XP.

Guessing all necessary information: For each modulator vertex \(m_i\), we guess a tuple describing how and when it first receives the information, as follows. First, we guess the time \(t_i^{\rightarrow} \in \{1, \dots, t\}\) at which \(m_i\) is informed, which lies within the first \(t\) steps. Second, we guess the source of this information: \(m_i\) may be informed either by a vertex of the path \(P\) or by another modulator vertex, and we guess which of the two cases occurs. Third, depending on this choice, we guess the informing vertex \(v_i\) itself, so that \(v_i \in V(P)\) in the first case and \(v_i\) is a modulator vertex in the second. Fourth, we guess the vertex \(vm_i\) in the modulator, whose subpath covers \(v_i\). Fifth, we guess the vertex \(u_i \in V(P)\) that lies at the center of the subpath associated with \(vm_i\). Finally, we guess the time \(t_i^{\leftarrow}\) at which \(u_i\) is first informed by \(vm_i\).

Once this is done, consider the guess that corresponds to the optimal case. According to the guess, we assign a sub path belonging to the guessed modulator vertex \(vm_i\) at the guessed vertex \(u_i\) and transmit the information to either direction, finally reaching \(v_i\) by the time \(t_i^{\rightarrow}-1\) and transmitting the information to \(m_i\) at the time \(t_i^{\rightarrow}\). Now, by loosing the same number of sub paths (across all the \(SP(m_i)'s\)) to inform the modulator vertices, we have also covered a super set of vertices in the path \(P\) when compared to the covering in the optimal case restricted to the paths centered at \(u_i\)’s. Now we are ready to start the \(\mathsf{DP}\) procedure to cover the remaining vertices of the path \(P\). \[\mathsf{DP}(n_1,n_2,\cdots, n_k, p_i)=1\]

If the vertices till \(p_i\) (in \(P\), the vertices from \(p_1\) till \(p_i\)) can be covered by \(n_j\) many sub paths of length \(2t-1\) belonging to \(SP(m_j)\) \(\forall j\in[k]\), where \(n_j\leq |SP(m_j)|\)-{the paths used to inform the modulator vertices} (the reduction in the amount is basically because, the reduction amount is exactly the many times we used the modulator vertex \(m_j\) to inform something in the path when we guessed and the remaining amount is the number of times we can inform an un informed modulator vertex within the first \(t\) time). The \(\mathsf{DP}\) entry is 0 otherwise.

The \(\mathsf{DP}\) entries are updated by checking if a “certain” number of paths belonging to “certain” many modulator vertices is enough top cover the path \(P\) till a “certain” vertex, to achieve which, we essentially check (consult the previously stored information/\(\mathsf{DP}\) entry) if it was possible to cover the path till a previous vertex using all but one available sub paths and then cover the excess with the additional path. We now provide the formal \(\mathsf{DP}\) update step- \[\mathsf{DP}(n_1,n_2,\cdots, n_k, p_i)=1\] \[\iff\]

1. ( \(p_i\) already covered by the guessing phase) the interval \([p_1,p_i]\) is already contained in the coverage produced by the (at most) \(k\) sub-paths used in the initial step to inform the modulator vertices, using at most \(n_j\) paths of \(SP(m_j)\) for each \(j\) from that step, or

2. There exists \(j\in[k]\), \(l<i\) and a sub-path in \(SP(m_j)\) such that \[\mathsf{DP}(n_1,\dots,n_{j-1},\,n_j-1,\,n_{j+1},\dots,n_k,\;p_{i-l})=1, (l<i),\] such that placing the sub path in \(SP(m_j)\) centered at some adjacent vertex of \(m_j\) (located between \(p_{i-l-2t}\) and \(p_{i}\)) would result in covering the portion of \(P\) from \(p_1\) and \(p_i\).

For the runtime, since we are making \(n^{5}\) many guesses for each vertex in the modulator and finally solving a \(DP\) that has \(n^k\) entry at each of the \(|p|\) vertices (which requires iterating over \(n\) choices of \(l\) and \(j\)), we have the runtime bounded by \(n^{\mathcal{O}(k)}\). Hence, we have an XP algorithm.

6 An FPT Additive Approximation Algorithm Parameterized by (vertex) Distance to Clique↩︎

We fix a clique modulator \(M\) with \(|M|=k\) and let \(C=V\setminus M\), \(|C|=n\).

6.1 Structural observation↩︎

Because \(C\) is a clique, once \(j\geq\) 1 of its vertices are informed, the remaining vertices of \(C\) can all be informed within \(\lceil \log_2(n-k)\rceil\) further rounds by doubling. Hence the only nontrivial bottleneck is getting information into and out of the small side \(M\). In particular:

This observation is what lets us avoid branching over the whole clique: we only need to guess and order a set of size \(O(k)\) inside \(C\), and then use color coding to locate, among the \(\binom{n}{O(k)}\) candidates, a correctly ordered and positioned witness set, all in FPT time.

6.2 High-level description of the algorithm↩︎

We first treat the case where a single modulator vertex holds the initial information; we then show how the general case reduces to this one. We further split the algorithm into two regimes, based on the relation between \(n\) (the clique size) and \(k\) (the modulator size):

• Case 1: \(k \cdot 2^k < n\)

• Case 2: \(k \cdot 2^k \geq n\)

Part of the construction is common to both regimes, so we describe it first.

Consider the modulator set \(M\). We guess a partition \(\mathcal{P} = \{P_1, P_2, \dots, P_{|\mathcal{P}|}\}\) of \(M\) according to the round in which each vertex is informed: two modulator vertices lie in the same part \(P_i\) iff they are informed in the same round.

We also guess the subset \(S \subseteq M\) of modulator vertices that are informed directly by a vertex of \(C\). For every vertex of \(M \setminus S\), we additionally guess the specific modulator vertex that informs it (since such vertices are informed from within \(M\)).

This completes the common part of the algorithm. We now describe each regime.

6.2.1 Algorithm for Case 1↩︎

Here \(k \cdot 2^k \leq n\), i.e. \(\log k + k \leq \log n \leq T_{\text{opt}}\) (the optimum time). So there is ample time to first inform some \(k\) vertices of the clique and then use them to inform all of \(M\).

For each part \(P_i\), fix a matching \(M_i\) between \(S \cap P_i\) and vertices of \(C\) that saturates \(S \cap P_i\). Once every clique vertex used in one of these matchings is informed, the modulator set can be informed in the next \(|\mathcal{P}|\) rounds by processing the parts \(P_1, P_2, \dots\) in order, one per round: within round \(i\), the vertices of \(S \cap P_i\) are informed via the matching \(M_i\) from their matched partners in \(C\), and the remaining vertices of \(P_i\) are informed from the modulator vertices that were guessed to inform them (Provided the initial guesses are correct).

The full broadcasting procedure is:

1. Inform two vertices of the clique in the first 2 rounds.

2. The first of these two vertices runs the procedure above (Observation 6).

3. The second vertex greedily propagates the information to all unmatched vertices of \(C\) (taking time \(O(\log n)\)).

Since the two branches run in parallel, the whole graph is broadcasted in time \(\max(\log n, \log k +k) + 2 \leq T_{\text{opt}} + 2\). This gives a \(+2\) approximation in this regime.

6.2.2 Algorithm for Case 2↩︎

Here \(n \leq k \cdot 2^k\), so the time required to broadcast the whole graph satisfies \(\log n + k \leq 2k + \log k = O(k)\). This means we can afford to guess the full partition of \(M\) and the exact round at which each part is informed.

Before describing the algorithm, note that every vertex of \(C\) can be assigned uniquely to a vertex of \(M\): iteratively, a clique vertex inherits the modulator assignment of whichever vertex first informed it and if a vertex in the clique is informed by a modulator vertex, it is assigned to the same modulator vertex.This partitions \(C\) into sub-cliques, one or more per modulator vertex (a single modulator vertex may seed several sub-cliques if it informs multiple clique vertices that later inform others clique vertices).

We guess the following:

1. For each vertex of \(M \setminus S\), we are guessing, which earlier-informed modulator vertex informs it.

2. A partition of \(S\) into subsets \(S_1, \dots, S_d\), where each \(S_i\) is informed (in possibly different rounds) by a single vertex \(s_i \in C\). Since two modulator vertices informed in the same round cannot share an informer, we require \(|S_i \cap P_j| \leq 1\) for all \(i, j\).

3. Which of the vertices in \(S_{\text{direct}} = \{s_i : i \in [d]\}\) are informed directly by a modulator vertex, rather than by another clique vertex. Call this subset \(M_{S_{\text{direct}}} \subseteq S_{\text{direct}}\).

4. The round \(t_{s_i}\) at which each \(s_i\) is informed.

5. For each \(s_i \in M_{S_{\text{direct}}}\), guess the modulator vertex \(m_i\) that informs it directly.

6. For each \(s_i \in S_{\text{direct}} \setminus M_{S_{\text{direct}}}\), guess which sub-clique it belongs to (two such vertices may lie in the same or different sub-cliques).

7. For each of the (at most \(k\)) sub-cliques identified in step 6, guess the modulator vertex is associated with.

8. For each such sub-clique, guess the round at which its first vertex received the information from that modulator vertex.

The feasibility of a guess is not mentioned here, but informally, a guess is feasible/realizable if there are no two vertices in the graph that demand to be informed at the same time/round and more precisely if it is possible to inform the vertices at the exact round they are guessed to be informed (which can be checked in poly time for each guess).

With these guesses fixed, we run a color-coding procedure:

1. The number of vertices \(s_i\) is at most \(k\) (more precisely \(d\)), and the number of sub-cliques guessed in step 6 is at most \(k\)(more precisely, say \(g\leq k\)). So there are at most \(d + g \leq 2k\) target vertices i.e. the \(s_i\)’s and the first-informed vertices of the guessed sub-cliques that we must correctly locate among the \(n\) vertices of \(C\). Order these target vertices arbitrarily as \(ver_1, \dots, ver_{d+g}\).

2. Randomly color the vertices of \(C\) with \(d + g\) colors.

3. Given correct guesses, the probability that \(ver_i\) receives color \(i\) for every \(i \in [d+g]\) is at least \((d+g)^{-(d+g)} \geq k^{-k}\).

If the guesses and the coloring are both correct, we can, in polynomial time, select one vertex from each relevant color class satisfying the required adjacency conditions, e.g., if \(ver_i\) plays the role of \(s_i\), we need a vertex of color \(i\) adjacent to all of \(S_i\) and to the appropriate vertex of \(M\); if \(ver_i\) plays the role of a sub-clique’s first informed vertex, we need a vertex of color \(i\) adjacent to the corresponding modulator vertex \(m_j\); and so on.

Hence, conditional on correct guesses and correct coloring, we obtain a broadcasting schedule that informs all of \(M\) within time \(T_{\text{opt}}\), mimicking the optimal protocol:

Using Observation 7, we build the full algorithm exactly as in Case 1:

1. In 2 rounds, inform a vertex \(v \in C\) not already informed by the procedure of Observation 7.

2. Run the guessing-and-color-coding procedure above, which informs all vertices of \(M\) (and some vertices of \(C\)) as described.

3. Let \(v\) propagate the information greedily through the remaining, not-yet-informed vertices of \(C\).

Since the two procedures run on disjoint vertex sets and hence in parallel, the total number of rounds is \(2 + \max(T_{\text{opt}}, \log n) \leq T_{\text{opt}} + 2\).

The color-coding step succeeds with probability at least \(k^{-k}\) (conditional on correct guesses), so the algorithm can be derandomized using a \(k\)-perfect hash family, yielding a deterministic FPT additive approximation.

6.2.2.1 Runtime analysis.

The number of guesses is bounded by \(2^{O(k \log k)}\), and the derandomization step also runs in time \(2^{O(k \log k)}\). Hence the total runtime is \(2^{O(k \log k)} \cdot \text{poly}(n + k)\).Therefore, we have the theorem-

7 Polynomial Time Algorithm on Polar graphs↩︎

Therefore, we have,

References↩︎