Appendix C Linear savings, product-form running times and Max Leaf Spanning Tree
This appendix explains why Max Leaf Spanning Tree needs sample-dependent running times: its natural extension problem is W[1]-hard (Appendix C.1), and product-form running-time exponents certify nothing below a single unsampled call when \(k/n\le d/(bc)\), nor, when \(c=1\), for the worst solution size. The product-form analyses we tried had their numerical optimum at \(c=1\) (Appendix C.2). The proofs of Corollary 4.3 and of the converse part of Proposition 4.5 are in Appendices D.2.1 and D.2.2. We keep the notation of Section 4.
C.1 MaxLeaf-Extension is W[1]-hard
The applications of the paper concern Max Leaf Spanning Tree (MaxLeaf), here in its decision version: given a connected graph \(G\) and an integer \(\ell\), decide whether \(G\) has a spanning tree with at least \(\ell\) leaves. A leaf of a tree is a vertex of degree \(1\), and \(\operatorname{leaves}(T)\) denotes the set of leaves of a tree \(T\). The most direct way to apply Monotone Local Search to MaxLeaf is to sample vertices that are to become leaves and to complete the sample with an algorithm for the following extension problem.
Definition C.1 (MaxLeaf-Extension). MaxLeaf-Extension: given a graph \(G\), a set \(X\subseteq V(G)\) and an integer \(\ell'\ge0\), decide whether \(G\) has a spanning tree \(T\) with \(X\subseteq \operatorname{leaves}(T)\) and \(|\operatorname{leaves}(T)\setminus X|\ge\ell'\). The parameter is \(\ell'\).
The words “at least” matter: if exactly \(\ell'\) further leaves were required, the forward direction of the reduction below could fail, because vertices that receive no pendant subdivision vertex become additional leaves. MaxLeaf parameterized by \(\ell\) is fixed-parameter tractable, with an \(O^{*}(3.188^{\ell})\)-time algorithm by Zehavi (Zehavi 2018). We show that its extension problem parameterized by \(\ell'\) is not, unless \(\mathrm{FPT}=\mathrm{W}[1]\); in particular it has no algorithm with running time \(c^{\ell'}N^{O(1)}\), which is what the original Monotone Local Search (Fomin et al. 2019) would need.
In the framework of Definition 3.1, MaxLeaf is the implicit set system \(\Phi_{\mathrm{ML}}\) whose instances are pairs \((G,\ell)\) of a graph \(G\) and an integer \(\ell\ge0\), with universe \(V(G)\) and with solutions the sets \(L\subseteq V(G)\) with \(|L|=\ell\) and \(L\subseteq\operatorname{leaves}(T)\) for some spanning tree \(T\) of \(G\); on connected graphs, \(\Phi_{\mathrm{ML}}\)-Subset is the decision version above. Membership is decided in polynomial time: graphs with at most two vertices are checked directly (a one-vertex tree has no leaf, and both vertices of a two-vertex tree are leaves), and if \(|V(G)|\ge3\), such a tree \(T\) exists exactly when \(G-L\) is connected and every vertex of \(L\) has a neighbor outside \(L\). On an input \(((G,\ell),X,k)\), \(\Phi_{\mathrm{ML}}\)-Extension asks for \(Y\subseteq V(G)\setminus X\) with \(|Y|\le k-|X|\) and \(|X\cup Y|=\ell\) such that \(X\cup Y\subseteq\operatorname{leaves}(T)\) for some spanning tree \(T\). So the input is a no-instance if \(\ell<|X|\) or \(\ell>k\), and otherwise it is equivalent to the instance \((G,X,\ell-|X|)\) of MaxLeaf-Extension, since a spanning tree with at least \(\ell-|X|\) leaves outside \(X\) has a set of exactly \(\ell-|X|\) of them, and every such set is a valid \(Y\).
Theorem C.2 (MaxLeaf-Extension is W[1]-hard). MaxLeaf-Extension parameterized by \(\ell'\) is W[1]-hard. Consequently it has no algorithm with running time \(f(\ell')N^{O(1)}\), for any computable function \(f\), unless \(\mathrm{FPT}=\mathrm{W}[1]\).
Proof. We give a parameterized reduction from Independent Set parameterized by the solution size, which is W[1]-hard (Cygan et al. 2015). The idea is to subdivide every edge and to prescribe every subdivision vertex as a leaf: a leaf’s neighbor in a tree with at least three vertices is not a leaf, so the further leaves lie in \(V(G)\) and are pairwise non-adjacent in \(G\). Let \((G,k)\) be an instance, asking whether \(G\) has an independent set of size \(k\). If \(k\le0\) the answer is yes; if \(k\ge1\) and \(V(G)=\emptyset\) it is no. In these cases we output a single edge with \(X=\emptyset\) and \(\ell'=0\) (a yes-instance) or \(\ell'=3\) (a no-instance). So let \(k\ge1\) and \(|V(G)|\ge1\); the case \(k>|V(G)|\) needs no separate treatment.
Construction. Let \(G'\) be obtained from \(G\) by subdividing every edge \(e=uv\in E(G)\) with a new vertex \(x_e\) (adjacent to \(u\) and \(v\) only), adding a vertex \(r\) adjacent to every vertex of \(V(G)\), and adding a vertex \(z\) adjacent only to \(r\). Let \(X=\{z\}\cup\{x_e:e\in E(G)\}\), and output \((G',X,\ell')\) with \(\ell'=k\). This takes polynomial time, \(G'\) is connected, and the parameter is unchanged. Note that \(V(G')\setminus X=V(G)\cup\{r\}\).
Forward direction. Let \(S\) be an independent set of \(G\) with \(|S|=k\). Let \(T\) consist of the edge \(rz\), the edges \(rv\) for all \(v\in V(G)\), and, for each \(e=uv\in E(G)\), one edge \(x_ey_e\) with \(y_e\in\{u,v\}\setminus S\); such a \(y_e\) exists because \(S\) is independent, so \(u\) and \(v\) are not both in \(S\). Then \(T\) is connected, since every vertex is joined to \(r\) directly or through a vertex of \(V(G)\), and it has \(1+|V(G)|+|E(G)|=|V(G')|-1\) edges; hence \(T\) is a spanning tree of \(G'\). In \(T\) the vertex \(z\) and every \(x_e\) have degree \(1\), and every \(v\in S\) has degree \(1\), because its only edge in \(T\) is \(rv\) (no \(x_e\) is attached to a vertex of \(S\)). So \(X\cup S\subseteq \operatorname{leaves}(T)\), and \(|\operatorname{leaves}(T)\setminus X|\ge|S|=\ell'\) since \(S\cap X=\emptyset\).
Backward direction. Let \(T\) be a spanning tree of \(G'\) with \(X\subseteq \operatorname{leaves}(T)\) and \(|\operatorname{leaves}(T)\setminus X|\ge\ell'\), and put \(S'=\operatorname{leaves}(T)\setminus X\). Since \(|V(G)|\ge1\), the tree \(T\) has at least three vertices, so no two leaves of \(T\) are adjacent in \(T\) (two adjacent leaves would form a component with two vertices). The only neighbor of \(z\) in \(G'\) is \(r\), so \(rz\in E(T)\), and \(r\) is not a leaf because its neighbor \(z\in X\) is a leaf. Hence \(S'\subseteq V(G')\setminus(X\cup\{r\})=V(G)\). Let \(e=uv\in E(G)\). The vertex \(x_e\) is a leaf of \(T\), and its neighbor in \(T\) is \(u\) or \(v\); this neighbor is not a leaf, so \(u\) and \(v\) are not both in \(S'\). Thus \(S'\) is an independent set of \(G\) with \(|S'|\ge\ell'=k\), and any \(k\) of its vertices form an independent set of size \(k\).
Since parameterized reductions preserve membership in FPT, an algorithm with running time \(f(\ell')N^{O(1)}\) for MaxLeaf-Extension would give one with running time \(f(k)N^{O(1)}\) for Independent Set, and hence \(\mathrm{FPT}=\mathrm{W}[1]\). ∎
The map \((G',X,\ell')\mapsto((G',|X|+\ell'),X,|X|+\ell')\) takes polynomial time, keeps the parameter (the number \(k-|X|\) of further elements equals \(\ell'\)), and by the description of \(\Phi_{\mathrm{ML}}\)-Extension after Definition C.1 maps yes-instances of MaxLeaf-Extension to yes-instances of \(\Phi_{\mathrm{ML}}\)-Extension and no-instances to no-instances. So \(\Phi_{\mathrm{ML}}\)-Extension on inputs \((I,X,k)\), parameterized by \(k-|X|\), is W[1]-hard as well, which rules out the case \(b=d=1\) of Corollary 4.6 for \(\Phi_{\mathrm{ML}}\), under \(\mathrm{FPT}\ne\mathrm{W}[1]\). It does not rule out extension algorithms with \(b>1\) or \(d>1\), which the multivariate version allows, and an earlier unpublished attempt pursued exactly these. The next subsection records what is known about this route.
C.2 Limits of product-form running times
The product form is the case of Corollary 4.3 with the following parameters, which the discussion after Proposition C.4 uses.
Remark C.3 (Product form through linear savings). Let \(1\le d\le bc\) and \(0<k<n\), and put \(\sigma=k/n\). Let \(S\in\mathcal{F}_I\) with \(|S|=k\) be such that \(g\) has the product form (10) on all inputs \((I,X,k)\) with \(X\subseteq S\). Then every \(X\in\binom St\) has \(g(I,X,k)=n\log b+k\log c-t\log(bc/d)\), so (7) holds with equality for every \(t\), with \[\beta=\log b+\sigma\log c,\qquad\rho=\log\frac{bc}{d}\ge0,\qquad C=0,\qquad p=2^{-\rho}=\frac{d}{bc}.\] Since \(g\) is constant on each \(\binom St\), Jensen’s inequality in the proof of Corollary 4.3(1) is an equality, so the upper bound computed there is exact: \(G_k=2^{nF^*(\sigma)}\). The criterion \(\rho>\log(1/\sigma)\) of Corollary 4.3(2) reads \(\sigma>d/(bc)\).
Two exact statements limit what product-form running-time exponents can certify.
Proposition C.4 (Two limits of the product form). Let \(b,c,d\ge1\), \(0\le k\le n\), and let \(M_k\) be as in Proposition 4.5. Then:
(a) \(\mathrm{base}(b,c,d)\ge b\), with equality if and only if \(c=1\). If \(c=1\), then \(\max_{0\le k\le n}M_k=M_0=b^n\).
(b) Let \(1\le k\le n\). If \(k/n\le d/(bc)\), then \(M_k=b^nc^k\); if \(k/n>d/(bc)\), then \(M_k<b^nc^k\).
By (a), if \(c=1\), the main theorem and multivariate Monotone Local Search certify no running-time bound below the bound \(b^nN^{O(1)}\) of a single call of the extension algorithm with \(X=\emptyset\). Part (b) is a sampling threshold: \(b^nc^k\) is the value of \(2^{g(I,\emptyset,k)}\) for the unsampled call.
Proof. (a) Since \(\min(d,bc)\ge1>0\), \(\mathrm{base}(b,c,d)-b=\min(d,bc)(1-1/c)\) vanishes exactly when \(c=1\). If \(c=1\), then \(M_0=b^n\) by (11), and \(M_k\le \mathrm{base}(b,1,d)^n=b^n\) for all \(k\) by Proposition 4.5(b).
(b) Write \(a_t=\binom nt\binom kt^{-1}(d/(bc))^t\), so that \(M_k=b^nc^k\min_{0\le t\le k}a_t\) and \(a_0=1\). For \(0\le t<k\), \[\frac{a_{t+1}}{a_t}=\frac{n-t}{k-t}\cdot\frac{d}{bc},\] because \(\binom n{t+1}/\binom nt=(n-t)/(t+1)\) and \(\binom k{t+1}/\binom kt=(k-t)/(t+1)\). As \(k\le n\), the factor \((n-t)/(k-t)\) is at least \(n/k\) and is nondecreasing in \(t\). If \(k/n\le d/(bc)\), every ratio is at least \((n/k)(d/(bc))\ge1\), so the sequence \((a_t)\) is nondecreasing and \(\min_ta_t=a_0=1\). If \(k/n>d/(bc)\), then \(a_1=(n/k)(d/(bc))<1=a_0\), so \(M_k\le b^nc^ka_1<b^nc^k\). ∎
Part (b) is the exact, finite-\(n\) form of the following asymptotic observation: the limit of \(\frac1n\log\) of the term \(\binom nt\binom kt^{-1}b^{\,n-t}c^{\,k-t}d^{\,t}\) of the classical expression, for fixed \(k/n\) and \(t/n\), is a convex function of the sampling fraction \(t/n\) and is minimized at \(t=0\) exactly when \(k/n\le d/(bc)\). Both are the product-form case of Corollary 4.3(2): with \(\rho=\log(bc/d)\) and \(\sigma=k/n\) (Remark C.3), the condition \(\rho>\log(1/\sigma)\) reads \(k/n>d/(bc)\).
We complement Proposition C.4 with numerical evidence from a local numerical optimization (Appendix F): with the measure-and-conquer branching algorithm of Binkele-Raible and Fernau (Binkele-Raible and Fernau 2014) as a MaxLeaf-Extension algorithm, the prescribed leaves \(X\) as initial floating leaves, and a general linear measure optimized for the base \(b+d-d/c\), every variant we tried had its optimum at \(c=1\), where by Proposition C.4(a) multivariate Monotone Local Search certifies nothing below a single call of the extension algorithm with \(X=\emptyset\). A first-order sensitivity analysis indicates the reason: each branching that determines the base has a branch that creates no leaves and does not decrease \(\ell'\). This is evidence about the analyses we tried, not a theorem, and it is not used elsewhere; the resulting bound, \(O^{*}(1.8957^n)\) with a numerically computed base, is also weaker than \(O^{*}(1.8619^n)\) (Abu-Khzam, Mouawad, and Liedloff 2011).