Connected Partitions via Connected Dominating Sets

Let $T_1$ be the dominating tree that contains $k$ terminal vertices. First we add all the vertices of $T_1$ to one of the $k$ vertex sets while maintaining the connectivity of each set. There exist $k-1$ dominating trees that have no terminal vertex. Now, we map these $k$ vertex sets to one of these $k-1$ dominating trees. We aim to fulfill the vertex set to its demand while using the corresponding dominating tree.

We use an iterative procedure that first assigns (but does not add) neighbors for each vertex set to these $k-1$ dominating trees, and then we add assigned vertices to each vertex set whose demand is not met by the assignment. Now, to fulfill the demand of each such vertex set, we use its corresponding dominating tree while preserving the connectivity of the vertex set. At the end of this procedure, each part is either full or contains a whole dominating tree (apart from the one that was not assigned to any tree). The remaining vertices are arbitrarily added to the non-full sets, as each contains a dominating tree, apart from the one that has not been assigned a tree, for which we have ensured that there are enough adjacent vertices left.

The algorithm receives an instance of GL-Partition, $(G,k,C,N)$, where $C=\{c_1,\mathrm{\dots },c_k\},N=\{n_1,\mathrm{\dots },n_k\}$ and a set of dominating trees $𝒯=\{T_1,\mathrm{\dots },T_k\}$ as an input such that such that $G$ is $k$-connected graph and $C\subseteq T_1$.

It is important to note that during this description of the algorithm, every time we add a vertex to a vertex set, it is implied that we also check whether the condition of having $l$ full sets say $V_1,\mathrm{\dots },V_l$, intersecting exactly $l$ of the dominating trees, say $T_1,\mathrm{\dots },T_l$ is met. If yes, then we output those $l$ full sets and return an instance of the original problem, $G-{\cup }_{i=1}^l{V}_i$ and $k-l$, $𝒯=𝒯\setminus \{T_{k-l},\mathrm{\dots },T_k\}$, $C=C\setminus \{c_{k-l},\mathrm{\dots },c_k\}$ and $N=N\setminus \{n_{k-l},\mathrm{\dots },n_k\}$. We moreover assume that every time we add a vertex we also check if a set meets its size demand and if so we add it to the set $\mathrm{𝖥𝗎𝗅𝗅}$ that includes all the connected vertex sets that satisfy their size demands. We denote this procedure of adding a vertex $u$ to set $V$ by $\text{Add}(V,u)$ (similarly $\text{Add}(V,U)$ when we have a vertex set $U$ instead of singleton $\{u\})$. Similarly every time we remove a vertex from some set we check if it is in $\mathrm{𝖥𝗎𝗅𝗅}$ and if yes, we remove the set from $\mathrm{𝖥𝗎𝗅𝗅}$. We denote this procedure of removing vertex $u$ from the set $V$ by $\text{Remove}(V,u)$.

Step 1

We initialize each set $V_i$ to contain the corresponding terminal vertex $c_i$ for all $i\in [k]$ and then add the vertices of $T_1\setminus C$ one by one to a vertex set that it is adjacent to (based only on the adjacencies occurring by $T_1$). Next, we add the vertices of $V(G)\setminus V(𝒯)$ to an adjacent set one by one.

Step 2

Each vertex of $𝒯\setminus T_1$ is assigned through a function $\mathrm{𝖵𝗅𝖺𝖻𝖾𝗅}$ to an adjacent vertex set. Depending on whether the amount of vertices assigned to some vertex set is less than the vertices needed to be added for the set to satisfy its demand or not, the set is categorized in the set $\mathrm{𝖴𝗇𝖽𝖾𝗋}$ or $\mathrm{𝖮𝗏𝖾𝗋}$ respectively (Algorithm 1).

Step 3

Through the function $\mathrm{𝖳𝗅𝖺𝖻𝖾𝗅}$ each set in $\mathrm{𝖴𝗇𝖽𝖾𝗋}$ is assigned one of the trees in $𝒯\setminus T_1$. Then, one vertex of each such tree adjacent to the corresponding set is added. Priority is given to the vertices assigned to this set through the function $\mathrm{𝖵𝗅𝖺𝖻𝖾𝗅}$. However, if no such vertex exists, another adjacent vertex is arbitrarily chosen to be added, and we change the value of this vertex in the function $\mathrm{𝖵𝗅𝖺𝖻𝖾𝗅}$ accordingly. If this results in a set moving from $\mathrm{𝖮𝗏𝖾𝗋}$ to $\mathrm{𝖴𝗇𝖽𝖾𝗋}$, we again assign a tree to this set (that has not been assigned to any other set) through the function $\mathrm{𝖳𝗅𝖺𝖻𝖾𝗅}$ (Algorithm 1).

