Parameterized Algorithms for Computing Pareto Sets

We first consider the multiobjective $s$-$t$ cut problem and its special case, the triangle aggregation problem [28]: Given some polygons $P$ and triangles $T$, the goal is to find all Pareto-optimal subsets $T^{\prime }\subseteq T$ minimizing both the total area and perimeter of $P\cup T^{\prime }$. This problem arises in cartography, where the goal is to compute a less detailed map from a given map. Here the polygons are building footprints and the space between these footprints is triangulated. By including triangles, one can glue together these building footprints, leading to a less detailed version of the map. We show that the multiobjective $s$-$t$ cut problem implies an algorithm to compute the Pareto set in time $𝒪(nw\cdot 2^w\cdot p_{\max }^2\log (p_{\max }))$ for this problem, where $w$ is the treewidth of the triangle adjacency graph.

In the full version of the paper, we show that this method for computing Pareto sets can also be applied for other multiobjective optimization problems, such as the multiobjective minimum spanning tree problem (MST) and the multiobjective traveling salesman problem (TSP). For both, we present algorithms with running time $𝒪(n{w}^{𝒪(w)}\cdot p_{\max }^2{\log }^{d-2}(w^{𝒪(w)}\cdot p_{\max }^2))$ where $w$ is the treewidth of the input graph, $n$ is the number of vertices in the graph, $p_{\max }$ is the size of the largest Pareto set computed in one of the subproblems of the dynamic program, and $d\ge 2$ is the (constant) number of different objectives. This shows that the Pareto set can be efficiently computed for graphs with small treewidth if the Pareto sets of the subproblems are not too large, which is often the case in realistic inputs.

Finally, we experimentally evaluate our algorithm on real-world datasets. We introduce new heuristic pruning techniques, runtime estimates for tree decompositions and their root, memory optimization, multi-threading, and other improvements for reducing runtime and memory usage.

Output-polynomial time algorithms (at least in the weak sense) are known for many problems. Examples include the multiobjective shortest path problem [12, 17, 29], multiobjective flow problems [15, 24], and the knapsack problem when viewed as a bicriteria optimization problem [25]. For the multiobjective spanning tree problem such algorithms are not known and there are only results on the set of extreme nondominated solutions. This is a subset of the Pareto set and it contains all solutions that optimize some linear combination of the different objectives. For the multiobjective spanning tree problem it is known that there are only polynomially many extreme nondominated solutions [14], and efficient algorithms for enumerating them exist [2].

Rottmann et al. [28] introduce the triangle aggregation problem under the objective of map simplification by grouping multiple building footprints together. They show that, similar to the multiobjective minimum spanning tree problem, there exist only a polynomial number of nondominated extreme solutions and they present an algorithm to compute this set in polynomial time. They also provide an extensive experimental study of their algorithms on real-world data sets showing that the model captures nicely the intention to aggregate building footprints to obtain less detailed maps. They put it as an open question whether or not it is possible to also compute the set of Pareto-optimal solutions in an output-efficient way.

Motivated by the observation that for many problems the Pareto set is often small in applications, the number of Pareto-optimal solutions has been studied in the probabilistic framework of smoothed analysis in a sequence of articles [27, 22, 10, 5]. It has been shown for a large class of linear integer optimization problems (which contains in particular the multiobjective MST problem and the multiobjective TSP) that the expected number of Pareto-optimal solutions is polynomially bounded if the coefficients (in our case, the edge weights) are independently perturbed by random noise. Formally, the coefficients of $d-1$ out of the $d$ objectives are assumed to be independent random variables with adversarially chosen distributions with bounded density. It is shown that not only the expected number of Pareto-optimal solutions is bounded polynomially in this setting but also all constant moments, so in particular the expected squared number of Pareto-optimal solutions is also polynomially bounded. Combined with this, our results imply that the Pareto set for the multiobjective MST problem, the multiobjective TSP and the multiobjective $s$-$t$ cut problem can be computed in expected FPT running time $𝒪(f(w)\cdot \text{poly}(n))$ in the model of smoothed analysis.

