Scale-Free Spanning Trees and Their Application in Genomic Epidemiology

Abstract

We study the algorithmic problem of finding the most “scale-free-like” spanning tree of a connected graph. This problem is motivated by the fundamental problem of genomic epidemiology: given viral genomes sampled from infected individuals, reconstruct the transmission network (“who infected whom”). We use two possible objective functions for this problem and introduce the corresponding algorithmic problems termed m -SF (-scale free) and s -SF Spanning Tree problems. We prove that those problems are APX- and NP-hard, respectively, even in the classes of cubic and bipartite graphs. We propose two integer linear programming (ILP) formulations for the s -SF Spanning Tree problem, and experimentally assess its performance using simulated and experimental data. In particular, we demonstrate that the ILP-based approach allows for accurate reconstruction of transmission histories of several hepatitis C outbreaks.

1. Introduction

Viral outbreaks continue to be major causes of morbidity and mortality. The ongoing pandemic of the coronavirus SARS-CoV-2 (Huang et al., 2020) is a vivid example, but long-standing epidemics of HIV, hepatitis B virus, and hepatitis C virus (HCV) are hardly less damaging (Kilmarx, 2009; Hajarizadeh et al., 2013). Viral epidemics are complex processes defined by evolutionary dynamics of pathogens and social dynamics of susceptible populations (e.g., individual behaviors, social interactions, and mobility patterns).

Recent advances in sequencing technologies invigorated the field of genomic epidemiology (Armstrong et al., 2019; Knyazev et al., 2020) that aims to use viral genomic data to understand the epidemiological dynamics of pathogens. The fundamental algorithmic problem of genomic epidemiology could be formulated as follows:

Given viral genomes sampled from n infected individuals, infer a transmission network indicating who of them infected whom (Knyazev et al., 2020). If each individual is supposed to be infected only once, then a transmission network is a tree called a transmission tree.

This problem has been approached by a variety of methods (Jombart et al., 2011, 2014; Sledzieski et al., 2019; Wertheim et al., 2014; Campo et al., 2016; De Maio et al., 2016; Klinkenberg et al., 2017; Skums et al., 2018). One family of methods is based on the so-called network approach. It is particularly popular among researchers of HIV and HCV and has been adopted as a standard methodology for outbreak investigations carried out by the CDC (Wertheim et al., 2014; Campo et al., 2016; Campbell et al., 2017; Kosakovsky Pond et al., 2018; Ramachandran et al., 2018; Ragonnet-Cronin et al., 2019). This approach usually consists of two stages. First, a weighted relatedness graph G_R is constructed. Its vertices represent infected hosts, and edges connect the hosts whose viral populations are close to each other according to a selected population genetics measure. Often G_R itself supplies enough information for epidemiologists and provides a fast and scalable alternative to phylogenetic trees when applied to next-generation sequencing (NGS) data (Wertheim et al., 2014; Campo et al., 2016; Ragonnet-Cronin et al., 2019). However, usually it contains many edges that do not represent actual transmissions. Thus, at the second stage, the transmission tree is inferred as the spanning tree of G_R.

Under the maximum parsimony criterion, the most likely transmission network is a minimum spanning tree of G_R (Jombart et al., 2011). However, experiments demonstrated that this approach is not accurate (Jombart et al., 2014). Furthermore, genomic data alone often do not allow to resolve ambiguities in transmission tree inference, and incorporation of additional evidence is necessary (Jombart et al., 2014; Villandre et al., 2016; Jha et al., 2017). Such evidence usually comes in the form of epidemiological information, such as sample collection times and exposure intervals. However, HIV, HCV, and many other infections tend to be initially asymptomatic, and consequently, sampling times may not accurately reflect the infection times. In addition, in outbreaks with high transmission rates (e.g., HIV/HCV among injection drug users), susceptible hosts are almost constantly exposed to the virus, which makes exposure intervals useless. Another important drawback of many existing methods is their implicit assumption that transmission tree edges are independent. In reality, it is not the case, as, for example, certain hosts (so-called superspreaders) infect more people than an average person (Galvani and May, 2005).

Skums et al. (2018) proposed an alternative approach. It is known that for viruses, whose transmissions are associated with behavioral risk factors, their transmission trees have properties of so-called scale-free graphs (Leigh Brown et al., 2011; Wertheim et al., 2014). Those graphs have specific features, including power-law degree distribution, small diameter, and the presence of high-degree vertices (hubs). This observation gives rise to the following informally defined algorithmic problem (scale-free spanning tree problem): find the most “scale-free-like” spanning tree T of the graph G_R. In addition, constraints on the weight of T could be imposed. This approach was the basis of the Bayesian framework and the Markov Chain Monte Carlo algorithm for the transmission network inference described by Skums et al. (2018) and implemented as a tool called QUENTIN. Although QUENTIN is efficient in practice, it is a heuristic, and the questions about computational complexity and possibility of the exact solution of the problem were left open.

In this article, we present the first detailed study of the scale-free spanning tree problem. Our major contributions are as follows.

1. (1)

   We propose two rigorous formulations of the scale-free spanning tree problem further referred to as m-SF Spanning Tree and s-SF Spanning Tree problems. They are based on two related objective functions and, to the best of our knowledge, have not been previously studied.

2. (2)

   We establish the computational complexity of both problems by demonstrating that they are NP-hard or APX-hard, even when restricted to cubic graphs and bipartite graphs.

3. (3)

   We propose two integer linear programming (ILP) formulations for the problems, and perform computational experiments to assess their performance using simulated data. Then we apply an ILP approach to real genomic data from several epidemiologically curated HCV outbreaks investigated by the CDC (Campo et al., 2016; Skums et al., 2018) and demonstrate that it allows for accurate inference of transmission trees.

2. Preliminaries

2.1. Problem formulations

We consider only finite undirected simple graphs and use standard graph-theoretic terminologies, see, for example, Chartrand et al. (2016). Let $G=\left(V,E\right)$ be a connected graph. For a vertex $x\in V\left(G\right)$ , the neighborhood $N_G\left(x\right)$ of x is the set of all vertices that are adjacent to x in G. The degree of x is defined as ${deg}_{G}x=\left|N_G\left(x\right)\right|$ . Several definitions of scale-free graphs of different degrees of mathematical rigor are known in a literature. We utilize the rigorous combinatorial characterization that has been introduced by Li et al. (2005) using the so-called s-metric of a graph. This graph invariant is defined as follows: $$s\left(G\right)={\sum }_{uv\in E\left(G\right)}{deg}_{G}u{deg}_{G}v.$$(1)