Step 4

For each tree assigned to some set, we consider its vertices not belonging in that set one by one and add them to that set as long as the set connectivity is preserved. Again, if, during this procedure, a set moves from $\mathrm{𝖮𝗏𝖾𝗋}$ to $\mathrm{𝖴𝗇𝖽𝖾𝗋}$, go to the previous Step. Repeat this procedure until each set in $\mathrm{𝖴𝗇𝖽𝖾𝗋}$ is either full or contains a whole tree (Algorithm 2).

Step 5

Add each of the remaining vertices, the ones not added to any set, to an adjacent non full set one by one (Algorithm 2).

Step 6

Output the $k$ sets created.

As Step 1 works in a straightforward way, we do not provide a pseudocode for it. We describe in the proof of the lemma below how this can be done in polynomial time. In the main algorithm, we refer to this procedure as $\text{AddTrees}(G,C,𝒯)$ that returns the sets $V_1,\mathrm{\dots },V_k$.

Algorithm 1 realizes the two next steps of Algorithm 3. In particular, first each remaining vertex of the graph is assigned to some set through $\mathrm{𝖵𝗅𝖺𝖻𝖾𝗅}$ and then each set is categorized in $\mathrm{𝖮𝗏𝖾𝗋}$ or $\mathrm{𝖴𝗇𝖽𝖾𝗋}$ depending on the number of vertices assigned to it. Then, for each set in $\mathrm{𝖴𝗇𝖽𝖾𝗋}$ the assigned vertices are added and through $\mathrm{𝖳𝗅𝖺𝖻𝖾𝗅}$ we assign a distinct tree each such set. Afterwards we ensure that each set in $\mathrm{𝖴𝗇𝖽𝖾𝗋}$ contains a vertex from its assigned tree.

It is easy to notice that Step 2 runs in polynomial time. In order to prove the correctness of Step 3 in Lemma 13, it suffices to show that there are at most $k-1$ sets in $\mathrm{𝖴𝗇𝖽𝖾𝗋}$ and this property is not affected while ensuring that each vertex set contains a vertex from the corresponding through $\mathrm{𝖳𝗅𝖺𝖻𝖾𝗅}$ tree. This part of the algorithm also runs in polynomial time because each set in $\mathrm{𝖴𝗇𝖽𝖾𝗋}$ is considered at most once and a set from $\mathrm{𝖮𝗏𝖾𝗋}$ might move to $\mathrm{𝖴𝗇𝖽𝖾𝗋}$ but once a set is in $\mathrm{𝖴𝗇𝖽𝖾𝗋}$ it will never move to $\mathrm{𝖮𝗏𝖾𝗋}$.

First notice that $G[V_i\cup \mathrm{𝖵𝗅𝖺𝖻𝖾𝗅}(V_i)]$ is connected for all $i\in [k]$, by the definition of the function $\mathrm{𝖵𝗅𝖺𝖻𝖾𝗅}$. We now show that there is at least one vertex set in $\mathrm{𝖮𝗏𝖾𝗋}$. Assume that there is no set in $\mathrm{𝖮𝗏𝖾𝗋}$ and hence $n_i-|V_i|>|\mathrm{𝖵𝗅𝖺𝖻𝖾𝗅}(V_i)|$ for all $i\in [k]$. Then ${\sum }_{i=1}^k{n}_i-|V_i|>{\sum }_{i=1}^k|\mathrm{𝖵𝗅𝖺𝖻𝖾𝗅}(V_i)|\Rightarrow n>{\sum }_{i=1}^k|\mathrm{𝖵𝗅𝖺𝖻𝖾𝗅}(V_i)|+{\sum }_{i=1}^k|V_i|=n$ which is a contradiction. This implies that regardless of whether a set moves from $\mathrm{𝖮𝗏𝖾𝗋}$ to $\mathrm{𝖴𝗇𝖽𝖾𝗋}$, as long as all vertices of $G$ are assigned to the sets $V_1,\mathrm{\dots },V_k$, one of these sets will be in $\mathrm{𝖮𝗏𝖾𝗋}$.

