A counterexample to the chain rule for conditional HILL entropy

Most entropy notions \({H(.)}\) like Shannon or min-entropy satisfy a chain rule stating that for random variables \({X,Z,}\) and \({A}\) we have \({H(X|Z,A)\ge H(X|Z)-|A|}\). That is, by conditioning on \({A}\) the entropy of \({X}\) can decrease by at most the bitlength \({|A|}\) of \({A}\). Such chain rules are known to hold for some computational entropy notions like Yao’s and unpredictability-entropy. For HILL entropy, the computational analogue of min-entropy, the chain rule is of special interest and has found many applications, including leakage-resilient cryptography, deterministic encryption, and memory delegation. These applications rely on restricted special cases of the chain rule. Whether the chain rule for conditional HILL entropy holds in general was an open problem for which we give a strong negative answer: we construct joint distributions \({(X,Z,A)}\), where \({A}\) is a distribution over a single bit, such that the HILL entropy H ^HILL \({(X|Z)}\) is large but H ^HILL \({(X|Z,A)}\) is basically zero.Our counterexample just makes the minimal assumption that \({{\mathbf{NP}} \nsubseteq{\mathbf{P/poly}}}\). Under the stronger assumption that injective one-way function exist, we can make all the distributions efficiently samplable.Finally, we show that some more sophisticated cryptographic objects like lossy functions can be used to sample a distribution constituting a counterexample to the chain rule making only a single invocation to the underlying object.     

Incompressible Functions,Relative-Error Extractors,and the Power of Nondeterministic Reductions

A circuit C compresses a function \({f : \{0,1\}^n\rightarrow \{0,1\}^m}\) if given an input \({x\in \{0,1\}^n}\), the circuit C can shrink x to a shorter ?-bit string x′ such that later, a computationally unbounded solver D will be able to compute f(x) based on x′. In this paper we study the existence of functions which are incompressible by circuits of some fixed polynomial size \({s=n^c}\). Motivated by cryptographic applications, we focus on average-case \({(\ell,\epsilon)}\) incompressibility, which guarantees that on a random input \({x\in \{0,1\}^n}\), for every size s circuit \({C:\{0,1\}^n\rightarrow \{0,1\}^{\ell}}\) and any unbounded solver D, the success probability \({\Pr_x[D(C(x))=f(x)]}\) is upper-bounded by \({2^{-m}+\epsilon}\). While this notion of incompressibility appeared in several works (e.g., Dubrov and Ishai, STOC 06), so far no explicit constructions of efficiently computable incompressible functions were known. In this work, we present the following results:

1. (1)
   Assuming that E is hard for exponential size nondeterministic circuits, we construct a polynomial time computable boolean function \({f:\{0,1\}^n\rightarrow \{0,1\}}\) which is incompressible by size n ^c circuits with communication \({\ell=(1-o(1)) \cdot n}\) and error \({\epsilon=n^{-c}}\). Our technique generalizes to the case of PRGs against nonboolean circuits, improving and simplifying the previous construction of Shaltiel and Artemenko (STOC 14).
    
2. (2)
   We show that it is possible to achieve negligible error parameter \({\epsilon=n^{-\omega(1)}}\) for nonboolean functions. Specifically, assuming that E is hard for exponential size \({\Sigma_3}\)-circuits, we construct a nonboolean function \({f:\{0,1\}^n\rightarrow \{0,1\}^m}\) which is incompressible by size n ^c circuits with \({\ell=\Omega(n)}\) and extremely small \({\epsilon=n^{-c} \cdot 2^{-m}}\). Our construction combines the techniques of Trevisan and Vadhan (FOCS 00) with a new notion of relative error deterministic extractor which may be of independent interest.
    
3. (3)
   We show that the task of constructing an incompressible boolean function \({f:\{0,1\}^n\rightarrow \{0,1\}}\) with negligible error parameter \({\epsilon}\) cannot be achieved by “existing proof techniques”. Namely, nondeterministic reductions (or even \({\Sigma_i}\) reductions) cannot get \({\epsilon=n^{-\omega(1)}}\) for boolean incompressible functions. Our results also apply to constructions of standard Nisan-Wigderson type PRGs and (standard) boolean functions that are hard on average, explaining, in retrospect, the limitations of existing constructions. Our impossibility result builds on an approach of Shaltiel and Viola (STOC 08).
    

     