The same parameter is known in mathematical chemistry as second Zagreb index (Das and Gutman, 2004; Borovicanin et al., 2017). Li et al. (2005) demonstrated that a higher s-metric indicates with high probability the presence of most of the expected properties of scale-free graphs. The intuition behind these results is that in a graph with a high s-metric, a large number of edges should be incident to high-degree vertices, thus forcing them to resemble preferential attachment graphs—a standard Barabási and Albert (1999) model for scale-free networks. Therefore, another mathematical chemistry parameter called the first Zagreb index (Borovicanin et al., 2017) or m-metric also can serve as a measure of “scale-freeness” of a graph:

Thus, we can formulate m-SF Spanning Tree and s-SF Spanning Tree problems: given a connected graph G, find the spanning tree T of G such that $m\left(T\right)$ (respectively, $s\left(T\right)$ ) is maximal. The respective maximum values of $m\left(T\right)$ and $s\left(T\right)$ are called first and second SF-dimensions of G and denoted by ${\tau }_1\left(G\right)$ and ${\tau }_2\left(G\right)$ . By $T^{sopt}$ and $T^{mopt}$ , we denote an s-optimal tree and an m-optimal tree of G, respectively.

A somehow related problem has been studied by Kincaid et al. (2016): find a spanning subgraph with prescribed vertex degrees such that its s-metric is maximum. This problem is polynomially solvable in general, but becomes NP-hard, when the output spanning subgraph is required to be connected.

2.2. Mathematical preliminaries

2.2.1. Subgraph counting

Here we establish the characterizations for the m-metric and s-metric in terms of numbers of small subgraphs in a graph. This technique is used to establish complexity results in Section 3 and ILP formulations in Section 4.

Proposition 1. For any graph G, $$m\left(G\right)=2{\gamma }_2\left(G\right)+2{\gamma }_1\left(G\right),s\left(G\right)=3{\gamma }_{\Delta }\left(G\right)+{\gamma }_3\left(G\right)+2{\gamma }_2\left(G\right)+{\gamma }_1\left(G\right),$$

where ${\gamma }_{\Delta }\left(G\right)$ is the number of triangles and ${\gamma }_t\left(G\right)$ is the number of paths of length t in G, respectively.

Proof. We prove only the second equality, the first one can be proved similarly. Let $A=\left[a_{ij}\right]$ be the adjacency matrix of G and d be its degree vector. We have $s\left(G\right)=\frac{1}{2}{d}^T\cdot A\cdot d$ and $d=A\cdot 1$ , where . Therefore $$s\left(G\right)=\frac{1}{2}{1}^T\cdot A^3\cdot 1=\frac{1}{2}{\sum }_{i=1}^n{\sum }_{j=1}^n{a}_{ij}^{\left(3\right)},$$

where denotes -entry in the matrix A³.

It is known that $a_{ij}^{\left(3\right)}$ equals the number of walks of length 3 between vertices i and j. Thus, $s\left(G\right)$ is equal to one-half of the total number of three-walks in G. An edge $v_1{v}_2$ produces exactly two such walks: $W_{11}=\left(v_1,v_2,v_1,v_2\right)$ and $W_{12}=\left(v_2,v_1,v_2,v_1\right)$ . Each 2-path $\left\{v_1{v}_2,v_2{v}_3\right\}$ produces four 3-walks: $W_{21}=\left(v_1,v_2,v_3,v_2\right)$ , $W_{22}=\left(v_2,v_3,v_2,v_1\right)$ , $W_{23}=\left(v_2,v_1,v_2,v_3\right)$ , and $W_{24}=\left(v_3,v_2,v_1,v_2\right)$ . Each 3-path $\left\{v_1{v}_2,v_2{v}_3,v_3{v}_4\right\}$ produces two 3-walks: $W_{31}=\left(v_1,v_2,v_3,v_4\right)$ and $W_{32}=\left(v_4,v_3,v_2,v_1\right)$ . Finally, each triangle with vertex set $\left\{v_1,v_2,v_3\right\}$ produces six 3-walks: $W_{\Delta 1}=\left(v_1,v_2,v_3,v_1\right)$ , $W_{\Delta 2}=\left(v_1,v_3,v_2,v_1\right)$ , $W_{\Delta 3}=\left(v_2,v_3,v_1,v_2\right)$ , $W_{\Delta 4}=\left(v_2,v_1,v_3,v_2\right)$ , $W_{\Delta 5}=\left(v_3,v_1,v_2,v_3\right)$ , and $W_{\Delta 6}=\left(v_3,v_2,v_1,v_3\right)$ . As every three-walk of G has one of these forms, the statement of the lemma follows.□

2.2.2. Neighbor switching

This is a tree rearrangement technique that is used for obtaining structural and complexity results. Let T be a tree and $\left(u,v\right)$ be a pair of distinct vertices $u,v\in V\left(T\right)$ , where ${deg}_{T}u=p\ge 2$ and ${deg}_{T}v=t\ge 2$ . We denote the unique $u-v$ path in T by $P_T\left(u,v\right)$ , and neighbors of u and v laying on $P_T\left(u,v\right)$ by $u^{+}$ and $v^{-}$ , respectively. In case u and v are not adjacent, the neighbor of $u^{+}$ distinct from u and laying on $P_T\left(u,v\right)$ is denoted by $u^{++}$ . Let $A=N_T\left(u\right)\setminus \left\{u^{+}\right\}=\left\{a_1,\dots ,a_{p-1}\right\}$ , and let the set $N_T\left(v\right)\setminus \left\{v^{-}\right\}$ be partitioned into two subsets $B=\left\{b_1,\dots ,b_q\right\}$ and $C=\left\{c_1,\dots ,c_r\right\}$ , where $B\ne$ . Furthermore, let ${deg}_T{u}^{+}=\alpha$ and ${deg}_T{v}^{-}=\beta$ . Define numbers D_A, D_B, and D_C as follows: $$D_A={\sum }_{i=1}^{p-1}{deg}_T{a}_i,D_B={\sum }_{j=1}^q{deg}_T{b}_j,D_C={\sum }_{k=1}^r{deg}_T{c}_k.$$(3)

Given the pair $\left(u,v\right)$ , the neighbor switch $S_{v\to u}^B$ is a transformation producing a new tree $\tilde{T}$ from T by replacing the edges $v{b}_1,\dots ,v{b}_q$ with new edges $u{b}_1,\dots ,u{b}_q$ (Fig. 1). This operation changes only degrees of the vertices u and v, namely ${deg}_{\tilde{T}}u=p+q$ , ${deg}_{\tilde{T}}v=r+1$ .

