A combinatorial algorithm for the ordered 1-median problem on cactus graphs

Abstract

Cactus graph is a graph in which any two simple cycles has at most one vertex in common. In this paper we address the ordered 1-median location problem on cactus graphs, a generalization of some popular location models such as 1-median, 1-center, and 1-centdian problems. For the case with non-decreasing multipliers, we show that there exists a cycle or an edge that contains an ordered 1-median. Based on this property, we develop a combinatorial algorithm that finds an ordered 1-median on a cactus in $O(n^2\log n)$ time, where n is the number of vertices in the underlying cactus.

1 Introduction

Location theory has recently become an important topic to the community because of its importance in practice. Here, the median and center functions are the most two popular objectives of a location problem. In a median location problem, we aim to find locations of new facilities that minimize the total weighted distances to the existing ones. Additionally, one aims to minimize the maximum weighted distances to new facilities in a center location problem. Interested readers can refer to Kariv and Hamkimi [12, 13] for results concerning the properties and solution approaches of the median and center location problems on networks. In brief, they proved these problems are, in general, NP-hard and thus solved them by exponential algorithms.

Special cases of location problem with polynomial algorithms are interesting. Among them, the problem of locating exactly one new facility attracts more interest. Hua [9] and Goldman [7] independently showed that the 1-median problem on trees is solvable in linear time based on the 1-median criterion. The 1-center location problem on trees was first solved in $O(n\log n)$ time by Kariv and Hakimi [13] and then it is improved to linear time by Megiddo [14]. For the unweighted tree, Handler [8] showed that the midpoint of the longest path of the tree is the 1-center and thus the 1-center can be found in linear time. Cactus graphs, a generalization of trees, are graphs in which any two cycles have at most one vertex in common. Concerning location problem on a cactus, Burkard and Krarup [3] solves the 1-median problem on cactus graph with pos/neg vertex weights in linear time. Ben-Moshe et al. [1] considered center location problems on cacti. They showed that the 1-center problem can be solved in $O(n\log n)$ time. The 1-centdian problem on catus graphs, where objective function is the sum of median and maxian functions, was also investigated by Ben-Moshe et al. [2].

For several facilities location problems, Tamir [17] proposed an $O(pn^2)$ algorithm for the p-median problem on trees. Then, Gavish and Sridhar [6] developed an improved $O(n\log n)$ algorithm for the 2-median problem on tree based on the link deletion method and the properties inherent in tree structure. Ben-Moshe et al. [1] also solved the 2-center problem on cacti in $O(nlog^3 n)$ time and further discussed solution approaches for p-center and obnoxious 1-center problems on cactus networks. Concerning the undesirable location problems, the p-maxian problem on trees was solved in linear time by Burkard et al. [4]. Moreover, the 2-maxian problem on cactus graphs can be further solved in quadratic time; see Kang et al. [11].

As there may be various points of view to a problem depending on an optimistic, deterministic, or pessimistic decision maker and that leads to the computation of corresponding objective functions. Hence, we required to investigate a general approach for a class of location problems. Recently, researchers coined the ordered median function, which is a generalization of a class of functions including median and center functions, and applied it to model the so-called ordered median location problem. One can see Nickel and Puerto [16] and references therein for solution approaches of the ordered median location problems.

In this paper we consider a generalization of the 1-median, 1-center, and 1-centdian problem on cacti, where the ordered median objective function is taken into account and the multipliers are nondecreasing. This unified problem is, according to the best of our knowledge, not under investigation so far although the related problems with classical objectives such as 1-median, 1-center and 1-centdian have already been solved. This paper is organized as follows. We introduce in Sect. 2 the fundamental concepts of ordered median function and the definition of the ordered 1-median problem on cactus graphs. We also investigate a special property, which allows us to localize the search for an ordered 1-median on the underlying cactus. Section 3 contributes to the algorithmic approach for the problem. It is shown that the problem is solvable in $O(n^2\log n)$ time, where n is the number of vertices on the cactus.

2 Preliminaries definitions and properties