While dynamic programming over tree decompositions is a well-established technique, using it effectively in practice comes with more difficulties than simply minimizing the width of the decomposition. In experiments the runtime of an algorithm can vary largely for different tree decompositions with the same width.

Bodlaender and Fomin [8] introduced the concept of the $f$-cost of a tree decomposition, which sums up a cost function $f$ applied to the bag sizes across all nodes. This framework formalizes the observation that not all nodes contribute equally to runtime or memory, and that practical efficiency can benefit from structurally favorable decompositions.

The $f$-cost approach was later extended and evaluated experimentally by Abseher et al. [1] using machine learning to select a tree decomposition based on different features such as bag sizes, branching factors, and node depths. With their method they could often select a decomposition that performs well in practice. Kangas et al. [18] used the same model for the problem of counting linear extensions, confirming the value of such estimators, and suggesting the average join-node depth as a good single feature for estimating runtime.

Beyond selection heuristics, tree decompositions have also been studied with respect to memory efficiency. Charwat et al. [11] explored compressed representations of intermediate states using decision diagrams, and Betzler et al. [6] proposed anchor-based compression techniques to reduce hard drive memory usage.

In our case, we not only solve an optimization problem, but compute the entire set of Pareto-optimal solutions. This makes memory usage more sensitive to the structure of join operations and limits the applicability of pointer-based or diagram-compressed representations. To address this, we develop a custom estimation strategy for predicting both runtime and memory usage, based on predicting the number of Pareto-optimal solutions at each node and the runtime impact of join operations. We then select a decomposition based on a combination of both runtime and memory usage. Details of this procedure are provided in the full version of the paper.

Our algorithms rely on dynamic programming over a tree decomposition. The concept of tree decomposition and treewidth, introduced by Robertson and Seymour [26], provide a measure of how similar a graph is to a tree. Many $𝒩𝒫$-hard problems become tractable on graphs with small treewidth. Computing the optimal treewidth is $𝒩𝒫$-hard [3], but it is FPT with respect to the treewidth [7], and a tree decomposition of width at most $2\cdot w(G)$ can be computed in linear time using approximation algorithms [21]. Hence, we assume that our algorithm starts from such an approximate decomposition if no optimal one is available. In the following, we briefly introduce the notation used for tree decompositions.

The width of a tree decomposition is $w(𝒯):={\max }_{t\in V(𝕋)}|X_t|-1$, and the treewidth $w(G)$ is the smallest possible width of a tree decomposition. We denote with $V_t$ the union of vertices that were introduced at $t$ or some child of $t$. In the following, we write $w$ for the width of the tree decomposition used by our algorithm, which may be larger than $w(G)$ if an approximation is used.

We assume we have a nice tree decomposition, which is a binary tree decomposition rooted at some node $r\in V(𝕋)$ with $X_r=\mathrm{\varnothing }$ and with four specific node types:

• $\mathrm{■}$

  Leaf node: Let $t$ be a node with no child nodes. Then $t$ is a Leaf node iff $X_t=\mathrm{\varnothing }$.

• $\mathrm{■}$

  Introduce node: Let $t_{\text{parent}},t_{\text{child}}$ be two nodes in $V(𝕋)$, where $t_{\text{parent}}$ has exactly one child $t_{\text{child}}$. Then $t_{\text{parent}}$ is an Introduce node iff $X_{t_{\text{parent}}}=X_{t_{\text{child}}}\cup \{v\}$ for some $v\in V(G)$.

• $\mathrm{■}$

  Forget node: Let $t_{\text{parent}},t_{\text{child}}$ be two nodes in $V(𝕋)$, where $t_{\text{parent}}$ has exactly one child $t_{\text{child}}$. Then $t_{\text{parent}}$ is a Forget node iff $X_{t_{\text{parent}}}\cup \{v\}=X_{t_{\text{child}}}$ for some $v\in V(G)$.