FIG. 1.

Neighbor switch.

Lemma 2. Suppose that $S_{v\to u}^B\left(T\right)=\tilde{T}$ . If $p\ge r+1$ , $D_A>D_C$ and, in case u and v are not adjacent, additionally $\alpha \ge \beta$ , then $s\left(\tilde{T}\right)>s\left(T\right)$ .

Proof. We prove lemma when u and v are not adjacent, that is, $u\ne v^{-}$ and $v\ne u^{+}$ (the proof for the other case is similar). Define by X (resp., Y) the set of edges of T (resp., $\tilde{T}$ ) incident to u or v. Let us denote by $\lambda \left(X\right)$ (resp., $\tilde{\lambda }\left(Y\right)$ ) the contribution to $s\left(T\right)$ (resp., $s\left(\tilde{T}\right)$ ) from the edges of X (resp., Y). Then $$s\left(\tilde{T}\right)-s\left(T\right)=\tilde{\lambda }\left(Y\right)-\lambda \left(X\right).$$(4)

Using Equation (3) one can easily calculate $$\begin{array}{c}\lambda \left(X\right)={deg}_{T}u{deg}_T{u}^{+}+{deg}_T{v}^{-}{deg}_{T}v+{\sum }_{i=1}^{p-1}{deg}_{T}u{deg}_T{a}_i+{\sum }_{j=1}^q{deg}_{T}v{deg}_T{b}_j\\ +{\sum }_{k=1}^r{deg}_{T}v{deg}_T{c}_k=p\alpha +\beta t+p{D}_A+t{D}_B+t{D}_C.\end{array}$$

After substituting $t=q+r+1$ , we obtain $$\lambda \left(X\right)=p\alpha +\beta q+\beta \left(r+1\right)+p{D}_A+q{D}_B+\left(r+1\right)D_B+q{D}_C+\left(r+1\right)D_C.$$(5)

Similarly, $$\tilde{\lambda }\left(Y\right)=p\alpha +q\alpha +\beta \left(r+1\right)+p{D}_A+q{D}_A+p{D}_B+q{D}_B+\left(r+1\right)D_C.$$(6)

Using equalities (4)–(6) we obtain $$\begin{array}{c}s\left(\tilde{T}\right)-s\left(T\right)=\tilde{\lambda }\left(Y\right)-\lambda \left(X\right)=q\alpha +q{D}_A+p{D}_B-\beta q-\left(r+1\right)D_B-q{D}_C\\ =q\left(\alpha -\beta \right)+D_B\left(p-r-1\right)+q\left(D_A-D_C\right).\end{array}$$(7)

Since $\alpha \ge \beta$ and $p\ge r+1$ , it follows that $q\left(\alpha -\beta \right)+D_B\left(p-r-1\right)\ge 0$ . On the contrary, since $q\ge 1$ and $D_A>D_C$ , we have $q\left(D_A-D_C\right)>0$ and therefore $s\left(\tilde{T}\right)-s\left(T\right)>0$ .

If $B=N_T\left(v\right)\setminus \left\{v^{-}\right\}$ , then the neighbor switch produces a tree $\tilde{T}$ with v being a leaf. In this case $S_{v\to u}^B$ is a total neighbor switch. For our goals it suffices to prove the following corollary.

Corollary 3. If $\tilde{T}$ is obtained from T by a total neighbor switch $S_{v\to u}^B$ and, in case of u and v not being adjacent, additionally $\alpha \ge \beta$ or $p\ge \beta$ , then $s\left(\tilde{T}\right)>s\left(T\right)$ .

Proof. We check that all conditions of Lemma 2 are satisfied for the total neighbor switch. Indeed, since $D_A\ge p-1\ge 1$ (recall ${deg}_{T}u=p\ge 2$ ) and $D_C=r=0$ , we have $D_A>D_C$ and $p\ge r+1$ . If u and v are not adjacent, we still require that $\alpha \ge \beta$ , as in Lemma 2. However, this condition can be replaced if we rewrite Equation (7) as follows: $$s\left(\tilde{T}\right)-s\left(T\right)=q\left(\alpha -\beta \right)+D_B\left(p-1\right)+q{D}_A=q\left(\alpha +D_A-\beta \right)+D_B\left(p-1\right).$$

Note that the latter expression is positive in case of $p\ge \beta$ , since $\alpha \ge 2$ and $D_A\ge p-1\ge 1$ .

In the same way we can compare the trees T and $\tilde{T}=S_{v\to u}^B\left(T\right)$ in terms of their m-metrics.

Lemma 4. Suppose that $S_{v\to u}^B\left(T\right)=\tilde{T}$ and $p>r+1$ . Then $m\left(\tilde{T}\right)>m\left(T\right)$ .

Proof. The idea is similar to the proof of Lemma 2. Since the neighbor switch changes only degrees of vertices u and v, $m\left(\tilde{T}\right)-m\left(T\right)={deg}_{\tilde{T}}^{2}u+{deg}_{\tilde{T}}^{2}v-{deg}_T^{2}u-{deg}_T^{2}v=2q\left(p-r-1\right)$ , which proves the lemma, since $q\ge 1$ .

For further results we need weaker modifications of Lemmas 2 and 4 for the case ${deg}_{T}u=p\ge 1$ (and therefore $D_A\ge 0$ ). Recall ${deg}_{T}v=t\ge 2$ since we still require at least one vertex to switch.

Lemma 5. Suppose $\tilde{T}$ is obtained from T by a total neighbor switch $S_{v\to u}^B$ , then the following propositions hold:

(a) $m\left(\tilde{T}\right)\ge m\left(T\right)$ ;

(b) $s\left(\tilde{T}\right)\ge s\left(T\right)$ (unless u and v are not adjacent with $\alpha <\beta$ ).

Now we consider a special case, when u is a vertex of maximum degree in T and all vertices in $N_T\left(v\right)\setminus \left\{v^{-}\right\}$ are leaves. In addition, let $B,C\ne$ . We introduce a double neighbor switch $S_{v\to u,u^{+}}^{B,C}\left(T\right)=S_{v\to u^{+}}^C\left(S_{v\to u}^B\left(T\right)\right)$ . The reason to treat this two-step switch as a single operation is that the first switch itself might cause the descend of s-metric, however, the decrease would be compensated by the second switch.

