# Polynomial time algorithm for a Bi-objective Spanning Star Forest Problem on Trees

Thanh Loan Nguyen, Viet Hung Nguyen

► To cite this version:

Thanh Loan Nguyen, Viet Hung Nguyen. Polynomial time algorithm for a Bi-objective Spanning Star Forest Problem on Trees. 2025. hal-05284724

HAL Id: hal-05284724

https://hal.science/hal-05284724v1

Preprint submitted on 26 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Polynomial time algorithm for a Bi-objective Spanning Star Forest Problem on Trees

Nguyen Thanh Loan¹ and Nguyen Viet Hung¹

INP Clermont Auvergne, Univ Clermont Auvergne, Mines Saint-Etienne, CNRS,
UMR 6158 LIMOS, 1 Rue de la Chebarde, 63178 Aubiere Cedex, France

thanh-loan.nguyen@doctorant.uca.fr

Corresponding author: viet_hung.nguyen@uca.fr

**Abstract.** A star is a graph in which all edges share a common endpoint, called the center, and a star forest is a collection of disjoint stars. Given a connected graph with positive edge weights, a spanning star forest (SSF) is a star forest that contains all nodes of the graph. The total weight of a SSF is the sum of its edge weights in the weighted case, and it is the number of its edges in the unweighted case. Recently, the minimum weight spanning star forest problem with a constraint on the number of centers has received attention. In the context of the automobile industry, Agra et al.[1] studied the problem with at most *k* centers and proved it to be NP-hard. In related works, [5] investigated a variant with exactly *k* centers. However, both works require specifying the value of *k* in advance, and no criterion is provided for how *k* should be chosen.

To avoid the need to predefine *k*, we study the *Bi-objective Spanning Star Forest Problem* (BSSFP), which aims to minimize the number of centers and the total edge weight simultaneously. Since the minimum version with bounded *k* centers is NP-hard, the BSSFP is also NP-hard on general graphs. To the best of our knowledge, no efficient results are known related to the enumeration of efficient solutions of constrained SSF problems involving both weight and center constraints, even for restricted graph classes. We focus on the case where the input graph is a tree and prove that, in this setting, all efficient solutions of the BSSFP can be enumerated through a two-phase dynamic programming algorithm. This result provides the first polynomial-time procedure for the BSSFP on trees.

**Keywords:** Bi-objective Combinatorial Optimization · Spanning Star Forest · Automobile industry · Dynamic programming

# 1 Introduction

Given an undirected graph $G = (V, E)$, a *star* in $G$ is defined as either an isolated node or a subgraph where all edges share a common endpoint called the *center*. A *star forest* is a collection of disjoint stars. A *spanning star forest* (SSF) of $G$ is a star forest that contains all nodes of $G$. Let $w \in \mathbb{R}_+^{|E|}$ be the weight vector associated with edges in $G$. The total weight of a SSF is the sum
of its edge weights in the weighted case, and it is the number of its edges in
the unweighted case. The single objective problem of finding a maximum weight
star forest is a combinatorial optimization problem that has received significant
attention in recent years. C. T. Nguyen et al. [10] prove that the problem is APX-
hard. Moreover, they developed a linear-time algorithm for solving this problem
on trees, leading to a 1/2-approximation algorithm for general graphs. Recently,
V. H. Nguyen [11] extended this approach to cactus graphs by introducing a
polynomial-time algorithm for this class.

In contrast, the minimum weight star forest of SSF is trivial since a solution
where every node is isolated already forms a spanning star forest with total
weight zero and |V| centers. Thus, the minimum version is significant when the
number of centers is bounded. This version is motivated by practical applications
in the automobile industry. Agra et al. [1] considered the problem of automobile
option selection systems, where each center corresponds to a base configuration,
and showed that minimizing the weight of configurations with at most *k* centers
is NP-hard on general graphs by reduction from the 3-minimum cover problem.
They proposed an integer programming formulation and heuristic algorithms.
In a related work, [5] introduced the Optimal Diversity Management Problem
(ODMP), which requires choosing exactly *k* models (centers) and replacing every
other model by a compatible one of minimum weight. They proved that ODMP
is NP-hard on general cases, as it can be formulated as a *p*-median problem on
a partial-order graph. Their solution strategy is based on Lagrangian relaxation
and variable fixing, tackling the solution of large instances. Observe that in these
two works, the value of *k* must be known before solving the problem. However,
this raises a natural question: what criterion should be used to select *k*?