Close to linear space routing schemes

Let \(G=(V,E)\) be an unweighted undirected graph with n vertices and m edges, and let \(k>2\) be an integer. We present a routing scheme with a poly-logarithmic header size, that given a source s and a destination t at distance \(\varDelta \) from s, routes a message from s to t on a path whose length is \(O(k\varDelta +m^{1/k})\). The total space used by our routing scheme is \(mn^{O(1/\sqrt{\log n})}\), which is almost linear in the number of edges of the graph. We present also a routing scheme with \(n^{O(1/\sqrt{\log n})}\) header size, and the same stretch (up to constant factors). In this routing scheme, the routing table of every \(v\in V\) is at most \(kn^{O(1/\sqrt{\log n})}deg(v)\), where deg(v) is the degree of v in G. Our results are obtained by combining a general technique of Bernstein (2009), that was presented in the context of dynamic graph algorithms, with several new ideas and observations.     

Entanglement witness criteria of strong-<Emphasis Type="Italic">k</Emphasis>-separability for multipartite quantum states

Let \(H_{1}, H_{2},\ldots ,H_{n}\) be separable complex Hilbert spaces with \(\dim H_{i}\ge 2\) and \(n\ge 2\). Assume that \(\rho \) is a state in \(H=H_1\otimes H_2\otimes \cdots \otimes H_n\). \(\rho \) is called strong-k-separable \((2\le k\le n)\) if \(\rho \) is separable for any k-partite division of H. In this paper, an entanglement witnesses criterion of strong-k-separability is obtained, which says that \(\rho \) is not strong-k-separable if and only if there exist a k-division space \(H_{m_{1}}\otimes \cdots \otimes H_{m_{k}}\) of H, a finite-rank linear elementary operator positive on product states \(\Lambda :\mathcal {B}(H_{m_{2}}\otimes \cdots \otimes H_{m_{k}})\rightarrow \mathcal {B}(H_{m_{1}})\) and a state \(\rho _{0}\in \mathcal {S}(H_{m_{1}}\otimes H_{m_{1}})\), such that \(\mathrm {Tr}(W\rho )<0\), where \(W=(\mathrm{Id}\otimes \Lambda ^{\dagger })\rho _{0}\) is an entanglement witness. In addition, several different methods of constructing entanglement witnesses for multipartite states are also given.     

Quantum Query Complexity of Almost All Functions with Fixed On-set Size

This paper considers the quantum query complexity of almost all functions in the set \({\mathcal{F}}_{N,M}\) of \({N}\)-variable Boolean functions with on-set size \({M (1\le M \le 2^{N}/2)}\), where the on-set size is the number of inputs on which the function is true. The main result is that, for all functions in \({\mathcal{F}}_{N,M}\) except its polynomially small fraction, the quantum query complexity is \({ \Theta\left(\frac{\log{M}}{c + \log{N} - \log\log{M}} + \sqrt{N}\right)}\) for a constant \({c > 0}\). This is quite different from the quantum query complexity of the hardest function in \({\mathcal{F}}_{N,M}\): \({\Theta\left(\sqrt{N\frac{\log{M}}{c + \log{N} - \log\log{M}}} + \sqrt{N}\right)}\). In contrast, almost all functions in \({\mathcal{F}}_{N,M}\) have the same randomized query complexity \({\Theta(N)}\) as the hardest one, up to a constant factor.     

The panpositionable panconnectedness of crossed cubes

In many parallel and distributed multiprocessor systems, the processors are connected based on different types of interconnection networks. The topological structure of an interconnection network is typically modeled as a graph. Among the many kinds of network topologies, the crossed cube is one of the most popular. In this paper, we investigate the panpositionable panconnectedness problem with respect to the crossed cube. A graph G is r-panpositionably panconnected if for any three distinct vertices x, y, z of G and for any integer \(l_1\) satisfying \(r \le l_1 \le |V(G)| - r - 1\), there exists a path \(P = [x, P_1, y, P_2, z]\) in G such that (i) \(P_1\) joins x and y with \(l(P_1) = l_1\) and (ii) \(P_2\) joins y and z with \(l(P_2) = l_2\) for any integer \(l_2\) satisfying \(r \le l_2 \le |V(G)| - l_1 - 1\), where |V(G)| is the total number of vertices in G and \(l(P_1)\) (respectively, \(l(P_2)\)) is the length of path \(P_1\) (respectively, \(P_2\)). By mathematical induction, we demonstrate that the n-dimensional crossed cube \(CQ_n\) is n-panpositionably panconnected. This result indicates that the path embedding of joining x and z with a mediate vertex y in \(CQ_n\) is extremely flexible. Moreover, applying our result, crossed cube problems such as panpositionable pancyclicity, panpositionably Hamiltonian connectedness, and panpositionable Hamiltonicity can be solved.     

Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas

In this paper, we give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation between black-box PIT and lower bounds, we obtain lower bounds for these models.For depth-3 multilinear formulas, of size exp\({(n^\delta)}\), we give a hitting set of size exp\({\left(\tilde{O}\left(n^{2/3 + 2\delta/3}\right) \right)}\). This implies a lower bound of exp\({(\tilde{\Omega}(n^{1/2}))}\) for depth-3 multilinear formulas, for some explicit polynomial.For depth-4 multilinear formulas, of size exp\({(n^\delta)}\), we give a hitting set of size exp\({\left(\tilde{O}\left(n^{2/3 + 4\delta/3}\right) \right)}\). This implies a lower bound of exp\({(\tilde{\Omega}(n^{1/4}))}\) for depth-4 multilinear formulas, for some explicit polynomial.A regular formula consists of alternating layers of \({+,\times}\) gates, where all gates at layer i have the same fan-in. We give a hitting set of size (roughly) exp\({\left(n^{1- \delta}\right)}\), for regular depth-d multilinear formulas with formal degree at most n and size exp\({(n^\delta)}\), where \({\delta = O(1/{\sqrt{5}^d})}\). This result implies a lower bound of roughly exp\({(\tilde{\Omega}(n^{1/{\sqrt{5}^d}}))}\) for such formulas.We note that better lower bounds are known for these models, but also that none of these bounds was achieved via construction of a hitting set. Moreover, no lower bound that implies such PIT results, even in the white-box model, is currently known.Our results are combinatorial in nature and rely on reducing the underlying formula, first to a depth-4 formula, and then to a read-once algebraic branching program (from depth-3 formulas, we go straight to read-once algebraic branching programs).     

Factors of low individual degree polynomials

Kaltofen (Randomness in computation, vol 5, pp 375–412, 1989) proved the remarkable fact that multivariate polynomial factorization can be done efficiently, in randomized polynomial time. Still, more than twenty years after Kaltofen’s work, many questions remain unanswered regarding the complexity aspects of polynomial factorization, such as the question of whether factors of polynomials efficiently computed by arithmetic formulas also have small arithmetic formulas, asked in Kopparty et al. (2014), and the question of bounding the depth of the circuits computing the factors of a polynomial. We are able to answer these questions in the affirmative for the interesting class of polynomials of bounded individual degrees, which contains polynomials such as the determinant and the permanent. We show that if \({P(x_{1},\ldots,x_{n})}\) is a polynomial with individual degrees bounded by r that can be computed by a formula of size s and depth d, then any factor \({f(x_{1},\ldots, x_{n})}\) of \({P(x_{1},\ldots,x_{n})}\) can be computed by a formula of size \({\textsf{poly}((rn)^{r},s)}\) and depth d + 5. This partially answers the question above posed in Kopparty et al. (2014), who asked if this result holds without the dependence on r. Our work generalizes the main factorization theorem from Dvir et al. (SIAM J Comput 39(4):1279–1293, 2009), who proved it for the special case when the factors are of the form \({f(x_{1}, \ldots, x_{n}) \equiv x_{n} - g(x_{1}, \ldots, x_{n-1})}\). Along the way, we introduce several new technical ideas that could be of independent interest when studying arithmetic circuits (or formulas).     

Some properties of the disjunctive languages contained in <Emphasis Type="Italic">Q</Emphasis>