In the loop in line 17, we consider each tree assigned to some vertex set and first check whether this vertex set already contains some vertex of the tree. If yes, our lemma is satisfied. Otherwise, since the tree is dominating, there exists at least one vertex adjacent to the part of the vertex set intersecting $T_1$. This vertex is already added to some vertex set in $\mathrm{𝖴𝗇𝖽𝖾𝗋}$ or assigned to one in $\mathrm{𝖮𝗏𝖾𝗋}$. If it belongs in some set in $\mathrm{𝖮𝗏𝖾𝗋}$, then we simply add it to the vertex set. Then we remove this vertex from the set that occurs from the assignment $\mathrm{𝖵𝗅𝖺𝖻𝖾𝗅}$ for the set previously in $\mathrm{𝖮𝗏𝖾𝗋}$, and we check to see if it now meets the condition for this set belonging to $\mathrm{𝖴𝗇𝖽𝖾𝗋}$. If yes, we go to line 12 to deal with this set similarly. Repeating this procedure for the other sets in $\mathrm{𝖴𝗇𝖽𝖾𝗋}$ does not affect them as every vertex set currently in $\mathrm{𝖴𝗇𝖽𝖾𝗋}$ already contains all the vertices assigned to it through the function $\mathrm{𝖵𝗅𝖺𝖻𝖾𝗅}$. Moreover, since in this step, we add a vertex to a vertex set, we also check if this set becomes full and intersects exactly one dominating tree. If that is true, we restart the algorithm for the adjusted values of $k$, $G$, $𝒯$, and $𝒞$.

Otherwise, if the adjacent vertex is part of some other set in $\mathrm{𝖴𝗇𝖽𝖾𝗋}$, we add it to our current set and remove it from the previous one (again checking if the condition for restarting the algorithm is met). Moreover, we remove it from the set created through the function $\mathrm{𝖵𝗅𝖺𝖻𝖾𝗅}$ to avoid this vertex from existing in two sets (in case we go to line 12) in some other iteration of this loop. Note that sets initially in $\mathrm{𝖴𝗇𝖽𝖾𝗋}$ might be added in $\mathrm{𝖥𝗎𝗅𝗅}$ or removed from it depending on whether we add or remove vertices from them, but they will never go from $\mathrm{𝖴𝗇𝖽𝖾𝗋}$ to $\mathrm{𝖮𝗏𝖾𝗋}$ as we need to maintain the property that each set in $\mathrm{𝖮𝗏𝖾𝗋}$ contains no vertices from $T_2,\mathrm{\dots },T_k$. $◀$

Algorithm 2 realizes essentially the last two steps of the algorithm and either returns the desired partition of size $k$ or a smaller instance of a more general problem. First we ensure that each set in $\mathrm{𝖴𝗇𝖽𝖾𝗋}$ is either full or contains the dominating tree assigned to it through $\mathrm{𝖳𝗅𝖺𝖻𝖾𝗅}$. This is done by considering each set in $Under$ separately and then adding the neighboring vertices of the corresponding tree one by one. If during this procedure we “steal” a vertex assigned in some set in $\mathrm{𝖮𝗏𝖾𝗋}$ and this causes it to move to $\mathrm{𝖴𝗇𝖽𝖾𝗋}$ we run Algorithm 1 starting from line 13 (only running the loop of line 12 once, for the set that moved to $\mathrm{𝖴𝗇𝖽𝖾𝗋}$). This happens at most once for each set hence this part of Algorithm 2 runs in polynomial time. In the last part of this algorithm we simply add the remaining vertices to some adjacent non full set, first based on their assignment through $\mathrm{𝖵𝗅𝖺𝖻𝖾𝗅}$ and then based on the adjacencies in $G$.

In order to see that the loop in line 1 terminates, it suffices to notice that it only considers sets in $\mathrm{𝖴𝗇𝖽𝖾𝗋}$ and the value of ${\sum }_{i=2}^k|T_i^{\prime }\cap {\mathrm{𝖳𝗅𝖺𝖻𝖾𝗅}}^{-1}(T_1)|$.

We start by considering the vertex set $V_j$ such that $\mathrm{𝖳𝗅𝖺𝖻𝖾𝗅}(V_j)=T_i$ for some value of $i$. Due to Lemma 13, we know that $T_i$ is either completely contained in $V_j$, in which case we do nothing and we proceed to consider the next tree, or it has a vertex of $T_i$ that is adjacent to $V_j\cap T_1$ and not in $V_j$. We then add that vertex to $V_j$ in the same manner as in the loop in line 17 of Algorithm 1 depending on whether this vertex belongs already in some set or not.