Lemma 6. If $\hat{T}$ is obtained from T by a double neighbor switch $S_{v\to u,u^{+}}^{B,C}\left(T\right)$ , then $s\left(\hat{T}\right)>s\left(T\right)$ .

Proof. In case u and v are adjacent, that is, $u^{+}=v$ , a double switch $S_{v\to u,u^{+}}^{B,C}\left(T\right)$ gets reduced to the first neighbor switch $S_{v\to u}^B\left(T\right)$ , which produces a tree with a higher s-metric due to Lemma 2. Therefore, assume u and v are not adjacent. Consider the first switch and let $\tilde{T}=S_{v\to u}^B\left(T\right)$ . From Equation (7), since $D_B=q$ and $D_C=r$ , we obtain $$s\left(\tilde{T}\right)-s\left(T\right)=q\left(\alpha +D_A-\beta \right)+q\left(p-r-1\right)-qr.$$(8)

Next let $\hat{T}=S_{v\to u^{+}}^C\left(\tilde{T}\right)$ be obtained by the total neighbor switch. To avoid reassigning of notations we denote $D_E={\sum }_{w\in N_{\tilde{T}}\left(u^{+}\right)\setminus \left\{u^{++}\right\}}{deg}_{\tilde{T}}w$ and $\gamma ={deg}_{\tilde{T}}{u}^{++}$ . Other notations stay the same from the first switch. Again from Equation (7) we get $$s\left(\hat{T}\right)-s\left(\tilde{T}\right)=r\left(\gamma -\beta \right)+r\left(\gamma -1\right)+r{D}_E.$$(9)

Summation of Equations (8) and (9) gives $$s\left(\hat{T}\right)-s\left(T\right)=q\left(\alpha +D_A-\beta \right)+q\left(p-r-1\right)+r\left(\gamma +D_E-\beta -q\right)+r\left(\gamma -1\right),$$

where $D_A\ge p-1$ , $\alpha \ge 2$ , $\gamma \ge 2$ , and $D_E\ge {deg}_{\tilde{T}}u=p+q$ . Furthermore, since u is a vertex of maximum degree in T, $p\ge \beta$ and $p\ge q+r+1>r+1$ (recall $q,r>0$ ), which proves the lemma.

2.3. Bounds in terms of the maximum degree

There exist bounds for both SF-dimensions of a graph in terms of its order only (de Caen, 1998; Das, 2003; Das and Gutman, 2004). However, they are not particularly efficient, when used as ILP cuts. Here we provide the adjusted upper bounds that turned out to be more useful for that purpose. Let $\Delta \left(G\right)$ denote the maximum vertex degree of G and $S_{m,k}$ denote a double star, that is, a tree obtained from two disjoint stars $K_{1,m}$ and $K_{1,k}$ with m and k leaves, respectively, by adding an edge joining their central vertices.

Theorem 7. For any graph G of order $n\ge 2$ , $$\begin{array}{c}{\tau }_1\left(G\right)\le m\left(S_{\Delta \left(G\right)-1,n-\Delta \left(G\right)-1}\right)=2{\Delta }^2\left(G\right)+n^2-2n\Delta \left(G\right)+n-2,\\ {\tau }_2\left(G\right)\le s\left(S_{\Delta \left(G\right)-1,n-\Delta \left(G\right)-1}\right)=n\left(n-\Delta \left(G\right)-1\right)+{\Delta }^2\left(G\right).\end{array}$$

Proof. We provide the proof for the second SF-dimension only (the other proof is similar). Suppose $T^{sopt}$ is an s-optimal tree of G and $T^{sopt}\ne S_{\Delta \left(G\right)-1,n-\Delta \left(G\right)-1}$ . We prove the statement by performing a sequence of neighbor switches on $T^{sopt}$ , with each of them increasing s-metric, so that the resulting tree is $S_{\Delta \left(G\right)-1,n-\Delta \left(G\right)-1}$ .

Let u be a vertex of maximum degree in $T^{sopt}$ . Then for every v in $T^{sopt}$ follows ${deg}_{T^{sopt}}v\le {deg}_{T^{sopt}}u\le {deg}_{G}u\le \Delta \left(G\right)$ . Let $T:=T^{sopt}$ . We divide the sequence of neighbor switches into three stages.

Stage 1: For each vertex v with all vertices in $N_T\left(v\right)\setminus \left\{v^{-}\right\}$ (where $v^{-}\in P_T\left(u,v\right)$ ) being leaves, we either perform the total neighbor switch $T:=S_{v\to u}^B\left(T\right)$ or double neighbor switch $T:=S_{v\to u,u^{+}}^{B,C}\left(T\right)$ until the degree of u is not equal to $\Delta \left(G\right).$

One can observe that a double neighbor switch is needed to ensure that ${deg}_{T}u$ can be increased exactly to $\Delta \left(G\right)$ . Since ${deg}_{T}u$ increases after each switch, only the finite number of switches is required. In case the tree T obtained after the first stage differs from $S_{\Delta \left(G\right)-1,n-\Delta \left(G\right)-1}$ , we perform the second stage if there exist at least two vertices w₁ and w₂ in $N_T\left(u\right)$ with ${deg}_T{w}_1\ge {deg}_T{w}_2\ge 2$ or jump directly to Stage 3 otherwise.

Stage 2: For each distinct w₁ and w₂ in $N_T\left(u\right)$ with ${deg}_T{w}_1\ge {deg}_T{w}_2\ge 2$ perform a total neighbor switch $T:=S_{w_2\to w_1}^B\left(T\right)$ .

After each iteration, the number of vertices in $N_T\left(u\right)$ with degree at least two decreases by one. Thus, Stage 2 terminates after a finite number of switches leaving at most one vertex $w\in N_T\left(u\right)$ with degree at least two. Finally if T still differs from $S_{\Delta \left(G\right)-1,n-\Delta \left(G\right)-1}$ , the third stage is required.

Stage 3: While there exists vertex v in $N_T\left(w\right)\setminus \left\{u\right\}$ with ${deg}_{T}v\ge 2$ perform a total neighbor switch $T:=S_{v\to w}^B\left(T\right)$ .

Since the number of neighbors of w with degrees at least two decreases after each switch, Stage 3 terminates after finite number of steps with all neighbors of $w,$ except for u, being leaves, that is, $T=S_{\Delta \left(G\right)-1,n-\Delta \left(G\right)-1}$ . Note that each iteration of Stages 1–3 produces a tree with a higher s-metric due to Lemmas 2, 6 and Corollary 3.

3. Hardness Results