To avoid committing to a single value of *k* and to explore the full trade-off,
we introduce a minimum bi-objective version of this problem, which is called
*Bi-objective Spanning Star Forest Problem (BSSFP)*, where the number of cen-
ters and the total edge weight are minimized simultaneously. In the bi-objective
version, no constraint on the value of *k* needs to be specified, which avoids the
need to predefine *k* and allows a balanced exploration of trade-offs. For the
general graph, as both the minimum weight SSF with a bound on the number
of centers problem and the minimum number of centers problem (which corre-
sponds to maximizing the total weight in the unweighted case) are NP-hard, it
follows that the BSSFP is also NP-hard. In bi-objective optimization, feasible
solutions are compared under Pareto dominance. A solution is called *efficient*
(i.e., Pareto optimal) if no other solution improves one objective without wors-
ening the other. Efficient solutions are typically classified as either *supported*
*efficient solutions*, which can be obtained by solving scalarized single-objective
problems such as weighted sums and lying on the boundary of the convex hull
of the Pareto front, or *non-supported efficient solutions*, which correspond to
points lying in the interior of the convex hull of the Pareto front. For BSSFP,
identifying even an efficient solution is computationally challenging due to the
problem's NP-hardness.
Our work focuses on the case where $G$ is a tree. To the best of our knowledge, no efficient results are known related to the enumeration of efficient solutions of constrained SSF problems involving both weight and center constraints, even for restricted graph classes. The difficulty lies in the exponential growth of the solution space, which arises once a second objective is considered. To address this, we adopt the classical two-phase approach, a general framework for solving bi-objective combinatorial optimization problems [13]. Phase I enumerates all supported efficient solutions, which are obtained through weighted-sum scalarization [12], while Phase II extends the search to non-supported efficient solutions. Both phases reduce to solving single-objective subproblems on trees, which motivates the design of an efficient dynamic programming algorithm. Our main contribution lies in presenting that these subproblems can be solved exactly in polynomial time by a dynamic programming scheme inspired by C. T. Nguyen et al. [10] and V. H. Nguyen [11], but for the minimum version instead of the maximum one. A key idea is the use of Lagrangian relaxation to address the possible cases of the children in the tree. This relaxation allows each child to be considered independently, so that the cases of all children can then be combined systematically into the dynamic programming recurrence. As a result, we obtain a bottom-up recursion that can solve both scalarized formulations for Phase I and $\epsilon$-constraint formulations for Phase II.

In this paper, we consider an edge-weighted tree $T = (V, E, w)$. In combinatorial optimization, it is natural to consider the weight values $w$ as positive integers. The objectives of the BSSFP are to simultaneously minimize the total weight and the number of centers, which can be formulated as

$$ \min_{x \in \mathcal{X}} (f_1(x), f_2(x)), $$

where $f_1(x)$ represents the total weight, $f_2(x)$ represents the number of centers in the star forest, and $\mathcal{X}$ denotes the set of all feasible decision vectors associated with the total weight and the number of centers in spanning star forests in $T$. Since $w$ is a positive integer vector, the value of the objectives $f_1(x)$ and $f_2(x)$ is a non-negative integer. Let $(f_1, f_2) = (f_1(x), f_2(x))$ denote the objective values corresponding to a decision vector. Let $\mathcal{F}$ represent the set of pairs $(f_1, f_2)$ corresponding to all feasible decision vectors. This work characterizes the feasible solutions of the BSSFP by their objective pairs $(f_1, f_2)$ instead of explicitly listing the decision vectors. Accordingly, two feasible solutions that have the same objective pair $(f_1, f_2)$ are considered equivalent.

The remainder of this chapter is organized as follows. Section 2 introduces Phase I, which enumerates the supported efficient solutions of the BSSFP on trees. By Geoffrion's theorem [7], every optimal solution of a weighted-sum problem with positive weights is a supported efficient solution. To obtain these solutions, we design dynamic programming algorithms for the weighted sum subproblems using Lagrangian relaxation. Section 3 deals with Phase II, which enumerates the non-supported efficient solutions. In the bi-objective problem, each pair of consecutive supported solutions defines a region in the objective space that may contain non-supported solutions. We explore these regions using
the $\epsilon$-constraint approach [9], and the resulting subproblems are solved by dynamic programming algorithms specifically designed to address the constraint on the number of centers. Section 4 concludes the chapter and discusses possible directions for future research.

## 2 Phase I: Determination of supported efficient solutions

This section aims to identify all supported efficient solutions of BSSFP on trees. We first recall that a solution is supported if it is an optimal solution of a weighted sum scalarization of the total edge weight and the number of centers [12]. Given a tree $T = (V, E)$ with $|V| = n$, edge weights $w_{ij} \ge 0$ for all $ij \in E$, and a scalarization coefficient $\alpha \in [0, 1]$, the weighted sum problem is formally written as

$$W_{\alpha} = \min_{(f_1, f_2) \in \mathcal{F}} (1 - \alpha)f_1 + \alpha f_2.$$

We now present Procedure FIND_SUPPORTED(), an iterative algorithm for identifying the supported solutions of BSSFP, following the two-phase framework in [6]. The idea is to detect all values of $\alpha$ at which the optimal solution changes. We begin with the two extremes by solving $W_0 = \min f_1$ and $W_1 = \min f_2$, which return the endpoint solutions $(f_1^0, f_2^0)$ and $(f_1^1, f_2^1)$, respectively. Note that a solution where every node is isolated already forms a spanning star forest. Therefore, minimizing $f_1$ leads to the trivial solution $(f_1^0, f_2^0) = (0, |V|)$. Since $(f_1^0, f_2^0)$ and $(f_1^1, f_2^1)$ are two efficient solutions, it follows that $f_1^0 < f_1^1$ and $f_2^0 > f_2^1$. We keep these endpoints sorted by increasing $f_1$, and we place the segment between them into a working list of segments. While there is a segment $[(f_1^i, f_2^i), (f_1^j, f_2^j)]$, we test whether there is a new supported solution strictly between them. This solution is associated with the weight $\alpha$, where the two endpoints give the same weighted sum. Solving $(1 - \alpha)f_1^i + \alpha f_2^i = (1 - \alpha)f_1^j + \alpha f_2^j$ gives $\alpha = \frac{f_1^i - f_1^i}{(f_1^j - f_1^i) + (f_2^i - f_2^j)}$. We then solve $W_{\alpha}$ and obtain a solution $(f_1^m, f_2^m)$. If it is the same as one endpoint, then no new point lies inside the segment, and we close it. If it is different from both endpoints, we have found a new supported solution and insert this point between the two endpoints in the ordered list. Then we push the two new subsegments onto the working list to further subdivide them in the same way. The loop ends when the working list is empty.

