Parameterized Spanning Tree Congestion

We start by stating the main theorem of this subsection.

By taking the set of stars as $𝒞$, Theorem 1 implies the W[1]-hardness parameterized by distance to star forest.

If $𝒞$ is the set of complete graphs, Theorem 1 implies W[1]-hardness parameterized by cluster vertex deletion number [25]. In fact, as we will later see, the proof of Theorem 1 more strongly implies W[1]-hardness parameterized by twin-cover number [35].

For an edge-weighted graph $G=(V,E;\mathrm{w})$ with $\mathrm{w}:E\to {\mathbb{Z}}^{+}$, we define its spanning tree congestion by setting the congestion of an edge $e$ in a spanning tree $T$ of $G$ as ${\mathrm{cng}}_{G,T}(e)=\mathrm{w}(E(V(T_{e,1}),V(T_{e,2})))$, where $\mathrm{w}(F)={\sum }_{e\in F}\mathrm{w}(e)$ for $F\subseteq E$. The following proposition provides a connection between the weighted and the unweighted case.

In the following, we prove Theorem 1 by a reduction from Unary Bin Packing. Given unary encoded integers $t,a_1,\mathrm{\dots },a_n\in {\mathbb{Z}}^{+}$ with ${\sum }_{i\in [n]}{a}_i=tB$, Unary Bin Packing asks whether there is a partition $(A_1,\mathrm{\dots },A_t)$ of $[n]$ such that ${\sum }_{i\in A_j}{a}_i=B$ for each $j\in [t]$. It is known that Unary Bin Packing is W[1]-hard parameterized by $t$ [46]. We assume that $t\ge 3$ since otherwise the problem can be solved in polynomial time. We now proceed to presenting the reduction.

In this subsection we consider Spanning Tree Congestion parameterized by the modular-width of the input graph [34]. We prove that the problem remains NP-complete even on graphs of modular-width at most $4$; there is no graph of modular-width $3$ since there is no prime graph with three vertices, therefore our result leaves open the case of graphs of modular-width at most $2$. Our result, along with the fact that graphs of modular-width at most $4$ have clique-width at most $3$ (Theorem 8), improves upon previous work by Okamoto et al. [61], who showed that the problem is NP-hard for graphs of clique-width at most $3$. As a matter of fact, the graph we construct has linear clique-width [31] at most $3$, thus directly improving over said result. Nevertheless, Theorem 8 is an interesting result in its own right which we were not able to find in the literature. Furthermore, the family of graphs constructed by our reduction has shrub-depth at most $2$ [36, 37], therefore yielding para-NP-hardness for this parameterization as well.

In the following, we mostly follow the proof of Theorem 1 by setting $𝒞$ to be the class of all complete graphs, albeit with a few adaptations. First, the starting point of our reduction is the strongly NP-complete $3$-Partition problem. Second, we notice that even though the edge-weighted graph $G$ produced in the proof of Theorem 1 has modular-width $2$ when $𝒞$ is the class of complete graphs (let one module contain the vertices of $Q$ and the other the rest), that is not the case for the unweighted graph $G^{\prime }$ produced by Proposition 4. In order to overcome this bottleneck, we emulate the weights of the edges by introducing a sufficiently large clique in our construction.

Given $3n$ unary encoded (not necessarily distinct) integers $a_i\in {\mathbb{Z}}^{+}$ for $i\in [3n]$, where ${\sum }_{i\in [3n]}{a}_i=nB$ and for all $i\in [3n]$, $3$-Partition asks whether there is a partition $(A_1,\mathrm{\dots },A_n)$ of $[3n]$ such that ${\sum }_{i\in A_j}{a}_i=B$ for all $j\in [n]$; notice that the bounds on the values of $a_i$ imply that if ${\sum }_{i\in A_j}{a}_i=B$, then $|A_j|=3$. It is well-known that $3$-Partition is strongly NP-complete [39, Theorem 4.4].

The last result of Section 3 is the NP-hardness on graphs of constant maximum degree. We first present an alternative gadget for the double-weighted edges which we subsequently use in our proof.

In this section, we prove the following theorem:

Before we proceed with the formal proof of the theorem, we will give an intuition of the algorithm. Following the usual structure for bounded-treewidth graphs, we will use dynamic programming to compute solutions to the subgraphs corresponding to subtrees of the tree decomposition $𝒯$. For each such subgraph, we consider different possibilities for the solution to manifest on the root bag of the subtree; these different possibilities, which we call states, represent equivalent classes of solutions that are “compatible” with respect to the rest of the graph, and thus it is sufficient to compute a feasible solution for each such class.