• $\mathrm{■}$

  Join node: Let $t_{\text{parent}},t_{\text{child}}^1,t_{\text{child}}^2$ be three nodes in $V(𝕋)$, where $t_{\text{parent}}$ has exactly two children $t_{\text{child}}^1$ and $t_{\text{child}}^2$. Then $t_{\text{parent}}$ is a Join node iff $X_{t_{\text{parent}}}=X_{t_{\text{child}}^1}=X_{t_{\text{child}}^2}$.

From any tree decomposition of width $w$, a nice tree decomposition of the same width with $𝒪(|V(G)|\cdot w)$ nodes can be computed in polynomial time [13].

The algorithm works as follows: Given an instance $G=(V,E)$ and a cost function $c:E\to {ℝ}^d$, it first computes a nice tree decomposition $(𝕋,{\{X_t\}}_{t\in V(𝕋)})$. In each leaf node the Pareto sets are initialized as empty sets. Then, for each node $t$, depending on its type, the algorithm recursively computes the set of Pareto-optimal solutions for each subproblem at this node. We distinguish between the functions computeLeafNode, computeIntroduceNode, and computeForgetNode, corresponding to their respective node types, and show correctness assuming that the Pareto sets for all child nodes are correctly computed.

Initially, the implementation was unable to solve even small datasets, such as Osterloh (treewidth $14$), due to RAM exhaustion reaching up to 100GB. To solve this problem, we implemented an efficient outsourcing strategy that stores all currently unneeded solutions onto a hard drive, keeping only the necessary solutions in RAM. Each solution is stored as a 16-byte entry in a dedicated origin-pointer file. Each DP table $D[t,S]$ is stored in a separate surface-pointer file, containing solution IDs and their weights. These files are kept on disk and only loaded into RAM when needed. This data structure allowed solving Osterloh without exceeding RAM limits, but other datasets remained unsolvable due to hard drive usage growing up to 2TB. To free up disk space, we remove obsolete surface-pointer files and, when necessary, run a slow in-place pruning step to clean the origin-pointer file. This involves recursively marking only reachable entries by following their pointers and compacting the file accordingly. Pruning is only triggered when space is critically low, based on conservative estimates of future storage use. These strategies prevented further storage issues, but many datasets were still unsolvable due to excessive runtime, particularly in join nodes. For example, the runtime required to solve the Ahrem dataset at this stage was estimated at approximately 13,768 hours, or one and a half year worth of CPU.

When generating multiple tree decompositions for the same graph, we observed that both the decomposition structure and the choice of the root node can significantly affect performance. Similar to Abseher et al. [1], we therefore generate multiple tree decompositions for the same graph and select one that is expected to yield good performance. However, our approach differs in two important aspects: First, since we consider a concrete algorithm rather than a general class of dynamic programming approaches, we can simulate its execution to approximate actual performance. Second, we do not only estimate runtime but also account for memory consumption, selecting the decomposition that minimizes a weighted combination of both. To this end, each decomposition is traversed in postorder, and we estimate the number of solutions at each node to predict resource usage.

Earlier versions of our approach focused solely on minimizing runtime, which did not always lead to reduced memory usage (see Table 1). Only in the final version did we optimize both runtime and memory simultaneously. Incorporating this performance estimator into the algorithm led to a significant improvement in runtime. For the Ahrem dataset we estimated a runtime decrease to around 7,130 hours, a $48\%$ decrease in the estimated runtime.

In an experiment with 100 decompositions for the instance Osterloh, our estimator selected the decomposition that ranked first in both runtime and storage. The correlation between the predicted score and actual performance was $0.91$ for runtime and $0.97$ for storage. We obtained similarly strong results when estimating performance for different root node choices, again observing a high correlation between predicted and actual runtime and memory usage. These results suggest that our estimator reliably selects either the best tree decomposition or at least one that still performs well with regards to runtime and memory consumption.