Algorithm 1 begins by solving $W_0$ and $W_1$ to obtain the two extreme supported solutions $(f_1^0, f_2^0)$ and $(f_1^1, f_2^1)$, respectively. Line 3 initializes the supported efficient solution set $S$ with these two points and initializes the list $L$ with the segment between them. The loop then iteratively takes one segment: if the two endpoints share the same value in at least one objective, the segment is skipped; otherwise, the scalarization coefficient $\alpha$ is computed and $W_{\alpha}$ is solved to generate a candidate solution. In Line 10, if this point shares the same value in at least one objective with either endpoint, nothing is added, but if it is distinct, it is inserted into $S$ and the two resulting subsegments are added to $L$. The
<caption>**Algorithm 1** Enumerating supported efficient solutions via $W_\alpha$</caption>

**Input:** A weighted tree $T = (V, E, w)$.
**Output:** Ordered set $S$ of supported efficient solutions.
1: **procedure** FIND_SUPPORTED()  
2:     solve $W_0$ to get $(f_1^0, f_2^0)$; solve $W_1$ to get $(f_1^1, f_2^1)$  
3:     $S \leftarrow \{(f_1^0, f_2^0), (f_1^1, f_2^1)\}$ ordered by $f_1$, $L \leftarrow {[(f_1^0, f_2^0), (f_1^1, f_2^1)]}$  
4:     **while** $L \neq \emptyset$ **do**  
5:         select and remove $[(f_1^i, f_2^i), (f_1^j, f_2^j)] \in L$  
6:         **if** $\min \{|f_1^j - f_1^i|, |f_2^i - f_2^j|\} \le 0$ **then** go to line 4  
7:         **end if**  
8:         $\alpha = \frac{f_1^j - f_1^i}{(f_1^j - f_1^i) + (f_2^i - f_2^j)}$  
9:         solve $W_\alpha$ to get $(f_1^m, f_2^m)$  
10:        **if** $\min \{|f_1^m - f_1^i|, |f_2^i - f_2^j|, |f_1^m - f_1^j|, |f_2^m - f_2^i|\} \le 0$ **then** go to line 4  
11:        **else**  
12:            insert $(f_1^m, f_2^m)$ between endpoints in $S$  
13:            $L \leftarrow L \cup {[(f_1^i, f_2^i), (f_1^m, f_2^m)], [(f_1^m, f_2^m), (f_1^j, f_2^j)]}$  
14:            **end if**  
15:            **end while**  
16:            **return** $S$  
17:        **end procedure**

process repeats until no segments remain, at which point the algorithm returns
the complete set $S$ of supported efficient solutions.

We now propose a dynamic programming algorithm that solves $W_\alpha$ exactly in linear time for trees. Our approach is inspired by prior works on the maximum weight spanning star forest problem (MWSFP). C. T. Nguyen et al. [10] developed a dynamic programming algorithm for MWSFP on trees, exploiting their recursive structure through bottom-up computations on a rooted tree. Then, V. H. Nguyen [11] extended this approach to cactus graphs, which comprise edges or simple cycles, by recursively processing blocks with tailored dynamic programming for trees and cycles, maintaining linear-time complexity. However, in our case, we deal with the minimum version instead of the maximum one. We thus employ Lagrangian relaxation to address our problem. The recurrence formulas of our dynamic programming algorithm are given in the following lemma.

**Lemma 1.** For each node $u \in V$, let $C(u)$ denote the set of children of $u$, and let $T(u)$ denote the subtree rooted at $u$. We then define

* Center case $\Phi(u)$: value of $W_\alpha$ of spanning star forests in $T(u)$, given that $u$ is the center of a star with at least one child.

* Leaf case $\Psi(u)$: value of $W_\alpha$ of spanning star forests in $T(u)$, given that $u$ is a leaf in a star.

* Isolated case $\Omega(u)$: value of $W_\alpha$ of spanning star forests in $T(u)$, given that $u$ is isolated.
Then the following recurrence holds

$$ \Phi(u) = \alpha + \sum_{v \in C(u)} \sigma(v) + \min_{v \in C(u)} (\Omega(v) + (1 - \alpha)w_{uv} - \sigma(v)), $$

$$ \Psi(u) = \min_{v \in C(u)} \left[ (1 - \alpha)w_{uv} + \min\{\Phi(v), \Omega(v)\} + \sum_{x \in C(u) \setminus \{v\}} \min\{\Phi(x), \Psi(x), \Omega(x)\} \right], $$

$$ \Omega(u) = \alpha + \sum_{v \in C(u)} \min\{\Phi(v), \Psi(v), \Omega(v)\}, $$

where for each $v \in C(u)$, $\sigma(v) = \min\{\Phi(v), \Psi(v), \Omega(v) + (1 - \alpha)w_{uv}\}$.

*Proof.* For each $v \in C(u)$, we define the terms $A(v)$, $B(v)$ as follows

$$ A(v) = \min\{\Phi(v), \Psi(v), \Omega(v)\}, \text{ and } B(v) = \Omega(v) + (1 - \alpha)w_{uv}, $$

where $A(v)$ denotes the optimal value of $W_\alpha$ for $T(v)$ when the edge $uv$ is not used, and $B(v)$ denotes the value when $uv$ is used. Moreover, we define $\sigma(v) = \min\{A(v), B(v)\}$. We consider three possible roles of $u$.