We first revisit some denotations concerning the ordered 1-median location problem on a network. Let a connected graph $G := (V,E)$ without loops and multiple edges be given. The vertex set is abbreviated by $V := \{v_1,\ldots ,v_n\}$, where each vertex $v_i$ in V is associated with a nonnegative weight $w_i$. Furthermore, a nonnegative length $\ell _e$ is assigned to each edge e in the edge set E. The length of the shortest path P(u, v) of two vertices u and v is defined as the distance d(u, v) between them. Moreover, each edge of G is a continuous interval which contains points of the graph. In other words, if a point $\rho$ lies on an edge $e = (u,v)$, there exists a parameter $\theta \in [0,1]$ such that $d(u,\rho ) := \theta \ell _e$. One can observe that $\rho \equiv u$ if $\theta = 0$ and $\rho \equiv v$ if $\theta = 1$. Let A(G) denote by the set of points in the graph G. Similarly to the distance between two vertices, we can also determine the distance between two points in the graph.

We now take into account the ordered 1-median problem on G. For a vector $\lambda := (\lambda _1,\lambda _2,\ldots ,\lambda _n) \in {\mathbb {R}}^n_{+}$ of multipliers corresponding to the vertex set V, one can define the ordered 1-median function at $\rho \in A(G)$ as

$$\begin{aligned} f_{\lambda } (\rho ) := \displaystyle \sum _{i=1}^{n} \lambda _i w_{\sigma (i)} d(\rho ,v_{\sigma (i)}). \end{aligned}$$

The operator $\sigma (\cdot )$ is a permutation of $\{1,2,\ldots ,n\}$ such that the following monotonicity condition holds;

$$\begin{aligned} w_{\sigma (1)}d(\rho ,v_{\sigma (1)}) \le w_{\sigma (2)}d(\rho ,v_{\sigma (2)}) \le \cdots \le w_{\sigma (n)}d(\rho ,v_{\sigma (n)}). \end{aligned}$$

We further call such a permutation $\sigma (.)$ a feasible permutation with respect to the point $\rho$ and denote by $\varPi (\rho )$ the set of all feasible permutation w.r.t. $\rho$. A point $\rho ^{0}$ which minimizes the ordered 1-median function is, by definition, an ordered 1-median of G.

We next formally recall the definition of a cactus graph. In a connected graph, a cycle is a closed-chain subgraph that consists of at least three vertices and all of its vertices have degree 2. A cactus graph G is a connected graph, where two arbitrary cycles in G have at most one vertex in common. Especially, if there is no cycle in the underlying cactus, then it is indeed a tree graph. From here after, we always assume that G is a cactus graph and the multipliers are nondecreasing, i.e.,

$$\begin{aligned} \lambda _1\le \lambda _2 \le \cdots \le \lambda _n. \end{aligned}$$

(1)

By (1), the ordered 1-median problem is an extension of many popular location problems, say 1-median problem, 1-center problem, and 1-centdian problem with $\lambda = (1,1,\ldots , 1, 1)$, $\lambda = (0,0,\ldots ,0, 1)$, and $\lambda = (1,1,\ldots ,1, 2)$, respectively.

For a permutation $\tau$ which is not necessary to be a feasible one, we denote $f^{\tau }_{\lambda } (\rho ) := \sum _{i=1}^{n} \lambda _i w_{\tau (i)} d(\rho ,v_{\tau (i)})$. Let us call ${\mathcal {P}}$ the set of all permutations of $\{1,2,\ldots ,n\}$. It is obviously observed that $f_{\lambda } (\rho ) = \max _{\tau \in \mathcal P}f^{\tau }_{\lambda }(\rho )$ for $\rho \in A(G)$.

For the ordered 1-median problem on a tree with non-decreasing multipliers, Kalcsics et al. [10] proved that the objective function is convex along each simple path of the tree. They also used the directional derivative to eliminate a part of the tree and claimed that there exists an edge that contains an ordered 1-median. For the problem on cactus graphs, we aim to derive the similar result. However, the computation of directional derivative requires a complicated partition of the cactus. Hence, we next introduce a concept regarding derivative on cactus that is easy to be applied in this situation.

For a vertex v, we denote by ${\mathcal {G}}(v)$ the set of all subgraphs induced by deleting v and its incident edges from G. Note that these induced subgraphs are also cacti. For a subgraph $S \in {\mathcal {G}}(v)$, let B(S, v) be a subgraph in G induced by S and v.

Let $\sigma \in \varPi (v)$ such that for $v_i$ and $v_j$ with $w_id(v,v_i) = w_jd(v,v_j)$, the following property holds.

• If neither $v_i$ nor $v_j$ in B(S, v), with $w_i < w_j$, then $\sigma (i) > \sigma (j)$.

• If both $v_i$ and $v_j$ in B(S, v), with $w_i < w_j$, then $\sigma (i) < \sigma (j)$.