Let $t$ be a join node with children $t_1$ and $t_2$. For each subset $S\subseteq X_t$, we compute ${𝒫}_t^S={𝒫}_{t_1}\oplus {𝒫}_{t_2}$ by combining all solutions $p_1\in {𝒫}_{t_1}^S$ with all solutions $p_2\in {𝒫}_{t_2}^S$ and subsequently remove all dominated solutions. To do this efficiently, we employ a lexicographical ordering of the input lists and process the combinations using a min-heap. Assume $|{𝒫}_{t_1}^S|\le |{𝒫}_{t_2}^S|$. We initialize a min-heap with one heap node for each $p_1\in {𝒫}_{t_1}^S$, each pointing to the first entry in ${𝒫}_{t_2}^S$. We then repeatedly extract the root of the min-heap, process the corresponding solution pair $(p_1,p_2)$, and increment its pointer to reference the next solution $p_2^{\prime }\in {𝒫}_{t_2}^S$ that follows $p_2$ in lexicographical order. If such a solution $p_2^{\prime }$ exists, we update the heap accordingly, otherwise, we remove the heap node from the data structure. This process continues until the heap is empty, ensuring that every valid solution pair has been considered. This min-heap mechanism ensures that all candidate pairs are enumerated in lexicographical order, which enables an efficient check for Pareto-optimality.

As with many dynamic programming algorithms over a nice tree decomposition, join nodes are the main computational bottleneck. At each join node $t$ we needed to compute $𝒫={𝒫}_1\oplus {𝒫}_2$ for two Pareto sets ${𝒫}_1,{𝒫}_2$ exactly $2^{|X_t|}$ many times. Computing ${𝒫}_1\oplus {𝒫}_2$ for $d\ge 2$ can be done in $𝒪(p_{\max }^2{\log }^{\max \{d-2,1\}}(p_{\max }^2))$. In the worst case, ${𝒫}_1\oplus {𝒫}_2$ can contain up to $|{𝒫}_1|\cdot |{𝒫}_2|$ many solutions if every combination is Pareto-optimal. By considering every combination $(p_1,p_2)\in {𝒫}_1\times {𝒫}_2$ and filtering out all dominated ones, this becomes very time-consuming. However, in practice we observed only a roughly linear growth in size relative to the larger input Pareto set. This discrepancy indicated that many combinations were computed that would ultimately be discarded. To circumvent this problem, we utilize a heuristic pruning strategy to efficiently exclude many non-Pareto-optimal combinations at the same time.

We construct a heuristic set $\mathscr{H}$ for $𝒫$ using a small subset of ${𝒫}_1$ and ${𝒫}_2$. Afterwards we partition ${𝒫}_1,{𝒫}_2$ and $\mathscr{H}$ into multiple sections and compute lower bounds for each section in ${𝒫}_1,{𝒫}_2$ and upper bounds for $\mathscr{H}$. We then iterate over all combinations of lower bounds and compare them with the upper bounds. If a combination of lower bounds is entirely dominated by all upper bounds, we can conclude that no solution in these sections will be Pareto-optimal (PO) in $𝒫$ and safely skip them in the min-heap. To construct $\mathscr{H}$, we apply the same optimization recursively until a base case is reached. Furthermore, we apply multi-threading for each join node $t$, enabling parallel computation of multiple entries $D[t,S]$ at the same time.

The heuristic pruning process introduces a trade-off between its own runtime and the efficiency gains from skipping combinations. By selecting appropriate parameters, we achieved a favorable balance, reducing the runtime by nearly $98\%$ and ultimately solving Ahrem in under seven days.

To further improve runtime and reduce memory usage, we analyzed recurring patterns in the algorithm process that allowed for optimization. In many instances, after computing a join node, many of these solutions were immediately discarded in subsequent forget nodes. To address this inefficiency, we introduce a new node type, called join-forget node, which merges a join node with subsequent forget nodes into a single operation. Formally, for a join node $t$ in the tree decomposition, if its unique parent and all ancestors up to the next non-forget node are forget nodes, we replace $t$ and all these forget nodes by a single join-forget node $t^{\prime }$. This new node retains the original bag $X_t$ and additionally stores the set $F$ of forgotten vertices from the removed forget nodes.