* Center case $\Phi(u)$. For each $v \in C(u)$ decide whether to attach $v$ to $u$, let $\xi_{uv} \in \{0, 1\}$ be the binary variable associated to the occurrence of edge $uv$ in the star centered at $u$, subject to $\sum_{v \in C(u)} \xi_{uv} \ge 1$. The value of $W_\alpha$ on the subtree $T(u)$ in this case is $\alpha + \sum_{v \in C(u)} (A(v) + (B(v) - A(v))\xi_{uv})$. Then $\Phi(u)$ can be obtained by solving the following optimization problem

$$ (W(u)) \quad \min \left\{ \alpha + \sum_{v \in C(u)} (A(v) + (B(v) - A(v))\xi_{uv}) \right\} \quad \text{s.t.} \quad \sum_{v \in C(u)} \xi_{uv} \ge 1. $$

Relax $\sum_v \xi_{uv} \ge 1$ with multiplier $\lambda \ge 0$. Let $\mathcal{L}(\xi, \lambda)$ be the Lagrangian of problem $(W(u))$, then

$$ \mathcal{L}(\xi, \lambda) = \alpha + \sum_{v} A(v) + \lambda + \sum_{v} ((B(v) - A(v)) - \lambda) \xi_{uv}. $$

Moreover, since $\xi_{uv} \in \{0, 1\}$, we get that for each $v \in C(u)$

$$ \min_{\xi_{uv} \in \{0,1\}} ((B(v) - A(v)) - \lambda)\xi_{uv} = \min\{0, (B(v) - A(v)) - \lambda\}. $$

Hence, the dual problem of problem $(W(u))$ is

$$ \max_{\lambda \ge 0} \quad g(\lambda) = \alpha + \sum_{v} A(v) + \lambda + \sum_{v} \min\{0, (B(v) - A(v)) - \lambda\}. $$

An optimal solution $\lambda^*$ of this dual problem is $\lambda^* = 0$ if there exists $v$ with $B(v) \le A(v)$, and otherwise $\lambda^* = \min_v(B(v) - A(v))$. Since the feasible set
$\{\xi \in [0, 1]^{C(u)} : \sum_v \xi_{uv} \ge 1\}$ has integral extreme points, the relaxation is tight and the optimal value of this dual problem equals $\Phi(u)$. Hence, we get

$$ \begin{aligned} \Phi(u) = g(\lambda^*) &= \begin{cases} \alpha + \sum_v \min\{A(v), B(v)\}, & \text{if } \exists v \text{ with } B(v) \le A(v), \\ \alpha + \sum_v A(v) + \min_v(B(v) - A(v)), & \text{if } B(v) > A(v) \text{ for all } v. \end{cases} \\ &= \alpha + \sum_v \min\{A(v), B(v)\} + \min_v (B(v) - \min\{A(v), B(v)\}) \\ &= \alpha + \sum_{v \in C(u)} \sigma(v) + \min_{v \in C(u)} (\Omega(v) + (1-\alpha)w_{uv} - \sigma(v)). \end{aligned} $$

* Leaf case $\Psi(u)$. The node $u$ must attach to exactly one child. Let $\eta_{uv} \in \{0, 1\}$ be the binary variable associated to the occurrence of edge $uv$ when $u$ is a leaf attached to $v$ subject to $\sum_{v \in C(u)} \eta_{uv} = 1$. For every $v \in C(u)$, we denote

$$ \Delta(v) = (1 - \alpha)w_{uv} + \min\{\Phi(v), \Omega(v)\} - A(v). $$

Then $\Psi(u)$ can be obtained by solving the following optimization problem

$$ \min_{\eta \in \{0,1\}^{C(u)}} \sum_{x \in C(u)} A(x) + \sum_{v \in C(u)} \Delta(v) \eta_{uv} \quad \text{s.t.} \quad \sum_{v \in C(u)} \eta_{uv} = 1. $$

Relax $\sum_v \eta_{uv} = 1$ with multiplier $\mu \in \mathbb{R}$. Let $\mathcal{L}(\eta, \mu)$ be the Lagrangian of problem $(\mathcal{W}(u))$, then

$$ \mathcal{L}(\eta, \mu) = \sum_{x \in C(u)} A(x) + \mu + \sum_{v \in C(u)} (\Delta(v) - \mu) \eta_{uv}. $$

Note that for each $v$, we have

$$ \min_{\eta_{uv} \in \{0,1\}} (\Delta(v) - \mu) \eta_{uv} = \min\{0, \Delta(v) - \mu\}. $$

Thus, the dual problem of $(\mathcal{W}(u))$ is

$$ \max h(\mu) = \sum_{x \in C(u)} A(x) + \mu + \sum_{v \in C(u)} \min\{0, \Delta(v) - \mu\}. $$

The maximum of $h(\mu)$ is reached at $\mu^* = \min_v \Delta(v)$. Since the feasible set $\{\eta \in [0, 1]^{C(u)} : \sum_v \eta_{uv} = 1\}$ has integral extreme points, the optimal value of this dual problem equals $\Phi(u)$. Therefore, we have

$$ \begin{aligned} \Psi(u) = h(\mu^*) &= \sum_{x \in C(u)} A(x) + \min_{v \in C(u)} \Delta(v) \\ &= \sum_{x \in C(u)} A(x) + \min_{v \in C(u)} \left( (1 - \alpha)w_{uv} + \min\{\Phi(v), \Omega(v)\} - A(v) \right) \\ &= \min_{v \in C(u)} \left[ (1 - \alpha)w_{uv} + \min\{\Phi(v), \Omega(v)\} + \sum_{x \in C(u) \setminus \{v\}} A(x) \right]. \end{aligned} $$
* Isolated case $\Omega(u)$. The node $u$ forms a single-vertex star, hence