To obtain the algorithm, we simply need to specify the states, as well as how to recursively obtain feasible solutions for each. Our states are composed of a tree, which we call the skeleton, as well as values of congestion for each of its edges. The skeleton of a solution $T$ for a given bag $X_t$ intuitively represents how $T$ connects the vertices of $X_t$, and it can be obtained by contracting the vertices in $V\setminus X_t$ that have degree 1 or 2 in $T$. Thus, the skeleton is a tree containing the vertices in $X_t$, plus at most $|X_t|$ vertices with degree at least $3$. The congestion values correspond to the congestion induced on an edge by edges in ${𝒯}_t$, the subtree of $𝒯$ rooted at $t$.

There is one further particularity that we must consider: when constructing a skeleton from a solution, some of the resulting edges may represent paths in the subtree rooted at $t$, while others represent paths outside of this subtree. Thus, we label each edge of the skeleton with one of three types: a present edge is simply an edge between two vertices in $X_t$; a past edge represents a path in ${𝒯}_t$; and a future edge represents a path outside ${𝒯}_t$, that is, one that is not (yet) in the solution, but that must be added to make it compatible with the state. We similarly label the vertices with the type present if they are in $X_t$, past if they are not in $X_t$ but in ${𝒯}_t$, and future otherwise.

Throughout the section, we assume familiarity with the definition and usual notation for treewidth (see e.g. [21, Chapter 7]). When referring to subgraphs of $G$, we often refer to subgraphs induced by subtrees of $𝒯$: we denote by ${𝒯}_t$ the subtree of $𝒯$ rooted at $t$, and by $G[S]$ the subgraph of $G$ induced by the vertices contained in bags of $S$, i.e. the subgraph $G\left[{\bigcup }_{t\in S}{X}_t\right]$; for convenience of notation, we write $G[{𝒯}_t]$ instead of $G[V({𝒯}_t)]$.

The algorithm starts by computing a nice tree decomposition $(𝒯,𝒳)$ for $G$ with width at most $2w+1$ and at most $𝒪(nw)$ bags, which can be computed in time $2^{𝒪(w)}\cdot n$ [50].

We now formalize the definition of skeleton:

We define a dynamic programming table $D$ with entries for every node $t\in 𝒯$ and every triple $(S,\mathrm{\ell },c)$, where $(S,\mathrm{\ell })$ is a skeleton for $G[X_t]$ and $c:E(S)\to [0,k]$ is a function assigning a congestion to each edge. Informally, $D[t,(S,\mathrm{\ell },c)]$ represents a forest $F\subseteq G[{𝒯}_t]$ such that $F\cup {\mathrm{\ell }}^{-1}(1)$ is a solution of congestion at most $k$ for $G[{𝒯}_t]$, and the congestion $c(uv)$ on an edge of the skeleton corresponds to the maximum congestion of the $u$-$v$-path in $F$. We formalize the desired properties by the definition below:

Before we describe the recursive rules of our algorithm, we show an operation called simplification which takes a quasi-skeleton and transforms it into a skeleton, which is necessary to keep the number of skeletons small enough.

We will now see how to construct the entries $D[t,(S,\mathrm{\ell },c)]$ recursively:

• $\mathrm{■}$

  Leaf $t$: the only allowed skeleton is $S=(\mathrm{\varnothing },\mathrm{\varnothing })$, and $D[t,(S,\mathrm{\varnothing },\mathrm{\varnothing })]=(\mathrm{\varnothing },\mathrm{\varnothing })$.

• $\mathrm{■}$

  Forget node $t$: let $t^{\prime }$ be the child of $t$ and let $\{v\}=X_{t^{\prime }}\setminus X_t$. For any solution $D[t^{\prime },(S^{\prime },{\mathrm{\ell }}^{\prime },c^{\prime })]$, if $v$ has an incident edge with label $1$, the solution is invalid; otherwise, we set $D[t,(S,\mathrm{\ell },c)]=D[t^{\prime },(S^{\prime },{\mathrm{\ell }}^{\prime },c^{\prime })]$ for $(S,\mathrm{\ell },c)$ obtained as follows:

  1. 1.

     we start with $(S,\mathrm{\ell },c)=(S^{\prime },{\mathrm{\ell }}^{\prime },c^{\prime })$;

  2. 2.

     we add the congestion corresponding to the forgotten vertex $v$: for any edge $uv\in E(G)$, $u\in X_t$, increment $c(e)$ on each edge $e$ on the $u$-$v$-path in $S$; if $c(e)>k$ for any edge, the solution is invalid and the process stops;

  3. 3.

     then we mark $v$ as a past vertex ($\mathrm{\ell }(v)=-1$) and apply simplification.