We consider which lists would be merged in the upcoming forget nodes of the original join node while combining solutions in the min-heap. More specifically, for a join-forget node with forgotten vertices $F$, we only create a min-heap for each subset $S^{\prime }\subseteq X_t\setminus F$. Each such heap allows us to efficiently iterate over all combinations from the union ${\bigcup }_{S\in \{S^{\prime }\cup F^{\prime }\mid F^{\prime }\subseteq F\}}\{p_1\cup p_2\mid p_1\in {𝒫}_{t_1}^S,p_2\in {𝒫}_{t_2}^S\}$.

This setup also enhances our join node heuristic. Instead of computing a heuristic set $\mathscr{H}$ and upper bounds for each pair ${𝒫}_{t_1}^S,{𝒫}_{t_2}^S$ separately, we reuse the join-forget structure. Specifically, for each subset $S^{\prime }\subseteq X_t\setminus F$, we compute the same heuristic set $\mathscr{H}$ for all $S\in \{S^{\prime }\cup F^{\prime }\mid F^{\prime }\subseteq F\}$. We do so by using subsets of ${𝒫}_{t_1}^S$ and ${𝒫}_{t_2}^S$ for all such $S$. As before, we recursively apply this heuristic until a small base case is reached. A side effect of this strategy is that it significantly increases RAM usage, as each thread now requires not just three lists in memory (namely ${𝒫}_{t_1}^S,{𝒫}_{t_2}^S$ and ${𝒫}_{t_1}^S\oplus {𝒫}_{t_2}^S$), but up to $2^{|F|+1}+1$ lists.

This strategy led to another significant boost in runtime for many of our datasets. For the Ahrem dataset, using join-forget nodes reduced the runtime by $95\%$, allowing us to solve the instance in almost $8$ hours. Moreover, storage usage also decreased by $59\%$. We emphasize that the improvements are not solely due to the use of join-forget nodes, but by adapting the tree decomposition performance estimator accordingly as well.

Together with the newly defined join-forget node, we searched for new patterns in the algorithm computations to reduce the storage consumption further. To this end, we introduce a second node type called introduce-join-forget node, which further generalizes the concept of join-forget nodes. After replacing applicable structures with join-forget nodes, we consider each join-forget node $t$ with child nodes $t_1,t_2$, where at least one child ($t_1$, $t_2$, or both) is an introduce node. We remove all consecutive introduce nodes among the children and store their introduced vertices as additional information in $t$.

A major inefficiency of standard introduce nodes arises from the exponential growth in possible subsets $S\subseteq X_t$. When a new vertex $v$ is introduced, each existing solution $p\in {𝒫}_t^S$ for $S\subseteq X_t\setminus \{v\}$ is, with a constant weight adjustment, duplicated for both $S$ and $S\cup \{v\}$. This significantly increases both memory usage and I/O overhead in the outsourcing step, making it a significant bottleneck. To resolve this, we avoid explicit duplication of solutions in introduce-join-forget nodes. Let $I\subseteq X_t$ be the set of vertices whose introduction was skipped on one side. If a set ${𝒫}^S$ is required for the min-heap computations and $S\cap I\ne \mathrm{\varnothing }$, we instead load the solutions of the surface-pointer file of ${𝒫}^{S\setminus I}$ and add the constant weight adjustments according to $S\cap I$. Additionally, we create an origin-pointer entry for such a solution only if they are identified as Pareto-optimal in the min-heap. This strategy also reduces the growth of the origin-pointer file.

Together with adapting the performance estimator, this final improvement reduced the memory consumption by an additional $92\%$, resulting in a total of only 122GB of storage required for the Ahrem dataset, while also achieving a further $15\%$ decrease in runtime, bringing the total runtime down to 7 hours.