$$ \Omega(u) = \alpha + \sum_{v \in C(u)} A(v) = \alpha + \sum_{v \in C(u)} \min\{\Phi(v), \Psi(v), \Omega(v)\}. \quad \square $$

We now state Procedure 2 to determine the solution of the subproblem $W_\alpha$. This procedure traverses the tree in post-order so that each node is processed only after all of its children. Lines 2-4 address initialization: if a node is a leaf, the algorithm assigns the base values $(\Phi(u), \Psi(u), \Omega(u)) = (+\infty, 0, \alpha)$. Otherwise, the set of children $C(u)$ is identified for the recursive step. Line 5 records the children of $u$, and Lines 6-11 compute $(\Phi(u), \Psi(u), \Omega(u))$ according to the recurrence given in Lemma 1. Finally, the algorithm returns the optimal solution at the root by taking the minimum among these three values.

**Procedure 2** Algorithm for solving $W_\alpha$

**Input:** A tree $T = (V, E)$ with edge weights $w_{uv}$ and a coefficient $\alpha \in [0, 1]$.

**Output:** A spanning star forest that minimizes the weighted sum of the total weight and the number of centers, with $\alpha$ as the scalarization coefficient.

1. **for all** nodes $u \in V$ in post-order traversal **do**

2. **if** $C(u) = \emptyset$ **then**

3. $(\Phi(u), \Psi(u), \Omega(u)) \leftarrow (+\infty, 0, \alpha)$ go to line 6

4. **end if**

5. $C(u) \leftarrow$ set of children of $u$

6. **for all** $v \in C(u)$ **do**

7. $\sigma(v) \leftarrow \min\{\Phi(v), \Psi(v), \Omega(v) + (1 - \alpha)w_{uv}\}$

8. **end for**

9. $\Phi(u) \leftarrow \alpha + \sum_{v \in C(u)} \sigma(v) + \min_{v \in C(u)} (\Omega(v) + (1 - \alpha)w_{uv} - \sigma(v))$

10. $\Psi(u) \leftarrow \min_{v \in C(u)} [(1 - \alpha)w_{uv} + \min\{\Phi(v), \Omega(v)\} + \sum_{\substack{x \in C(u) \\ x \neq v}} \min\{\Phi(x), \Psi(x), \Omega(x)\}]$

11. $\Omega(u) \leftarrow \alpha + \sum_{v \in C(u)} \min\{\Phi(v), \Psi(v), \Omega(v)\}$

12. **end for**

13. **return** $\min\{\Phi(r), \Psi(r), \Omega(r)\}$, where $r$ is the root of the tree

**Theorem 1.** Procedure 2 solves the problem $W_\alpha$ in $O(n)$ time, where $n$ is the number of nodes in the tree.

*Proof.* The algorithm performs a single post-order traversal of $T$, computing $\Phi(u), \Psi(u)$, and $\Omega(u)$ for every $u \in V$ using the recurrences of Lemma 1. For a fixed $u$, all quantities required by these recurrences, including $\sum_{v \in C(u)} \sigma(v)$, the extremal term in $\Phi(u)$, and the unrestricted sums in $\Psi(u)$ and $\Omega(u)$, are obtained in one pass over $C(u)$, requiring $O(|C(u)|)$ time. Since $\sum_{u \in V} |C(u)| = n - 1$, the overall running time is $O(n)$, and the optimal objective value is obtained by a constant-time evaluation of $\min\{\Phi(r), \Psi(r), \Omega(r)\}$ at the root $r$. $\square$
### 3 Phase II: Determination of non-supported efficient solutions

Phase II determines the set of efficient solutions, which are in the triangle defined by two consecutive supported solutions ($f_1^i, f_2^i$) and ($f_1^j, f_2^j$), where we assume the solutions are ordered by increasing $f_2$ so that $f_2^i < f_2^j$. In order to do this, we first recall that an efficient solution is an optimal solution of a $\epsilon$-constraint problem [9]. For the BSSFP, this problem focuses on minimizing the total weight of a spanning star forest in the tree $T = (V, E)$ with edge weights $w$, subject to a bound on the number of centers $k$, i.e.,

$$ (\mathcal{P}_k) \quad \min \{f_1 : (f_1, f_2) \in \mathcal{F}, f_2 \le k\} $$

Algorithm 3 presents Procedure FIND_NONSUPPORTED(), which applies the $\epsilon$-constraint method [9] to enumerate the non-supported efficient solutions. Starting from two consecutive supported solutions ($f_1^i, f_2^i$) and ($f_1^j, f_2^j$), the procedure initializes $k = f_2^j - 1$ and sets $U = \emptyset$ as the set of non-supported solutions. At each step, problem $(\mathcal{P}_k)$ is solved to obtain a solution ($f_1^u, f_2^u$). If this solution is distinct from the endpoints, it is recorded as a non-supported efficient solution and added to the set $U$. After that, set $k = f_2^u - 1$ and continue the search. The loop continues until no integer $k$ remains strictly between $f_2^i$ and $f_2^j$, at which point all non-supported solutions in that range have been found.

**Algorithm 3** Enumerating non-supported efficient solutions via $(\mathcal{P}_k)$

**Input:** A weighted tree $T = (V, E, w)$ and two consecutive supported efficient solution ($f_1^i, f_2^i$), ($f_1^j, f_2^j$) with $f_2^i < f_2^j$ of BSSFP for $T$.