• $\mathrm{■}$

  Introduce node $t$: let $t^{\prime }$ be the child of $t$ and let $\{v\}=X_t\setminus X_{t^{\prime }}$. For any $(S,\mathrm{\ell },c)$, we obtain $(S^{\prime },{\mathrm{\ell }}^{\prime },c^{\prime })$ from $(S,\mathrm{\ell },c)$ by setting ${\mathrm{\ell }}^{\prime }(v)=1$ and applying simplification. If $D[t^{\prime },(S^{\prime },{\mathrm{\ell }}^{\prime },c^{\prime })]$ exists, we construct $D[t,(S,\mathrm{\ell },c)]$ from $D[t^{\prime },(S^{\prime },{\mathrm{\ell }}^{\prime },c^{\prime })]$ by adding the vertex $v$ and every of its incident edges $e\in E(S)$ with label $\mathrm{\ell }(e)=0$.

• $\mathrm{■}$

  Join node $t$: given solutions $D[t_1,(S,{\mathrm{\ell }}_1,c_1)]$, $D[t_2,(S,{\mathrm{\ell }}_2,c_2)]$, a valid solution can be obtained if $c_1(e)+c_2(e)\le k$, if ${\mathrm{\ell }}_1(x)=-1$ implies ${\mathrm{\ell }}_2(x)=1$ and vice-versa ($x\in V(S)\cup E(S)$), and ${\mathrm{\ell }}_1(e)=0$ if and only if ${\mathrm{\ell }}_2(e)=0$.

  We define $\mathrm{\ell }(x)=\min \{{\mathrm{\ell }}_1(x),{\mathrm{\ell }}_2(x)\}$, $x\in V(S)\cup E(S)$ and $c(e)=c_1(e)+c_2(e)$, $e\in E(S)$, and set $D[t,(S,\mathrm{\ell },c)]=D[t_1,(S,{\mathrm{\ell }}_1,c_1)]\cup D[t_2,(S,{\mathrm{\ell }}_2,c_2)]$.

To obtain a solution to the problem, we simply compute $T=D[r,(\mathrm{\varnothing },\mathrm{\varnothing },\mathrm{\varnothing })]$. If $T$ is a consistent solution, then it is a forest containing the vertices $V(G)$ by Property 1, it is a tree by Property 4, and has congestion at most $k$ by Property 7. We therefore conclude that $T$ is a spanning tree of $G$ with congestion at most $k$, as desired.

Lemmas 18, 19, and 20 show that $T$ is indeed a consistent solution, that if there is a feasible solution then our algorithm can always find it, and that the algorithm runs in the stated running time.

In this section we leverage the algorithm of Theorem 14 to obtain two further results. On the one hand, we observe that the FPT algorithm of Theorem 14 relies on two parameters (treewidth and the optimal congestion), but it is likely impossible to improve this to an exact algorithm parameterized by treewidth alone (indeed, we saw that Theorem 1 implies that the problem is hard even for parameters much more restricted than treewidth). We are therefore motivated to consider the question of approximation and present an FPT approximation scheme parameterized by treewidth alone. Our algorithm is based on a combination of the algorithm of Theorem 14 together with a technique introduced in [54] (later also used among others in [3, 4, 19, 55]) which allows us to perform dynamic programming while maintaining approximate values for the congestion. The end result is an FPT approximation scheme, which for any $\epsilon >0$ is able to return a $(1+\epsilon )$-approximate solution in time ${(w/\epsilon )}^{𝒪(w)}{n}^{𝒪(1)}$, that is, FPT in $w+\frac{1}{\epsilon }$.

Having established this, we obtain a second extension of Theorem 14, to the more general parameter clique-width. Here, we rely on a Win/Win argument: suppose we are given an input graph $G$ of clique-width $w$ and are asked if a tree of congestion $k$ can be found; if $G$ contains a large bi-clique (in terms of $k$), then we show that this can be found and we can immediately say No; otherwise, by a well-known result of Gurski and Wanke [42], we infer that the graph actually has low treewidth, so we can apply Theorem 14.