• If $v_i$ in B(S, v) and $v_j$ in $G \backslash B(S,v)$, then $\sigma (i) > \sigma (j)$.

Then we call $\sigma$ a feasible permutation corresponding to B(S, v). We introduce the formal derivative corresponding to B(S, v) as

$$\begin{aligned} f^{B(S,v)}_\lambda (v) := \displaystyle \sum _{v_{\sigma (i)} \in B(S,v)}\lambda _iw_{\sigma (i)} - \sum _{v_{\sigma (i)} \not \in B(S,v)}\lambda _iw_{\sigma (i)}. \end{aligned}$$

Example 1

Given a cactus graph G in Fig. 1. We consider $S :=\{v_1,v_2,v_3\} \in {\mathcal {G}}(v_4)$ and $B(S,v_4) := \{v_1,v_{2},v_3,v_4\}$. Let all edge lengths be equal 1 and $\lambda := (1,1,1,1,2,2,2,2,3,3,3,3)$. Then the weighted distances from vertices in G to $v_4$ are computed in Table 1. The formal derivative corresponding to $B(S,v_4)$ is

$$\begin{aligned} f^{B(S,v_4)}_\lambda (v_4) := \displaystyle \sum _{v_{\sigma (i)} \in B(S,v_4)}\lambda _iw_{\sigma (i)} - \sum _{v_{\sigma (i)} \not \in B(S,v_4)}\lambda _iw_{\sigma (i)}=-21 < 0. \end{aligned}$$

Fig. 1

A cactus graph G

Table 1 Weighted distances to vertex $v_4$

Implicitly, the formal derivative corresponding to B(S, v) can be considered as the derivative at v in the outside direction of B(S, v). If v is in a single edge, then the formal derivative is equivalent to the directional derivative at v. Observe that the formal derivative can be computed in $O(n\log n)$ time. Indeed, we have to sort all weighted distances to v nondecreasingly and break all ties with equal weighted distance to v. Then we apply the defined cases to resort these ties.

The following result allows us to eliminate a part of G that does not contain any ordered 1-median based on the formal derivative.

Proposition 1

Let a subcactusB(S, v) forSin${\mathcal {G}}(v)$be given such that$f^{B(S,v)}(v)\le 0$, then there exists an ordered 1-median in$(G \backslash B(S,v)) \cup \{v\}$.

Proof

Let $\sigma$ be a feasible permutation corresponding to B(S, v). Considering a point $\rho$ on B(S, v), one obtains

$$\begin{aligned} f^{\sigma }_{\lambda }(\rho )=&\sum _{i=1}^{n}\lambda _iw_{\sigma (i)}d(v_{\sigma (i)},\rho )\\ =&\sum _{v_{\sigma (i)}\notin \mathcal {B}(S,v)}\lambda _iw_{\sigma (i)}\left[ d(v_{\sigma (i)},v)+d(v,\rho )\right] +\sum _{v_{\sigma (i)}\in \mathcal {Q}}\lambda _iw_{\sigma (i)}\left[ d(v_{\sigma (i)},v)-d(v,\rho )\right] \\&+\sum _{v_{\sigma (i)}\in \overline{\mathcal {Q}}}\lambda _iw_{\sigma (i)}d(v_{\sigma (i)},\rho ). \end{aligned}$$

Here, $\mathcal {Q}$ is the set of vertices in B(S, v) whose shortest path to v containing $\rho$ and $\overline{\mathcal {Q}}:=B(S,v)\diagdown \mathcal {Q}$. We can rewrite

$$\begin{aligned} f^{\sigma }_{\lambda }(\rho )-f_{\lambda }(v)&=\left[ \sum _{v_{\sigma (i)}\notin B(S,v)}\lambda _iw_{\sigma (i)}-\sum _{v_{\sigma (i)}\in \mathcal {Q}}\lambda _iw_{\sigma (i)}\right] d(v,\rho )\\&\quad +\sum _{v_{\sigma (i)}\in \overline{\mathcal {Q}}}\lambda _iw_{\sigma (i)}\left[ d(v_{\sigma (i)},\rho )-d(v_{\sigma (i)},v)\right] \end{aligned}$$

Because of the triangle inequality and $f^{B(S,v)}(v)\le 0$, we trivitally get