**Output:** Set $U$ of non-supported efficient solutions between ($f_1^i, f_2^i$), ($f_1^j, f_2^j$).

1: **procedure FIND_NONSUPPORTED()**

2: &nbsp;&nbsp;&nbsp;&nbsp; $U = \emptyset, k = f_2^j - 1$

3: &nbsp;&nbsp;&nbsp;&nbsp; **while** $k \ge f_2^i + 1$ **do**

4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; solve $(\mathcal{P}_k)$ to obtain solution ($f_1^u, f_2^u$)

5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; add ($f_1^u, f_2^u$) to $U$ and set $k = f_2^u - 1$

6: &nbsp;&nbsp;&nbsp;&nbsp; **end while**

7: **end procedure**

We then present a dynamic programming algorithm to solve $(\mathcal{P}_k)$, which minimizes the total weight of a spanning star forest in a rooted tree $T = (V, E)$ with edge weights $w_{uv}$, subject to at most $k$ centers. The algorithm also uses bottom-up dynamic programming with post-order traversal. The recurrence relations are stated in the following lemma.

**Lemma 2.** For each node $u \in V$ and $\ell \in \{0, 1, \dots, k\}$, let $C(u)$ denote the set of children of $u$, and let $T(u)$ denote the subtree rooted at $u$, we define

* Isolated case $\Omega(u, \ell)$: minimum weight (i.e., objective value of $(\mathcal{P}_k)$) in $T(u)$ with $u$ isolated and exactly $\ell$ centers.
* Leaf case $\Psi(u, \ell)$: minimum weight of spanning star forests in $T(u)$ with $u$ as a leaf in the star and exactly $\ell$ centers.

* Center case $\Phi(u, \ell)$: minimum weight of spanning star forests in $T(u)$ with $u$ as a star center (at least one child) and exactly $\ell$ centers.

For each $\ell \in \{0, 1, \dots, k\}$, let $\sigma(v, \ell) = \min\{\Phi(v, \ell), \Psi(v, \ell), \Omega(v, \ell)\}$. Then the following recurrences hold

$$ \Phi(u, \ell) = \min_{\substack{S \subseteq C(u), S \neq \emptyset \\ \sum_{x \in C(u)} \ell_x = \ell - 1 + |S|}} \left[ \sum_{v \in S} (w_{uv} + \Omega(v, \ell_v)) + \sum_{x \in C(u) \setminus S} \sigma(x, \ell_x) \right], $$

$$ \Psi(u, \ell) = \min_{\substack{v \in C(u), \{\ell_x\}_{x \in C(u)} \\ \sum_{x \in C(u)} \ell_x = \ell}} \left[ w_{uv} + \min\{\Phi(v, \ell_v), \Omega(v, \ell_v)\} + \sum_{x \in C(u), x \neq v} \sigma(x, \ell_x) \right], $$

$$ \Omega(u, \ell) = \min_{\substack{\{\ell_v\}_{v \in C(u)} \\ \sum_{v \in C(u)} \ell_v = \ell - 1}} \sum_{v \in C(u)} \sigma(v, \ell_v). $$

*Proof.* For each $v \in C(u)$ and $t \in \{0, \dots, k\}$, we let $\sigma(v, t) = \min\{\Phi(v, t), \Psi(v, t), \Omega(v, t)\}$, which is the optimal total weight in $T(v)$ when the edge $uv$ does not occur in the component containing $u$.

* Center case $\Phi(u, \ell)$. Let $\xi_{uv} \in \{0, 1\}$ be the binary variable associated to the occurrence of edge $uv$ in the star centered at $u$, with $\sum_v \xi_{uv} \ge 1$, and integers $\ell_v \ge 0$ for the number of centers used in $T(v)$. Then $\Phi(u, \ell)$ can be obtained by solving the following optimization problem

$$ \min_{\xi, \ell} \sum_{v: \xi_{uv} = 1} (w_{uv} + \Omega(v, \ell_v)) + \sum_{x: \xi_{ux} = 0} \sigma(x, \ell_x) \quad (2.1) $$

$$ \text{s.t.} \quad \sum_v \xi_{uv} \ge 1, \quad \sum_{x \in C(u)} \ell_x - |\{v: \xi_{uv} = 1\}| = \ell - 1. $$

Relax the two constraints with multipliers $\lambda \ge 0$ and $\gamma \in \mathbb{R}$. The Lagrangian of (2.1) is

$$ \mathcal{L}(\xi, \ell; \lambda, \gamma) = \sum_v \left( (1 - \xi_{uv})\sigma(v, \ell_v) + \xi_{uv}(w_{uv} + \Omega(v, \ell_v)) \right) + \lambda \left( 1 - \sum_v \xi_{uv} \right) \\ + \gamma \left( (\ell - 1) - \sum_v \ell_v + \sum_v \xi_{uv} \right). $$

For each $v$, let $A_\gamma(v) = \min_{t \ge 0}\{\sigma(v, t) - \gamma t\}$, and $B_\gamma(v) = \min_{t \ge 0}\{\Omega(v, t) - \gamma t\} + (\gamma + w_{uv})$. Then minimizing $\mathcal{L}(\xi, \ell; \lambda, \gamma)$ over $\ell_v$, we obtain the dual problem $\max_{\lambda \ge 0, \gamma \in \mathbb{R}} g(\lambda, \gamma)$ of (2.1) where