In this section, we study the computational complexity of both the m-SF and the s-SF Spanning Tree problem. The following known fact is used:

Theorem 8 (Kleitman and West, 1991). Any connected graph of order n with minimum vertex degree at least 3 has a spanning tree with at least $n∕4+2$ leaves.

We start by investigating the complexity of our problems for cubic graphs.

Theorem 9. The m-SF Spanning Tree problem is $APX$ -hard for cubic graphs.

Proof. Let G be a cubic graph on n vertices and T be a spanning tree with $\ell =\ell \left(T\right)$ leaves and $n_i=n_i\left(T\right)$ vertices of degree i, $i\in \left\{2,3\right\}$ . Then $$m\left(T\right)=\ell +4n_2+9n_3,$$(10)

with the numbers n_i satisfying the equalities $\ell +n_2+n_3=n$ and $\ell +2n_2+3n_3=2\left(n-1\right).$ Deriving n₂ and n₃ from these equalities gives us $$n_2=n+2-2\ell ,n_3=\ell -2.$$(11)

After substituting these expressions into Equation (10), we get $$m\left(T\right)=2\ell +4n-10.$$(12)

Thus, finding a spanning tree with maximum m-metric in this case is polynomially equivalent to finding a spanning tree with maximum number of leaves (MaxLeaf problem). For cubic graphs, the latter problem was shown to be APX-hard by Bonsma (2012). Thus, we prove the APX-hardness of the m-SF Spanning Tree problem by providing an L-reduction (Papadimitriou and Yannakakis, 1991) from MaxLeaf.

Given an optimization problem P and an instance I of this problem, we use $op{t}_P\left(I\right)$ to denote the optimum value of I, and $va{l}_P\left(I,S\right)$ to denote the value of a feasible solution S of instance I. Let A and B be two optimization problems. The problem A is said to be L-reducible to B if there exist polynomial-time computable functions f, g and constants $\alpha ,\beta >0$ such that

(L1) f maps any instance I of A to an instance $f\left(I\right)$ of B such that $op{t}_B\left(f\left(I\right)\right)\le \alpha \cdot op{t}_A\left(I\right)$ ;

(L2) for any instance I of A and a solution $S\prime$ of the instance $f\left(I\right)$ , g maps $S\prime$ to a solution S for I such that $|va{l}_A\left(I,S\right)-op{t}_A\left(I\right)|\le \beta \cdot |va{l}_B\left(f\left(I\right),S\prime \right)-op{t}_B\left(f\left(I\right)\right)|$ .

Let $T^{mopt}$ be an m-optimal spanning tree of G and ${\ell }^{\ast }$ be the maximum number of leaves in spanning trees of G. Note that ${\ell }^{\ast }\ge n∕4+2$ by Theorem 8, and therefore, $n\le 4{\ell }^{\ast }-8$ . Then using Equation (12) we get $${\tau }_1\left(G\right)=m\left(T^{mopt}\right)=2\ell \left(T^{mopt}\right)+4n-10\le 2{\ell }^{\ast }+16{\ell }^{\ast }-32\le 18{\ell }^{\ast }.$$

Moreover, for every spanning tree T of G we have $\frac{1}{2}|m\left(T\right)-m\left(T^{mopt}\right)|=|\ell \left(T\right)-{\ell }^{\ast }|$ . As a result, Equation (12) implies an L-reduction with identity mappings f and g and constants $\alpha =18$ and $\beta =\frac{1}{2}$ , thus proving the theorem.

Theorem 10. The s-SF Spanning Tree problem is $NP$ -hard for cubic graphs.

Proof. For the reduction, we use the following problem proved to be NP-complete by Lemke (1988):

Instance: A connected cubic graph G of order n.

Question: Is there a spanning tree of G without vertices of degree 2?

According to Equation (11), $n_2=n_2\left(T\right)=n+2-2\ell \left(T\right)$ . Thus, the answer for the problem's question is negative if n is odd. Hence, we concentrate only on the case when $n\ge 4$ is even, thus n₂ is even as well. We show that among all trees T of order n with $\Delta \left(T\right)\le 3$ , the trees without vertices of degree 2 have the highest s-metric. Indeed, the following claim holds:

Claim 11. If $\Delta \left(T\right)\le 3$ and $n\ge 4$ are even, then $s\left(T\right)\le 6n-15$ . The equality holds if and only if T has no vertices of degree 2.

Proof. If T has no vertices of degree 2, then Equation (11) implies $\ell =\ell \left(T\right)=\frac{n+2}{2}$ . Furthermore, $s\left(T\right)=3m_1+9m_3$ , where m₁ is the number of edges incident to a leaf and m₃ is the number of edges with both ends of degree 3. Obviously, $m_1=\ell$ and $m_3=n-1-\ell$ , thus yielding $s\left(T\right)=6n-15$ .

Now suppose that T has $n_2\ge 2$ vertices of degree 2. Let u and v be two vertices of degree 2 lying on a path $P_T\left(u,v\right)$ and ${deg}_T{u}^{+}\ge {deg}_T{v}^{-}$ . Iteratively applying a total neighbor switch $S_{v\to u}^B$ for all pairs of vertices u and v of degree 2, we obtain a tree with higher s-metric (due to Corollary 3) and without vertices of degree 2. This proves the claim. □

Thus, ${\tau }_2\left(G\right)=6n-15$ if and only if G has a spanning tree without vertices of degree 2. This concludes the proof.

Next, we consider bipartite graphs.

Theorem 12. The m-SF Spanning Tree and s-SF Spanning Tree problems are $NP$ -hard for bipartite graphs.

Proof. We present a polynomial-time reduction from the NP-complete 3-Dimensional Matching (3-DM) problem (Garey and Johnson, 1979):

Instance: Pairwise disjoint sets X, Y, Z of cardinality n, and a collection $ℳ$ of m three-element sets, where each $M\in ℳ$ includes exactly one element from each of X, Y, and Z.

Question: Is there a set of pairwise disjoint members of $ℳ$ (a perfect 3-dimensional matching), whose union is $X\cup Y\cup Z$ ?

Let $Q=\left(X,Y,Z,ℳ\right)$ be an instance of 3-DM. We construct a graph $G=G_Q$ on $3n+m+1$ vertices as follows. The vertex set of G is the disjoint union $\left\{r\right\}\cup A\cup B$ , where $A=ℳ$ , $B=X\cup Y\cup Z$ , and r is the special root vertex. The edge set includes all edges ra, $a\in A$ , as well as the edges Mx, My, and Mz for each $M=\left\{x,y,z\right\}\in A$ (Fig. 2). We may assume that G is connected. Note also that G is a bipartite graph with the parts A and $\left\{r\right\}\cup B$ .