The set of all primitive words Q over an alphabet X was first defined and studied by Shyr and Thierrin (Proceedings of the 1977 Inter. FCT-Conference, Poznan, Poland, Lecture Notes in Computer Science 56. pp. 171–176 (1977)). It showed that for the case |X| ≥ 2, the set along with \({Q^{(i)} = \{f^i\,|\,f \in Q\}, i\geq 2}\) are all disjunctive. Since then these disjunctive sets are often be quoted. Following Shyr and Thierrin showed that the half sets \({Q_{ev} = \{f \in Q\,|\,|f| = {\rm even}\}}\) and Q _od = Q \ Q _ev of Q are disjunctive, Chien proved that each of the set \({Q_{p,r}= \{u\in Q\,|\,|u|\equiv r\,(mod\,p) \},\,0\leq r < p}\) is disjunctive, where p is a prime number. In this paper, we generalize this property to that all the languages \({Q_{n,r}= \{u\in Q\,|\,|u|\equiv r\,(mod\,n) \},\, 0\leq r < n}\) are disjunctive languages, where n is any positive integer. We proved that for any n ≥ 1, k ≥ 2, (Q _n,0) ^k are all regular languages. Some algebraic properties related to the family of languages {Q _n,r | n ≥ 2, 0 ≤ r < n } are investigated.     

A general framework for architecture composability

Architectures depict design principles: paradigms that can be understood by all, allow thinking on a higher plane and avoiding low-level mistakes. They provide means for ensuring correctness by construction by enforcing global properties characterizing the coordination between components. An architecture can be considered as an operator A that, applied to a set of components \({\mathcal{B}}\), builds a composite component \({A(\mathcal{B})}\) meeting a characteristic property \({\Phi}\). Architecture composability is a basic and common problem faced by system designers. In this paper, we propose a formal and general framework for architecture composability based on an associative, commutative and idempotent architecture composition operator \({\oplus}\). The main result is that if two architectures A ₁ and A ₂ enforce respectively safety properties \({\Phi_{1}}\) and \({\Phi_{2}}\), the architecture \({A_{1} \oplus A_{2}}\) enforces the property \({\Phi_{1} \land \Phi_{2}}\), that is both properties are preserved by architecture composition. We also establish preservation of liveness properties by architecture composition. The presented results are illustrated by a running example and a case study.     

Counter machines and crystallographic structures

One way to depict a crystallographic structure is by a periodic (di)graph, i.e., a graph whose group of automorphisms has a translational subgroup of finite index acting freely on the structure. We establish a relationship between periodic graphs representing crystallographic structures and an infinite hierarchy of intersection languages \(\mathcal {DCL}_d,\,d=0,1,2,\ldots \), within the intersection classes of deterministic context-free languages. We introduce a class of counter machines that accept these languages, where the machines with d counters recognize the class \(\mathcal {DCL}_d\). An intersection of d languages in \(\mathcal {DCL}_1\) defines \(\mathcal {DCL}_d\). We prove that there is a one-to-one correspondence between sets of walks starting and ending in the same unit of a d-dimensional periodic (di)graph and the class of languages in \(\mathcal {DCL}_d\). The proof uses the following result: given a digraph \(\Delta \) and a group G, there is a unique digraph \(\Gamma \) such that \(G\le \mathrm{Aut}\,\Gamma ,\,G\) acts freely on the structure, and \(\Gamma /G \cong \Delta \).     

An optimal adaptive stabilizing algorithm for two edge-disjoint paths problem

The problem of two edge-disjoint paths is to identify two paths \(Q_1\) and \(Q_2\) from source \(s \in V\) to target \(t \in V\) without any common arc in a directed connected graph \(G=(V, E)\). In this paper, we present an adaptive stabilizing algorithm for finding a pair of edge-disjoint paths from s to t in G in O(D) rounds with state-space complexity of \(O(log\; n)\) bits per process, where n is the number of nodes and D is the diameter of the graph. The proposed algorithm is optimal with respect to its time complexity, and the total length of the shortest paths. In addition, it can also be used to solve the problem for undirected graphs. Since the proposed algorithm is stabilizing, it does not require initialization and is capable of withstanding transient faults. We view a fault that perturbs the state of the system but not its program as a transient fault. In addition, the proposed algorithm is adaptive since it is capable of dealing with topology changes in the form of addition/removal of arcs and/or nodes as well as changes in the directions of arcs provided that two edge-disjoint paths between s and t exist after the topology change.     

The hierarchical Petersen network: a new interconnection network with fixed degree