$$ g(\lambda, \gamma) = \inf_{\xi, \ell} \mathcal{L} = \lambda + \gamma(\ell - 1) + \sum_v \min\{A_\gamma(v), B_\gamma(v) - \lambda\} \\ = \gamma(\ell - 1) + \sum_v \min\{A_\gamma(v), B_\gamma(v)\} + \max_{\lambda \ge 0} \left[ \lambda + \sum_v \min\{0, \Delta_\gamma(v) - \lambda\} \right], $$
with $\Delta_{\gamma}(v) = B_{\gamma}(v) - A_{\gamma}(v)$. Maximizing $g(\lambda, \gamma)$ over $\lambda \ge 0$ gives us an
optimal solution for $\lambda$

$$
\lambda^* = \begin{cases} 0, & \text{if there exists } v \text{ with } B_{\gamma}(v) \le A_{\gamma}(v), \\ \min_{v \in C(u)} \Delta_{\gamma}(v), & \text{otherwise.} \end{cases}
$$

Then we get the optimal value of g(λ, γ) as follows

$$
\max_{\gamma \in \mathbb{R}} g(\lambda, \gamma) = \gamma(\ell - 1) + \sum_{v \in C(u)} \min\{A_{\gamma}(v), B_{\gamma}(v)\} + \min_{v \in C(u)} (B_{\gamma}(v) - \min\{A_{\gamma}(v), B_{\gamma}(v)\}).
$$

We then maximize $g(\lambda, \gamma)$ over $\gamma \in \mathbb{R}$. Note that the optimal value of this dual problem equals $\Phi(u)$. Thus, we have

$$
\begin{align*}
\Phi(u, \ell) &= \max_{\lambda \ge 0, \gamma \in \mathbb{R}} g(\lambda, \gamma) \\
&= \min_{S \subseteq C(u), S \ne \emptyset} \max_{\gamma \in \mathbb{R}} \left\{ \gamma(\ell - 1 + |S|) + \sum_{v \in S} \min_{t \ge 0} (\Omega(v, t) - \gamma t) + \sum_{x \in C(u) \setminus S} \min_{t \ge 0} (\sigma(x, t) - \gamma t) \right\} \\
&= \min_{\substack{S \subseteq C(u), S \ne \emptyset \\ \sum_{x \in C(u)} \ell_x = \ell - 1 + |S|}} \left[ \sum_{v \in S} (w_{uv} + \Omega(v, \ell_v)) + \sum_{x \in C(u) \setminus S} \sigma(x, \ell_x) \right].
\end{align*}
$$

* Leaf case $\Psi(u)$. The node $u$ must attach to exactly one child. Let $\eta_{uv} \in \{0, 1\}$ be the binary variable associated to the occurrence of edge $uv$ when $u$ is a leaf attached to $v$ subject to $\sum_{v \in C(u)} \eta_{uv} = 1$. For every $v \in C(u)$, we denote

$$
\Delta(v) = (1 - \alpha)w_{uv} + \min\{\Phi(v), \Omega(v)\} - A(v).
$$

Then $\Psi(u)$ can be obtained by solving the following optimization problem

$$
\min_{\eta \in \{0,1\}^{C(u)}} \sum_{x \in C(u)} A(x) + \sum_{v \in C(u)} \Delta(v) \eta_{uv} \quad \text{s.t.} \quad \sum_{v \in C(u)} \eta_{uv} = 1.
$$

Relax $\sum_v \eta_{uv} = 1$ with multiplier $\mu \in \mathbb{R}$. Let $\mathcal{L}(\eta, \mu)$ be the Lagrangian of problem $(\mathcal{W}(u))$, then

$$
\mathcal{L}(\eta, \mu) = \sum_{x \in C(u)} A(x) + \mu + \sum_{v \in C(u)} (\Delta(v) - \mu) \eta_{uv}.
$$

Note that for each v, we have

$$
\min_{\eta_{uv} \in \{0,1\}} (\Delta(v) - \mu) \eta_{uv} = \min\{0, \Delta(v) - \mu\}.
$$

Thus, the dual problem of $(\mathcal{W}(u))$ is

$$
\max h(\mu) = \sum_{x \in C(u)} A(x) + \mu + \sum_{v \in C(u)} \min\{0, \Delta(v) - \mu\}.
$$
The maximum of $h(\mu)$ is reached at $\mu^* = \min_v \Delta(v)$. Since the feasible set $\{\eta \in [0, 1]^{C(u)} : \sum_v \eta_{uv} = 1\}$ has integral extreme points, the optimal value of this dual problem equals $\Phi(u)$. Therefore, we have

$$ \begin{aligned} \Psi(u) = h(\mu^*) &= \sum_{x \in C(u)} A(x) + \min_{v \in C(u)} \Delta(v) \\ &= \sum_{x \in C(u)} A(x) + \min_{v \in C(u)} \left( (1 - \alpha)w_{uv} + \min\{\Phi(v), \Omega(v)\} - A(v) \right) \\ &= \min_{v \in C(u)} \left[ (1 - \alpha)w_{uv} + \min\{\Phi(v), \Omega(v)\} + \sum_{x \in C(u) \setminus \{v\}} A(x) \right]. \end{aligned} $$

* Isolated case $\Omega(u)$. The node $u$ forms a single-vertex star, hence

$$ \Omega(u) = \alpha + \sum_{v \in C(u)} A(v) = \alpha + \sum_{v \in C(u)} \min\{\Phi(v), \Psi(v), \Omega(v)\}. \quad \square $$

From the recurrence formulation in Lemma 2, we obtain a dynamic programming algorithm to solve each problem ($\mathcal{P}_k$). The overall complexity of solving the BSSFP on trees is given by the combination of Phase I and Phase II, as stated in the following theorem.