For a vertex v of G and a subset $W\subseteq V\left(G\right)$ let us denote by $\left(v:W\right)$ the set of edges connecting v to vertices in W.

FIG. 2.

An example of the graph G for $n=3$ , $X=\left\{x_1,x_2,x_3\right\}$ , $Y=\left\{y_1,y_2,y_3\right\}$ , $Z=\left\{z_1,z_2,z_3\right\}$ , and $ℳ=\left\{\right\{x_1,y_2,z_1\},\left\{x_3,y_2,z_3\right\},\left\{x_2,y_1,z_1\right\},$ $\left\{x_1,y_2,z_3\right\},\left\{x_3,y_1,z_2\right\},\left\{x_2,y_3,z_1\right\}\}$ . Here each vertex labeled $\left\{p,q,r\right\}$ represents a set $\left\{x_p,y_q,z_r\right\}$ .

Lemma 13. There are spanning trees T₁ and T₂ in G, both containing all edges of $\left(r:A\right)$ , with $m\left(T_1\right)={\tau }_1\left(G\right)$ and $s\left(T_2\right)={\tau }_2\left(G\right)$ .

Proof. We provide the proof for the s-metric, the proof for the m-metric is similar. Among the optimal spanning trees of G, let T₂ be the one with the maximum number of edges from $\left(r:A\right)$ . We claim that T₂ contains all these edges.

Suppose for a contradiction that the set $C\subseteq A$ of all vertices that are adjacent to r in T₂ differs from A. Then there must be a vertex $b\in B$ with $P_{T_2}\left(r,b\right)$ having two edges, such that set $D=N_{T_2}\left(b\right)\cap \left\{A\setminus C\right\}$ is nonempty. By Lemma 5, since ${deg}_{T_2}{r}^{+}={deg}_{T_2}{b}^{-}$ and ${deg}_{T_2}r\ge 1$ , we can apply total neighbor switch $S_{b\to r}^D$ to construct a spanning tree $T{\prime }_2$ from T₂ with $s\left(T{\prime }_2\right)\ge s\left(T_2\right)$ , and the root r having more neighbors in $T{\prime }_2$ than it has in T₂.

Any spanning tree T of G containing all edges of $\left(r:A\right)$ has $m+3n$ edges, $3n\left(m-1\right)$ paths of length three (each of the $3n$ edges of the tree connecting A and B induces exactly $m-1$ such paths), and $m\left(m-1\right)∕2+3n$ paths of length two that are not formed by a pair of edges between A and B. There are $3{\delta }_4+{\delta }_3$ remaining paths of length two, where ${\delta }_i$ is the number of vertices in A that have degree i in the tree. Indeed, a vertex $v\in A$ with $j\in \left\{0,1,2,3\right\}$ neighbors from B in the tree contributes no such path in case of $j\in \left\{0,1\right\}$ , one such path in case of $j=2$ , and three such paths in case of $j=3$ . Thus by Proposition 1 $$m\left(T\right)=m^2+m+12n+6{\delta }_4+2{\delta }_3,s\left(T\right)=m^2+3mn+6n+6{\delta }_4+2{\delta }_3.$$

Since $\left|B\right|=3n$ , we have $3{\delta }_4+2{\delta }_3\le 3n$ and $6{\delta }_4+2{\delta }_3\le 6{\delta }_4+4{\delta }_3\le 6n$ . Hence, $6{\delta }_4+2{\delta }_3\le 6n$ with equality holding if and only if ${\delta }_3=0$ and ${\delta }_4=n$ .

A perfect 3-DM ${ℳ}^{\ast }=\left\{M_1,\dots ,M_n\right\}$ induces the spanning tree $T_{{ℳ}^{\ast }}$ that contains all edges from $\left(r:A\right)$ and edges $ax,ay,az$ for each $a=\left\{x,y,z\right\}\in {ℳ}^{\ast }$ . For this tree we have ${\delta }_4=n$ and

Conversely, every spanning tree T that contains all edges from $\left(r:A\right)$ and $m\left(T\right)=t_1\left(n,m\right)$ or $s\left(T\right)=t_2\left(n,m\right)$ (and thus ${\delta }_4=n$ ) arises from a perfect 3-DM.

By Lemma 13, the graph G satisfies ${\tau }_1\left(G\right)\ge t_1\left(n,m\right)$ (resp., ${\tau }_2\left(G\right)\ge t_2\left(n,m\right)$ ) if and only if there is a spanning tree T of G that contains all edges from $\left(r:A\right)$ and whose m-metric (resp., s-metric) is equal to $t_1\left(n,m\right)$ (resp., $t_2\left(n,m\right))$ . The latter is true if and only if Q has a perfect 3-DM. □

4. ILP Formulations