Network cost and fixed-degree characteristic for the graph are important factors to evaluate interconnection networks. In this paper, we propose hierarchical Petersen network (HPN) that is constructed in recursive and hierarchical structure based on a Petersen graph as a basic module. The degree of HPN(n) is 5, and HPN(n) has \(10^n\) nodes and \(2.5 \times 10^n\) edges. And we analyze its basic topological properties, routing algorithm, diameter, spanning tree, broadcasting algorithm and embedding. From the analysis, we prove that the diameter and network cost of HPN(n) are \(3\log _{10}N-1\) and \(15 \log _{10}N-1\), respectively, and it contains a spanning tree with the degree of 4. In addition, we propose link-disjoint one-to-all broadcasting algorithm and show that HPN(n) can be embedded into FP\(_k\) with expansion 1, dilation 2k and congestion 4. For most of the fixed-degree networks proposed, network cost and diameter require \(O(\sqrt{N})\) and the degree of the graph requires O(N). However, HPN(n) requires O(1) for the degree and \(O(\log _{10}N)\) for both diameter and network cost. As a result, the suggested interconnection network in this paper is superior to current fixed-degree and hierarchical networks in terms of network cost, diameter and the degree of the graph.     

Data assimilation and sampling in Banach spaces

This paper studies the problem of approximating a function f in a Banach space \(\mathcal{X}\) from measurements \(l_j(f)\), \(j=1,\ldots ,m\), where the \(l_j\) are linear functionals from \(\mathcal{X}^*\). Quantitative results for such recovery problems require additional information about the sought after function f. These additional assumptions take the form of assuming that f is in a certain model class \(K\subset \mathcal{X}\). Since there are generally infinitely many functions in K which share these same measurements, the best approximation is the center of the smallest ball B, called the Chebyshev ball, which contains the set \(\bar{K}\) of all f in K with these measurements. Therefore, the problem is reduced to analytically or numerically approximating this Chebyshev ball. Most results study this problem for classical Banach spaces \(\mathcal{X}\) such as the \(L_p\) spaces, \(1\le p\le \infty \), and for K the unit ball of a smoothness space in \(\mathcal{X}\). Our interest in this paper is in the model classes \(K=\mathcal{K}(\varepsilon ,V)\), with \(\varepsilon >0\) and V a finite dimensional subspace of \(\mathcal{X}\), which consists of all \(f\in \mathcal{X}\) such that \(\mathrm{dist}(f,V)_\mathcal{X}\le \varepsilon \). These model classes, called approximation sets, arise naturally in application domains such as parametric partial differential equations, uncertainty quantification, and signal processing. A general theory for the recovery of approximation sets in a Banach space is given. This theory includes tight a priori bounds on optimal performance and algorithms for finding near optimal approximations. It builds on the initial analysis given in Maday et al. (Int J Numer Method Eng 102:933–965, 2015) for the case when \(\mathcal{X}\) is a Hilbert space, and further studied in Binev et al. (SIAM UQ, 2015). It is shown how the recovery problem for approximation sets is connected with well-studied concepts in Banach space theory such as liftings and the angle between spaces. Examples are given that show how this theory can be used to recover several recent results on sampling and data assimilation.     

Finding vertex-surjective graph homomorphisms

The Surjective Homomorphism problem is to test whether a given graph G called the guest graph allows a vertex-surjective homomorphism to some other given graph H called the host graph. The bijective and injective homomorphism problems can be formulated in terms of spanning subgraphs and subgraphs, and as such their computational complexity has been extensively studied. What about the surjective variant? Because this problem is NP-complete in general, we restrict the guest and the host graph to belong to graph classes \({{\mathcal G}}\) and \({{\mathcal H}}\), respectively. We determine to what extent a certain choice of \({{\mathcal G}}\) and \({{\mathcal H}}\) influences its computational complexity. We observe that the problem is polynomial-time solvable if \({{\mathcal H}}\) is the class of paths, whereas it is NP-complete if \({{\mathcal G}}\) is the class of paths. Moreover, we show that the problem is even NP-complete on many other elementary graph classes, namely linear forests, unions of complete graphs, cographs, proper interval graphs, split graphs and trees of pathwidth at most 2. In contrast, we prove that the problem is fixed-parameter tractable in k if \({{\mathcal G}}\) is the class of trees and \({{\mathcal H}}\) is the class of trees with at most k leaves, or if \({{\mathcal G}}\) and \({{\mathcal H}}\) are equal to the class of graphs with vertex cover number at most k.     

Construction of quantum caps in projective space <Emphasis Type="Italic">PG</Emphasis>(<Emphasis Type="Italic">r</Emphasis>, 4) and quantum codes of distance 4