Notice that this action preserves the connectivity of the set $V_j$ due to the way the vertex is chosen and also does not affect the connectivity of other sets as this is based only on the adjacencies of the parts of each vertex set intersecting $T_1$, which is not affected. Moreover it increases the value of ${\sum }_{i=2}^k|T_i\cap {\mathrm{𝖳𝗅𝖺𝖻𝖾𝗅}}^{-1}(T_1)|$ by $1$, which ensures that this loop terminates. Again, every time we add a vertex to a vertex set, it is implied that we also check if that set should meets its size demand and should be added to $\mathrm{𝖥𝗎𝗅𝗅}$ and also if the condition to terminate and output $l$ full sets and a smaller instance of the general problem is met. $◀$ Now that we have proved the correctness of Description of Algorithm 3., notice that in the last part of Algorithm 2 each non full set either contains a whole dominating tree or is adjacent to at least as many available vertices as it needs for its size demand to be met. We first start by the second case in which we add the assigned vertices to the set one by one until it is full. Then we are left with the case where each non full set contains a dominating tree, in which we can greedily add adjacent vertices to each such set one by one until all of them meet their size demands.

We now put everything together and provide the main algorithm of this section.

In the next section we tackle the more general instance in which there is a dominating tree that contains strictly less than $k$ terminals and some other contains at least one by showing that we are able to iteratively find a smaller instance in which all the terminals are contained in some dominating tree and then employ the algorithm developed in this section.

The Algorithm receives as input a GL-Partition instance $(G,k,C,N)$, where $C=\{c_1,\mathrm{\dots },c_k\}$, $N=\{n_1,\mathrm{\dots },n_k\}$, and a set of $k$ vertex-disjoint dominating trees $𝒯=\{T_1,\mathrm{\dots },T_k\}$ separated into three sets ${𝒯}_0,{𝒯}_1,{𝒯}_{>1}$ depending on how many terminal vertices they contain. It is important to note that, like in the previous section, during this description of the algorithm, every time we add a vertex to a vertex set, it is implied that we also check if the condition of having $l$ full sets say $V_1,\mathrm{\dots },V_l$, intersecting exactly $l$ of the dominating trees, say $T_1,\mathrm{\dots },T_l$ is met. If yes, then we output those $l$ full sets and restart the algorithm for $G-{\cup }_{i=1}^l{V}_i$ and $k-l$, $𝒯=𝒯\setminus \{T_{k-l},\mathrm{\dots },T_k\}$, $C=\{c_{k-l},\mathrm{\dots },c_l\}$ and $N=\{n_{k-l},\mathrm{\dots },n_k\}$. For simplicity and space constraints, we do not include this in every step of this description nor in the pseudocodes provided in this section. We moreover assume both in pseudocodes of this section and in this description that every time we add a vertex we also check if a set meets its size demand and if so we add it to the set $\mathrm{𝖥𝗎𝗅𝗅}$ that includes all the connected vertex sets that satisfy their size demands. Similarly every time we remove a vertex from some set we check if it is in $\mathrm{𝖥𝗎𝗅𝗅}$ and if yes, we remove it from $\mathrm{𝖥𝗎𝗅𝗅}$.

Step 1

We first initialize each vertex set $V_i$ to contain the corresponding terminal vertex $c_i$, where $i\in [k]$. Then, for each tree in ${𝒯}_1\cup {𝒯}_{>1}$, we add its vertices one by one to a vertex set that it is adjacent to (based only on the adjacencies occurring only by the tree considered). Next, we add the vertices of $V(G)\setminus V(𝒯)$ to an adjacent set one by one.

Step 2

For each tree $T\in {𝒯}_{>1}$ that contains $l$ terminals, we create a tree set ${𝒯}^{\prime }$ containing $T$ and $l-1$ trees from ${𝒯}_0$, which we then remove from ${𝒯}_{>1}$ and ${𝒯}_0$ respectively. Among those sets, we choose one that has enough vertices available to satisfy the size demands of all of the $l$ vertex sets intersecting $T$. (Algorithm Choose a Tree Set)

Step 3

Call Algorithm 3 that has as input those $l$ dominating trees, the corresponding vertex sets and terminal vertices, while the graph we work on is the one that occurs from the union of those sets and trees. Notice that the sum of the demands of those sets might be less than the size of the graph but this does not affect the correctness of the algorithm.