$$\begin{aligned} f^{\sigma }_{\lambda }(\rho )-f_{\lambda }(v)&\ge \left[ \sum _{v_{\sigma (i)}\notin B(S,v)}\lambda _iw_{\sigma (i)}-\sum _{v_{\sigma (i)}\in \mathcal {Q}}\lambda _iw_{\sigma (i)}- \sum _{v_{\sigma (i)}\in \overline{\mathcal {Q}}}\lambda _iw_{\sigma (i)}\right] d(v,\rho )\\&\ge -f^{B(S,v)}(v)d(v,\rho ) \ge 0. \end{aligned}$$

Hence, $f_{\lambda }(\rho )=\max _{\sigma '\in \mathcal P}f^{\sigma '}_{\lambda }(\rho )\ge f_{\lambda }(v)$ for all $\rho \in B(S,v)$. The result follows. $\square$

By Proposition 1, we can eliminate a part, say B(S, v), from searching for an ordered 1-median of the cactus G. In Example 1, we can eliminate $B(S,v_4)$. For a cycle C in the cactus, if the formal derivative $f^{B(S,v)}(v) \ge 0$ for all $v \in C$ and $C \subset B(S,v)$, then C is called a candidate cycle.

Proposition 2

There exists at most two candidate cycle(s) in the underlying cactus.

Proof

If there is no ordered 1-median on a cycle of the cactus, then there is no candidate cycle. Otherwise, we consider an ordered 1-median which is contained in a cycle C, we can easily check that the C is a candidate cycle in G. As any two cycles have at most one vertex in common, there are at most two candidate cycles. $\square$

From the previous analysis, one can observe that an ordered 1-median is possibly contained in a cycle or an edge of the cactus; see Fig. 2.

Fig. 2

Eliminated parts of the cactus

3 Combinatorial algorithm for the ordered 1-median on cacti

In this section we aim to find an ordered 1-median of the cactus G by a combinatorial approach. The main idea can be described the two steps. In the first step we localize the search for an ordered 1-median based on the property given in Sect. 2. After completing the first step, in the second step we further apply the solution approach for the ordered 1-median problem on trees or decompose the cycles into intervals, in which the objective function is convex. An ordered 1-median of G can be found by comparing all minimizer of ordered 1-median function at the underlying intervals and taking the smallest one. Concerning the details, let us consider the following steps.

Step 1:Identify candidate cycle(s) onG.

We first compute the length of each cycle C in G, say $\ell (C) := \sum _{e\in C}\ell _e$. It is obviously done in linear time by summing up the corresponding edge lengths of each cycle. Furthermore, we orientate each cycle C such that its vertices are indexed in counter-clockwise direction. The distance from vertex u to vertex v in counter-clockwise direction is denoted by $d'(u,v)$. Note that the distance from u to v in C can be identified as $d(u,v) := \min \{d'(u,v),\ell (C) - d'(u,v)\}$.

Let us induce a tree based on the structure of the cactus G. For two vertices u and v, if there is a simple path connecting these two vertices such that its vertices are not in any cycle, possibly except u and v, then we contract this path into a single edge, say (u, v). Furthermore, we contract each cycle in G into a single vertex. After these contraction, we obtain an induced unweighted tree T(G). Note that each vertex in T(G) corresponds to a cycle in G. A centroid on T(G) is computed in linear time; see Kariv and Hakimi [12]. We call this centroid $c^*$.

Let us now turn back to the original cactus G. Let $C^*$ be a cycle containing $c^*$. For each vertex v in $C^*$, we compute the formal derivative $f^{B(S,v)}$ where $S \in {\mathcal {G}}(v)$ that does not contains $C^*$. We first root the cactus at $r \in C^*$ and compute the weighted distances from all other vertices to the root r in linear time by a breath-first-search algorithm. For detailed computation, readers can refer to Burkard and Krarup [3]. Also, we can derive the distance of any vertex a to $C^*$ by setting $d(a,C^*) := 0$ if $a \in C^*$ and $d(a,C^*) := d(a,v) - d(v,u)$ if u is the common vertex of P(a, r) and $C^*$. Applying the analysis in Sect. 2, we can compute the formal derivative at v in $O(n\log n)$ time. For a vertex $v'$ in $C^*$ which is adjacent to v, we can update the distances from any other vertices to $v'$ in linear time. Indeed, for an arbitrary vertex $v''$ in G, let u be a vertices in $C^*\cap P(v,v'')$. Then we set