Constructions of quantum caps in projective space PG(r, 4) by recursive methods and computer search are discussed. For each even n satisfying \(n\ge 282\) and each odd z satisfying \(z\ge 275\), a quantum n-cap and a quantum z-cap in \(PG(k-1, 4)\) with suitable k are constructed, and \([[n,n-2k,4]]\) and \([[z,z-2k,4]]\) quantum codes are derived from the constructed quantum n-cap and z-cap, respectively. For \(n\ge 282\) and \(n\ne 286\), 756 and 5040, or \(z\ge 275\), the results on the sizes of quantum caps and quantum codes are new, and all the obtained quantum codes are optimal codes according to the quantum Hamming bound. While constructing quantum caps, we also obtain many large caps in PG(r, 4) for \(r\ge 11\). These results concerning large caps provide improved lower bounds on the maximal sizes of caps in PG(r, 4) for \(r\ge 11\).     

Exact Algorithms for Intervalizing Coloured Graphs

In the Intervalizing Coloured Graphs problem, one must decide for a given graph G = (V, E) with a proper vertex colouring of G whether G is the subgraph of a properly coloured interval graph. For the case that the number of colors is fixed, we give an exact algorithm that uses \(2^{\mathcal {O}(n/\log n)}\) time. We also give an \(\mathcal {O}^{\ast }(2^{n})\) algorithm for the case that the number of colors is not fixed.     

Least common container of tree pattern queries and its applications

Tree patterns represent important fragments of XPath. In this paper, we show that some classes \({\mathcal{C}}\) of tree patterns exhibit such a property that, given a finite number of compatible tree patterns \({P_1, \ldots, P_n\in \mathcal{C}}\), there exists another pattern P such that P ₁, . . . , P _n are all contained in P, and for any tree pattern \({Q\in \mathcal{C}}\), P ₁, . . . , P _n are all contained in Q if and only if P is contained in Q. We experimentally demonstrate that the pattern P is usually much smaller than P ₁, . . . , P _n combined together. Using the existence of P above, we show that testing whether a tree pattern, P, is contained in another, \({Q\in \mathcal{C}}\), under an acyclic schema graph G, can be reduced to testing whether P _G , a transformed version of P, is contained in Q without any schema graph, provided that the distinguished node of P is not labeled *. We then show that, under G, the maximal contained rewriting (MCR) of a tree pattern Q using a view V can be found by finding the MCR of Q using V _G without G, when there are no *-nodes on the distinguished path of V and no *-nodes in Q.     

Approximating the Metric TSP in Linear Time

Given a metric graph G=(V,E) of n vertices, i.e., a complete graph with a non-negative real edge cost function satisfying the triangle inequality, the metricity degree of G is defined as \(\beta=\max_{x,y,z\in V}\{\frac{c(x,y)}{c(x,z)+c(y,z)}\}\in[\frac{1}{2},1]\). This value is instrumental to establish the approximability of several NP-hard optimization problems definable on G, like for instance the prominent traveling salesman problem, which asks for finding a Hamiltonian cycle of G of minimum total cost. In fact, this problem can be approximated quite accurately depending on the metricity degree of G, namely by a ratio of either \(\frac{2-\beta}{3(1-\beta)}\) or \(\frac{3\beta^{2}}{3\beta^{2}-2\beta+1}\), for \(\beta<\frac{2}{3}\) or \(\beta\geq \frac{2}{3}\), respectively. Nevertheless, these approximation algorithms have O(n ³) and O(n ^2.5log?^1.5 n) running time, respectively, and therefore they are superlinear in the Θ(n ²) input size. Thus, since many real-world problems are modeled by graphs of huge size, their use might turn out to be unfeasible in practice, and alternative approaches requiring only O(n ²) time are sought. However, with this restriction, all the currently available approaches can only guarantee a 2-approximation ratio for the case β=1, which means a \(\frac{2\beta^{2}}{2\beta^{2}-2\beta+1}\)-approximation ratio for general β<1. In this paper, we show how to elaborate—without affecting the space and time complexity—one of these approaches, namely the classic double-MST heuristic, in order to obtain a 2β-approximate solution. This improvement is effective, since we show that the double-MST heuristic has in general a performance ratio strictly larger than 2β, and we further show that any alternative elaboration of it cannot lead to a performance ratio better than 2β?ε, for any ε>0. Our theoretical results are complemented with an extensive series of experiments, that show the practical appeal of our approach.