Here we describe two ILP models for the s-SF Spanning Tree problem (for the m-SF Spanning Tree problem the approach is similar). For a given spanning tree T of a graph $G=\left(V,E\right)$ of order n, consider the indicator variables $(x_e)e\in E$ : $$x_e=\left\{\begin{array}{c}\begin{array}{c}1,e\in E\left(T\right);\\ 0,otherwise.\end{array}\end{array}\right.$$(13)

Using Proposition 1, we can represent $s\left(T\right)$ as $$s\left(T\right)={\sum }_{\left\{e_i,e_j,e_k\right\}\in {\Gamma }_3\left(G\right)}{x}_{e_i}{x}_{e_j}{x}_{e_k}+2{\sum }_{\left\{e_i,e_j\right\}\in {\Gamma }_2\left(G\right)}{x}_{e_i}{x}_{e_j}+{\sum }_{e\in E\left(G\right)}{x}_e,$$(14)

where ${\Gamma }_i\left(G\right)$ denotes the set of all paths of length i in G. To linearize (14), we introduce Boolean variables $y_{ijk}$ and $y_{ij}$ and the following constraints: $$\begin{array}{c}{y}_{ijk}\le x_{e_i},y_{ij}\le x_{e_i},\\ y_{ijk}\le x_{e_j},y_{ij}\le x_{e_j},\\ y_{ijk}\le x_{e_k},y_{ij}\ge x_{e_i}+x_{e_j}-1,\\ y_{ijk}\ge x_{e_i}+x_{e_j}+x_{e_k}-2,\end{array}$$(15)

for every $\left\{e_i,e_j,e_k\right\}\in {\Gamma }_3\left(G\right)$ and $\left\{e_i,e_j\right\}\in {\Gamma }_2\left(G\right)$ , which are equivalent to $y_{ijk}=x_{e_i}{x}_{e_j}{x}_{e_k}$ and $y_{ij}=x_{e_i}{x}_{e_j}$ . Thus the objective function (14) can be rewritten as $$s\left(T\right)={\sum }_{\left\{e_i,e_j,e_k\right\}\in {\Gamma }_3\left(G\right)}{y}_{ijk}+2{\sum }_{\left\{e_i,e_j\right\}\in {\Gamma }_2\left(G\right)}{y}_{ij}+{\sum }_{e\in E\left(G\right)}{x}_e.$$(16)

We use two types of constraints to describe the spanning trees. The first type is the extended formulation of Martin (1991), which uses auxiliary variables $$z_{\left(v,w\right)}^r,z_{\left(w,v\right)}^r\ge 0foreveryr\in V\left(G\right),vw\in E\left(G\right),$$(17)

where $z_{\left(v,r\right)}^r=0$ for every $r\in V\left(G\right)$ and $vr\in E\left(G\right)$ . A 0/1-vector x describes a spanning tree of G if and only if these variables satisfy the constraints $$\begin{array}{cc}{x}_{vw}-z_{\left(v,w\right)}^r-z_{\left(w,v\right)}^r& =0,r\in V\left(G\right),vw\in E\left(G\right),\\ {\sum }_{vw\in E\left(G\right)}{z}_{\left(v,w\right)}^r=1,r,w\in V\left(G\right),r\ne w,\\ {\sum }_{vr\in E\left(G\right)}{z}_{\left(v,r\right)}^r=0,r\in V\left(G\right).\end{array}$$(18)

The second type exploits the Miller–Tucker–Zemlin (MTZ) constraints (Miller et al., 1960). We introduce the auxiliary variables $$\begin{array}{c}{z}_{\left(v,w\right)},z_{\left(w,v\right)}\in \left\{0,1\right\}foreveryvw\in E\left(G\right),\\ t_v\in \left[0,n-1\right]foreveryv\in V\left(G\right),\end{array}$$(19)

and constraints $$\begin{array}{c}{x}_{vw}-z_{\left(v,w\right)}-z_{\left(w,v\right)}=0,vw\in E\left(G\right),\\ {\sum }_{vw\in E\left(G\right)}{z}_{\left(v,w\right)}=1,w\in V\left(G\right)\setminus \left\{r\right\},\\ {\sum }_{vr\in E\left(G\right)}{z}_{\left(v,r\right)}=0,\\ t_v-t_w+n{z}_{\left(v,w\right)}\le n-1,v,w\in V\left(G\right),vw\in E\left(G\right),\end{array}$$(20)

where $r\in V\left(G\right)$ is some fixed vertex. Finally we add the additional constraint $$s\left(T\right)={\sum }_{\left\{e_i,e_j,e_k\right\}\in {\Gamma }_3\left(G\right)}{y}_{ijk}+2{\sum }_{\left\{e_i,e_j\right\}\in {\Gamma }_2\left(G\right)}{y}_{ij}+{\sum }_{e\in E\left(G\right)}{x}_e\le n\left(n-\Delta \left(G\right)-1\right)+{\Delta }^2\left(G\right),$$(21)

defined by Theorem 7, which turns out to significantly improve the algorithm running times. Maximization of the objective (16) subject to the constraints (15), (18), (21) is further referred to as Martin formulation, while maximization of Equation (16) subject to Equations (15), (20), (21) as MTZ formulation.

5. Experimental Results

In this section, we investigate the practical aspects of scale-free spanning tree problems by conducting computational experiments for various simulated and experimental data sets to evaluate the performance of the ILP models. All computations below were performed on a standard laptop with 2.0 GHz dual core processor and 16 GB of RAM, and ILP problems were solved using Gurobi 8.1.

5.1. Synthetic data

5.1.1. Synthetic graphs

We used graphs from the following synthetic data sets:

Erdős-Rényi graphs constructed by adding each possible edge uniformly and independently with the probability $p=4.25∕n$ . The number of nodes n in our experiments varied from 10 to 40 (corresponding to the sizes of HCV outbreaks analyzed later).

$n\times m$ grid graphs (Cartesian products of paths P_n and P_m) with $n,m=4,\dots ,7$ .

Scale-free graphs of two types generated using NetworkX library (Hagberg et al., 2008): those based on the classical Barabási and Albert (1999) model and those constructed with NetworkX default parameters. The latter graphs are usually denser.

For all synthetic data sets except for grid graphs, we generated 10 graphs per node number. Figures 3 and 4 illustrate the running times of the ILP solver on both the MTZ formulation and the Martin formulation compared with the published tool QUENTIN (Skums et al., 2018) runtimes for all four simulated graph classes. ¹ The results demonstrate that for those graph classes, the ILP algorithms in average perform much better than in the worst case and are able to produce optimal results in a reasonable amount of time. Moreover, for considered graph sizes, they outperform QUENTIN. For Erdős–Rényi graphs and grids (Fig. 3), which are characterized by relatively large sets of feasible solutions, the Martin formulation was superior to MTZ and QUENTIN, while for Barabási–Albert scale-free graphs (Fig. 4a), the MTZ formulation was leading to the faster algorithm. In general, the ILP approach allows to solve the problem within minutes or few hours for small-to-medium-sized problems (up to several dozens of vertices) on Erdős–Rényi graphs and grids, and for medium-sized problems (several hundred vertices) on scale-free graphs.

FIG. 3.

Running times of ILP solver and QUENTIN on Erdős–Rényi graphs (a) and grids (b). ILP, integer linear programming.

FIG. 4.

Running times of ILP solver on Barabási–Albert (a) and NetworkX (b) scale-free graphs.

5.1.2. Simulated outbreaks

We simulated outbreaks over scale-free Barabási–Albert contact networks of $n=10-30$ nodes using the following model. The infection spreads over each network according to the susceptible infected (SI) model (Newman, 2010) with the transmission rate $\rho =10^{-2}$ . Each infected individual is assumed to carry a viral sequence of length $m=13200$ , and at each transmission event, the source's sequence is transmitted to the recipient. Sequence evolution is described by a skyline model with the piecewise constant decreasing mutation rate, that is, viral sequences mutate at the basic rate of $\mu =10^{-5}$ changes/position/time unit, and the mutation rate is decreasing by $30\%$ every $\tau =100$ time units. This model captures the decrease of the speed of intrahost evolution as the infection progresses from an acute to a persistent stage (De Maio et al., 2016; Icer et al., 2020).

For each simulated outbreak, we compared the performance of the ILP algorithm for the Martin formulation, with the standard approach based on the phylogenetic trait inference (Sagulenko et al., 2018). First, we constructed a maximum likelihood phylogeny using MEGA (Kumar et al., 2018). Each patient was encoded by a discrete trait, and the marginal likelihood ancestral traits were reconstructed using the Felsenstein pruning algorithm (Felsenstein, 2004) with the pairwise between-trait transition rates equal to $\rho$ . Inferred transmission links then correspond to trait changes along the phylogeny branches. The genetic relatedness network G_R used as an input for the ILP was constructed using a threshold-based approach suggested by Kosakovsky Pond et al. (2018). A pair of vertices of G_R are adjacent, if the Hamming distance between the corresponding sequences does not exceed a threshold t that was estimated as the minimal integer such that the graph G_R is connected. The obtained graph was further sparsed out by applying the same procedure to each of its biconnected component.

The results of algorithms' comparison are shown in Figure 5. We measured algorithm accuracy by the proportion of correctly inferred transmission links and transmission ancestries (i.e., pairs, ancestor/descendant). s-SF-based ILP clearly outperformed the phylogenetic approach: the average transmission link detection accuracy was $82.44\%$ for the former and $72.61\%$ for the latter, while the average transmission ancestry detection accuracies were $97.48\%$ and $73.96\%$ , respectively.

FIG. 5.

Accuracy of s-SF ILP model compared with the phylogenetic trait inference algorithm.

5.2. Data from hepatitis C outbreaks

We applied the concept of scale-free spanning trees to the graphs arising from the benchmark data set consisting of several epidemiologically curated HCV outbreaks investigated by the CDC (Campo et al., 2016; Glebova et al., 2017; Skums et al., 2018). This data set comprises HCV quasispecies populations sampled from 81 infected individuals involved in 10 viral outbreaks. Each population consists of RNA sequences of HCV hypervariable region 1 (HVR1) of length 264 bp. Transmission histories of the outbreaks (“who infected whom”) are known as a result of epidemiological investigations. In this case, we are dealing with intrahost viral populations rather than single sequences, and therefore, we compared the proposed approach with QUENTIN, which has been specifically designed to handle such data (Skums et al., 2018).

For each outbreak, the genetic relatedness network G_R was constructed using the threshold-based approach suggested by Campo et al. (2016). The vertices of G_R are adjacent, if the minimal Hamming distance between the sets of sequences sampled from these patients does not exceed the threshold t. The threshold value was estimated as described in Subsection 5.1.2. Next, the ILP algorithm for the Martin formulation has been applied to G_R. For all outbreaks, the ILP problem has been solved to optimality.

We tested the accuracy of inference of transmission links and identification of the superspreaders (the sources of majority of infections). The results are reported in Table 1. The superspreaders correspond to vertices of highest degrees in s-optimal and m-optimal trees for 9 out of 10 outbreaks. It should be noted that all algorithms incorrectly identified a superspreader for the same outbreak. It is the only outbreak where the virus was transmitted via a nonsocial interaction (namely, through blood transfusions), while all other outbreaks were associated with unsafe injection practices or sexual contacts. For those outbreaks, both ILP approaches correctly recovered $92\%$ of transmission links and all ancestor/descendant pairs, thus outperforming QUENTIN.

Table 1.

Results on Experimental Data with Different Models

Methods	Evaluation metric
	(A)	(B)	(C)
QUENTIN	0.9	0.78	0.98
s-SF	0.9	0.92	1.0
m-SF	0.9	0.92	1.0

(A) Superspreader inference accuracy, (B) accuracy of transmission link inference, and (C) accuracy of transmission ancestry inference.

6. Discussion

In genomic epidemiology, reconstruction of viral transmission histories from genomic data is fundamental for the investigation of outbreaks and understanding of epidemic spread. Genomic analysis has become one of the major tools for the investigation of outbreaks and surveillance of transmission dynamics (Armstrong et al., 2019; Knyazev et al., 2020). Naturally, graphs are the primary models used in such studies (Wertheim et al., 2014; Campo et al., 2016; Ragonnet-Cronin et al., 2019). In many settings, graph-based methods have been shown to be more efficient to ascertain transmission links compared with methods based on binary phylogenies (Wertheim et al., 2014), as phylogenetic clades are not easily resolvable into transmission clusters and pairs (Lewis et al., 2008; Hughes et al., 2009; Kouyos et al., 2010), while the statistical support for a clade does not necessarily indicate the statistical support for a relationship between individual genomes inside a clade (Volz et al., 2012; Wertheim et al., 2014). However, in many cases, transmission links cannot be inferred using the genomic data alone (Jombart et al., 2014; Villandre et al., 2016). It leads to the need to introduce additional constraints on the reconstructed transmission networks or utilize more complicated objectives.

As a result, the associated algorithmic problems become harder. In this article, we studied one such problem—scale-free spanning tree problem—that arises in epidemiological studies of viruses whose spread is highly influenced by social networks of contacts between susceptible individuals. This includes HIV, HCV, and other pathogens transmitted through sexual contact or needle sharing. We demonstrated that this problem in its two possible algorithmic formulations is NP-hard, even if restricted to relatively simple graph classes. However, it admits an ILP formulation allowing to efficiently solve the problem for small-to-medium networks. It is often enough for the vast majority of outbreaks of HIV and HCV that involve dozens of infected individuals.

However, some outbreaks involve hundreds or even thousands of hosts, and in such cases, more scalable algorithmic solutions are needed. Thus, an important open problem is to establish whether constant or logarithmic approximation exists for the m-SF Spanning Tree and s-SF Spanning Tree problems. In this context, it would be interesting to explore the relationships between scale-free spanning tree problems and max-leaf spanning tree problems. The latter is a well-studied combinatorial problem (Griggs et al., 1989; Galbiati et al., 1994), which seems to be the closest to our problem. Indeed, both problems aim to find a “star-like” spanning tree; furthermore, several reduction schemes for the proof of NP-completeness used by us exploit this relationship. Importantly, Lu and Ravi (1998) and Reich (2016) showed that the max-leaf spanning tree problem is approximable within a constant factor. Although the problems are far from being equivalent, it may seem reasonable for future studies to try to adopt algorithmic machinery developed for the max-leaf spanning tree problem to the scale-free spanning tree problem.