**Theorem 2.** The efficient solution set of BSSFP on trees can be determined in $O(n^3)$ time and $O(n^2)$ space.

*Proof.* To show the time and space complexity of our method for solving BSSFP on trees, we only need to consider the complexity of Phase II. We first show that the number of problems ($\mathcal{P}_k$) that have to be solved is equal to the number $|U|$ of non-supported efficient solutions. Considering two consecutive supported efficient solutions $(f_1^i, f_2^i)$, $(f_1^j, f_2^j)$ with $f_2^i < f_2^j$. We start with $k = f_2^j - 1$ and solve ($\mathcal{P}_k$). Note that the endpoints are consecutive supported solutions; there is no supported efficient solution $(f_1, f_2)$ with $f_2 \in (f_2^i, f_2^j)$. Hence, every executed call returns a rightmost non-supported efficient solution $(f_1^m, f_2^m)$ with $f_2^i < f_2^m \le k$. Record $(f_1^m, f_2^m)$ and split the interval into $(f_2^i, f_2^m)$ and $(f_2^m, f_2^j)$, on each subinterval apply the same rule. By induction on the number $|U_{ij}|$ of non-supported solutions inside $(f_2^i, f_2^j)$, the step case removes one point and recurses on the two subintervals, the number of ($\mathcal{P}_k$) solves on this interval is $|U_{ij}|$. Summing over all intervals, we get that the number of iterations for solving ($\mathcal{P}_k$) in phase II is $|U|$. Since each efficient solution corresponds to a distinct value of $f_2$ in $\{0, \dots, n\}$, it follows that $|U| < n$.

We now build a memoization table $\sigma(v, \ell)$ for every node $v \in V$ and every $\ell \in \{0, \dots, n\}$. All values are computed bottom-up on the rooted tree using the recurrences of Lemma 2. At each node, combining the contributions of the children requires distributing $\ell$ among their subtrees, which can be done in $O(\deg(v)n^2)$ time. Summing $\deg(v)$ over all nodes gives a total running time of $O(n^3)$, and the size of the table is $O(n^2)$. Once the table is available, each problem ($\mathcal{P}_k$) can be solved in constant time by reading the corresponding entry.
Since Phase II needs to evaluate exactly *U* such problems, the additional time is *O*(*U*). Therefore, the full efficient solution set is obtained in *O*(*n*³) time using *O*(*n*²) space. ☐

# 4 Conclusion

This work has introduced and studied the Bi-objective Spanning Star Forest Problem (BSSFP), where the two objectives are to minimize the number of centers and the total edge weight simultaneously. Our focus has been on the case where the input is a tree. To enumerate the efficient solution set for BSSFP, we presented a polynomial-time algorithm through a two-phase dynamic programming approach. The key idea is the use of a Lagrangian relaxation to justify sub-tree separability, which ensures that the recurrence relations are exact. Based on the results obtained for trees, it is natural to consider extending the algorithm in this paper to graphs that can be reduced to trees, such as cactus graphs. Another promising line of research is to investigate approximation algorithms for general graphs by comparing the solutions on a general graph with those obtained from its spanning trees.

# References

1. A. Agra, D. Cardoso, O. Cerdeira, and E. Rocha. A spanning star forest model for the diversity problem in the automobile industry. In: *ECCO XVIII, Minsk*, 2005.

2. M. Aïder, L. Aoudia, M. Baiou, A. R. Mahjoub, and V. H. Nguyen. On the star forest polytope for trees and cycles. *RAIRO-Operations Research*, 53, 2019.

3. A. Andersson. General Balanced Trees. *Journal of Algorithms*, 30(1):1–18, 1999.

4. S. Athanassopoulos, I. Caragiannis, C. Kaklamanis, and M. Kyropoulou. An improved approximation bound for spanning star forest and color saving. In: *Mathematical Foundations of Computer Science (MFCS)*, pp. 90–101, 2009.

5. O. Briant and D. Naddef. The Optimal Diversity Management Problem. *Operations Research*, 52(4):515–526, 2004.

6. C. Filippi and G. Stevanato. A two-phase method for bi-objective combinatorial optimization and its application to the TSP with profits. *4OR*, 11(3):253–276, 2013.

7. A. M. Geoffrion. Proper efficiency and the theory of vector maximization. *Journal of Mathematical Analysis and Applications*, 22(3):618–630, 1968.

8. O. Kariv and L. Hakimi. An algorithmic approach to network location problems. II: The *p*-medians. *Operations Research*, 37(3):539–560, 1979.

9. G. Mavrotas. Effective implementation of the epsilon-constraint method in multi-objective mathematical programming problems. *Applied Mathematics and Computation*, 213:455–465, 2009.

10. C. T. Nguyen, J. Shen, M. Hou, L. Sheng, W. Miller, and L. Zhang. Approximating the spanning star forest problem and its applications to genomic sequence alignment. *SIAM Journal on Computing*, pp. 946–962, 2008.

11. V. H. Nguyen. The maximum weight spanning star forest problem on cactus graphs. *Discrete Mathematics, Algorithms and Applications*, World Scientific Publishing, 2015.
12. O. Özpeynirci and M. Köksalan. An exact algorithm for finding extreme supported non-dominated points of multiobjective mixed integer problems. *Management Science*, 56(12):2302–2315, 2010.

13. E. L. Ulungu and J. Teghem. The two phases method: An efficient procedure to solve bi-objective combinatorial optimization problems. *Foundations of Computing and Decision Sciences*, 20:149–165, 1995.