$$\begin{aligned}&d(v'',v') := d(v'',u) + \min \{d'(u,v'),\ell (C^*) - d'(u,v')\} = d(v'',C^*) \\&\quad + \min \{d'(u,v'),\ell (C^*) - d'(u,v')\}. \end{aligned}$$

By the same argument, we can compute the directional derivatives at $v'$ in $O(n \log n)$ time. Hence, we can iteratively compute the formal derivative at each vertex in $C^*$ in $O(n^2\log n)$ time. If there exists a non-negative formal derivative, we turn to the adjacent vertex or cycle w.r.t the corresponding non-negative direction. Otherwise, the cycle is a candidate cycle.

After completing Step 1, we identify either a cycle or an edge that contains an ordered 1-median of G. If we find an edge, then the objective function is trivially convex in this edge. Hence, we can find an ordered 1-median in $O(n\log n)$ by the similar approach for finding ordered 1-median on trees; see [10]. On the other hand, if we find a candidate cycle $C^0$ that contains an ordered 1-median of G. We further search for the desired point on $C^0$ in the following step.

Step 2:Find an ordered 1-median ofGon the cycle$C^0$.

One of the simple way to find an ordered 1-median on $C^0$ is to find the set of equilibrium points on A(G), say

$$\begin{aligned} \text {EQ} := \bigcup _{u,v \in V, u\ne v} \{x\in A(G): w_ud(u,x) = w_vd(v,x)\}, \end{aligned}$$

and the set of mid-points in all cycles, say

$$\begin{aligned} \text {M} := \bigcup _{e = (u,v)\in E, v' \in V} \{x \in (u,v): d(x,v') = d(x,u)+d(x,v') = d(x,v)+d(x,v')\}. \end{aligned}$$

Then we search for an ordered 1-median on the dominating set $V\cup \text {EQ}\cup \text {M}$; see Kalcsics et al. [10]. As there are $O(n^2)$ many elements in $V\cup \text {EQ}\cup \text {M}$, the complexity of this procedure is $O(n^3\log n)$. We discuss another approach in this step such that we can avoid to deal with the points in $\text {EQ}\cup \text {M}$ as follows.

Let us first identify the midpoint $m_v$ with respect to v, say $d(v,m_v) = \frac{\ell (C^0)}{2}$, for all vertices v in $C^0$ in linear time. For an edge e in C, we induce a path $P^C(e)$ based on deleting an edge $e = (u,v)$. We recall that $m_u$ and $m_v$ are the two midpoints corresponding to u and v on the cycle C. We consider the path $P(m_u,m_v)$ on $P^C(e)$, where the two midpoints are auxiliary vertices. Assume that this path can be represented as $P(m_u,m_v) := (m_u, v'_1,v'_2,\ldots ,v'_l,m_v)$. For example, consider a cycle C in Fig. 3, the induced path $P(m_3,m_4)$ on $P^C(v_3,v_4)$ is represented as $(m_3,v_1,v_2,m_4)$.

Fig. 3

A cycle C and $P^C(v_3,v_4)$

Assume that after adding auxiliary vertices $m_u$ and $m_v$ with zero weights, for all edges (u, v) in G, we obtain a cycle $\bar{C}^0$. We reindex the vertices in $\bar{C}^0$ in counter-clockwise direction to get $v_1,v_2,\ldots ,v_q$. The the weighted distance function $w_v'd(v',x)$, with a fixed vertex $v'$, is a linear function for on $[v_i,v_{i+1}]$, $i = 1,\ldots ,q-1$. Therefore, we can find the minimizer of $f_\lambda (x)$ on a each interval in $O(n\log n)$ time by mastering a program which sort a set of n linear functions; see Megiddo [15], or Cole [5]. As there are at most 2n intervals induced by $P^C(e)$ for all e in C. We stop after $O(n^2\log n)$ time.

To summarize the computation in the two previous steps, we develop the following algorithm that solves the ordered 1-median problem on cactus networks in $O(n^2\log n)$ time. Algorithm 1 is efficient to compute an ordered 1-median on a cactus with many numbers of cycles. Indeed, we can eliminate most of the part of the cactus and remain to search for the desired point on at most two cycles. Let us finally state the main result of this paper.

Theorem 1

The ordered 1-median problem on cactus graphs can be solved in$O(n^2 \log n)$time.

4 Conclusions

We addressed the ordered 1-median problem on cactus graphs. It is shown that the problem is solvable in $O(n^2\log n)$ time, where n is the number of vertices. Efficient solution approach for the ordered p-median problem on cactus graphs is a promising topic.