Uncertain programming model for uncertain minimum weight vertex covering problem

Abstract

In this paper, the minimum weight vertex covering problem with uncertain vertex weights is investigated. By virtue of the uncertainty distribution operation of independent uncertain variables, the uncertainty distribution of the minimum weight of vertex cover is derived, and the concept of the $\alpha$-minimum cover among uncertain weight vertex covers is proposed within the framework of uncertain programming. Then an $\alpha$-minimum model for uncertain weight vertex covering problem is established and discussed. Taking advantage of some properties of uncertainty theory, the model can be transformed into the corresponding deterministic form. At last, a numerical example is presented to show the performance of the model.

Introduction

Minimum weight vertex covering problem (MWVCP) is a classic problem in graph theory. Given an undirected and vertex-weighted graph, the task of the MWVCP is to find a vertex cover with minimum weight, where the vertex cover is defined as a set of vertices such that all the edges in the graph are incident upon at least one vertex in the cover. The MWVCP plays a significant role in various applications, such as social network Ni et al. (2010), circuit design Shiue (2005), and so on.

The research of MWVCP dated back to Norman and Rabin (1959). In 1972, Karp (1972) proved that the MWVCP is a NP-hard problem, which means no polynomial time algorithm is expected to be designed to solve the problem. Since then, some approximate algorithms have been employed for the problem by researchers, such as Bar-Yehuda and Even (1981), Bouamama et al. (2012), Feige et al. (2008), Han et al. (2009), Oliveto et al. (2009), etc. In addition, several heuristic algorithms including evolutionary algorithm (Kratsch and Neumann 2013) and ant colony optimization algorithm (Shyu et al. 2004) have also been developed to solve the problem.

All of the above researchers focused on how to solve the MWVCP efficiently, and they only investigated it under the condition that the weights of vertices are determinate. However, the vertex weights are usually indeterminate in real world applications. Let us give an example here to illustrate it. The application of the MWVCP is often used to model the guard arrangement problem of museum. In order to protect the valuable famous painting, the museum always arrange some guard in each crossing such that all corridors are monitored and the total cost is minimized. For such a problem, a given exhibition hall can be represented by a graph, where each corridor is denoted by an edge and each crossing is denoted by a vertex. If the weight on each vertex is regarded as the cost of each crossing, then this problem is equivalent to the MWVCP. In fact, the number of guards depends on many indeterminacy factors such as the number of visitors and the period of their visiting.

From the above example, we can see that the meaning of studying MWVCP in indeterminacy environment is significant. Some researchers regarded that indeterminacy phenomena belonged to the stochastic phenomena, so they introduced probability theory into the MWVCP. In 2000, Weigt and Hartmann (2000) studied the MWVCP on finite connectivity random graphs. One year later, Hartmann and Weigt (2001) investigated the vertex covering problem for random graphs, and some exact numerical results were obtained by branch-and-bound algorithm. After that, Murat and Paschos (2002) discussed the complexity of optimally solving probabilistic vertex covering problem. In the year 2012, Ni (2012) introduced random variables to describe the vertex weights on the MWVCP and designed a hybrid intelligent algorithm that integrates stochastic simulation with genetic algorithm to solve the problem.

As we know, a premise to apply probability is that the estimated probability distribution is close enough to the real frequency. However, we are often lack of observed data about the events in our daily life, not only for economic reasons or technical difficulties, but also for influence of unexpected events. In this case, we have to invite some domain experts to give the belief degree that each event will occur. Nevertheless, human beings usually estimate a much wider range of values than the object actually takes (Kahneman and Tversky 1979), thus the belief degree deviates far from the real frequency. In this situation, if we insist on dealing with the belief degree by using probability theory, some counterintuitive consequences will appear (Liu 2012). In order to deal with the experts’ belief degree rationally, uncertainty theory was founded by Liu (2007) in 2007 and perfected by Liu (2009b) in 2009.

To our best knowledge, the investigation on the MWVCP in indeterminacy environment based on uncertainty theory is still blank before now. In this paper, we assume that the vertex weights are uncertain variables, and propose the concept of the $\alpha$-minimum cover among uncertain weight vertex covers. Then, we investigate the uncertainty distribution of the minimum weight of vertex cover. Fortunately, the uncertainty distribution of the minimum weight of vertex cover can be easily obtained under the framework of uncertainty theory. In addition, an $\alpha$-minimum model is proposed to solve the uncertain weight vertex covering problem. Taking advantage of some properties of uncertainty theory, the $\alpha$-minimum model can be transformed into the corresponding deterministic form.

The rest of the paper is organized as follows. Some basic concepts and results of uncertainty theory are introduced in “Preliminary” section. In “Problem description” section, we present the problem considered in this paper. The uncertainty distribution of the minimum weight of vertex cover is given in “Uncertainty distribution of ${f_{MW}}({{\varvec{\xi }}})$” section. In “$\alpha$-minimum model” section, the $\alpha$-minimum model for uncertain weight vertex covering problem is constructed and discussed. For the sake of illustrating the modeling idea, a numerical example is given in “Numerical experiment” section. A brief summary is presented in the last section.

Preliminary

Uncertainty theory is a new mathematical tool to study indeterminacy phenomena, especially subjective estimation or expert data. Up to now, uncertainty theory has been developed to a fairly complete system and has considerable achievements in both theoretical aspect and practical aspect.

From a theoretical point of view, the concept of uncertain differential equation was pioneered by Liu (2008) in 2008. After that, Yao (2013a) presented some formulas to calculate extreme value and time integral of solution of uncertain differential equation. Moreover, Yao (2013b) designed an analytic method to solve a type of nonlinear uncertain differential equation. Nowadays, uncertain differential equation has been widely applied in many fields such as uncertain finance (Liu 2013), uncertain differential game (Yang and Gao 2013), and uncertain optimal control (Sun et al. 2011; Zhu 2010). In addition, uncertain inference (Gao et al. 2010), uncertain logic (Kovac et al. 2013; Li and Liu 2009), and uncertain risk analysis (Liu 2010b) have been extensively studied in recent years.

In practical aspect, Liu (2009a) proposed a spectrum of uncertain programming which is a type of mathematical programming involving uncertain variables. Uncertain network was first explored by Liu (2010a) for modeling project scheduling problem in 2010. After that, Gao (2011) dealt with the shortest path problem, Han et al. (2014) investigated the maximum flow problem, and Zhang and Peng (2012) discussed the Chinese postman problem for an uncertain network. Recently, Peng et al. (2014) presented a state-of-the-art review on the recent advances in uncertain network optimization, and showed the general uncertain network optimization models based on uncertainty theory. To explore the recent developments of uncertainty theory, the interested readers may consult the book of Liu (2015).

In this section, we briefly state some foundational concepts and results about uncertainty theory, which are excerpted from Liu (2007), Liu (2009b), Liu (2010a) and will be used throughout the paper.

Let $\varGamma$ be a nonempty set, and $\mathcal{L}$ a $\sigma$-algebra over $\varGamma$. Each element $\varLambda \in \mathcal{L}$ is called an event. Liu (2007) presented an axiomatic uncertain measure $\mathcal {M}\{\varLambda \}$ to indicate the belief degree that uncertain event $\varLambda$ occurs. The set function $\mathcal {M}$: $\mathcal{L} \rightarrow [0,1]$ is required to satisfy the following axioms:

• (1) (Normality Axiom) $\mathcal {M}\{\varGamma \}=1$ for the universal set $\varGamma$.

• (2) (Duality Axiom) $\mathcal {M}\{\varLambda \}+\mathcal {M}\{\varLambda ^{c}\}=1$ for any event $\varLambda$.

• (3) (Subadditivity Axiom) For every countable sequence of events $\varLambda _{1}$,$\varLambda _{2}$,$\ldots ,$ we have

  $$\begin{aligned} \mathcal {M}\left\{ \bigcup _{i=1}^{\infty }\varLambda _{i}\right\} \le \sum _{i=1}^{\infty }\mathcal {M}\{\varLambda _{i}\}. \end{aligned}$$

For the sake of briefness, the triplet $(\varGamma ,\mathcal{L},\mathcal {M})$ is called an uncertainty space. In order to obtain an uncertain measure of compound event, the product uncertain measure was given by Liu (2009b) as the following product axiom.

• (4) (Product Axiom) Let $(\varGamma _{k},\mathcal{L}_{k},\mathcal {M}_{k})$ be uncertainty spaces for $k=1, 2, \ldots$ The product uncertain measure $\mathcal {M}$ is an uncertain measure satisfying

  $$\begin{aligned} \mathcal {M}\left\{ \prod _{k=1}^{\infty }\varLambda _{k}\right\} = \bigwedge _{k=1}^{\infty }\mathcal {M}_{k}\{\varLambda _{k}\} \end{aligned}$$

where $\varLambda _{k}$ are arbitrarily chosen events from $\mathcal{L}_{k}$ for $k=1, 2, \ldots$, respectively.

An uncertain variable is a function $\xi$ from an uncertainty space $(\varGamma ,\mathcal{L},\mathcal {M})$ to the set of real numbers such that $\{\xi \in B\}$ is an event for any Borel set $B$. In order to describe an uncertain variable analytically, Liu (2007) suggested the concept of uncertainty distribution as follows

$$\begin{aligned} \varPhi (x)=\mathcal {M}\left\{ \xi \le x\right\} ,\quad \!\! \forall x\in \mathfrak {R}. \end{aligned}$$

In 2010, Peng and Iwamura (2010) verified that a function $\varPhi (x)$ from $\mathfrak {R}$ to [0,1] is an uncertainty distribution if and only if it is a monotone increasing function except $\varPhi (x)=0$ and $\varPhi (x)=1.$

Liu (2010a) introduced the regular uncertainty distribution of an uncertain variable. An uncertainty distribution $\varPhi (x)$ is said to be regular if it is a continuous and strictly increasing function with respect to $x$ at which $0<\varPhi (x)<1$, and

$$\begin{aligned} \lim _{x\rightarrow -\infty }\varPhi (x)=0,\quad \lim _{x\rightarrow +\infty }\varPhi (x)=1. \end{aligned}$$

Based on the definition above, the inverse uncertainty distribution is defined by Liu (2010a) as follows. Assume that $\xi$ is an uncertain variable with regular uncertainty distribution $\varPhi$. Then the inverse function $\varPhi ^{-1}(\alpha )$ is called the inverse uncertainty distribution of $\xi$. Similar to the uncertainty distribution, the following sufficient and necessary condition of the inverse uncertainty distribution was proved by Liu (2013) in 2013. A function $\varPhi ^{-1}(\alpha ): (0,1)\rightarrow \mathfrak {R}$ is an inverse uncertainty distribution if and only if it is a continuous and strictly increasing function with respect to $\alpha$.

The uncertain variables $\xi _{1}, \xi _{2},\ldots , \xi _{n}$ are called independent (Liu 2009b) if

$$\begin{aligned} \mathcal {M}\left\{ \bigcap _{i=1}^{n}(\xi _{i}\in B_{i})\right\} = \bigwedge _{i=1}^{n}\mathcal {M}\{\xi _{i}\in B_{i}\} \end{aligned}$$

for any Borel sets $B_{1}$, $B_{2}$,$\ldots$, $B_{n}$.

Based on uncertain measure, Liu (2007) defined the expected value of uncertain variables as follows. Assume that $\xi$ is an uncertain variable. The expected value of $\xi$ is defined as the following form

$$\begin{aligned} E[\xi ]=\int _{0}^{+\infty }\mathcal {M}\{\xi \ge x\}\hbox {d}x-\int _{-\infty }^{0}\mathcal {M}\{\xi \le x\}\hbox {d}x \end{aligned}$$

provided that at least one of the two integrals is finite. If $\xi$ has an uncertainty distribution $\varPhi$, then the expected value of $\xi$ may be calculated by

$$\begin{aligned} E[\xi ]=\int _{0}^{+\infty }(1-\varPhi (x))\text{ d }x-\int _{-\infty }^{0}\varPhi (x)\text{ d }x. \end{aligned}$$

The variance of uncertain variable provides a degree of the spread of the distribution around its expected value. Let $\xi$ be an uncertain variable with finite expected value $e$. Then the variance (Liu 2007) of $\xi$ is

$$\begin{aligned} V[\xi ]=E[(\xi -e)^2]. \end{aligned}$$

For the sake of convenience, Liu (2007) introduced the concept of strictly increasing of multi-variable function in a manner. A real-valued function $f(x_{1}$, $x_{2}$, $\ldots$, $x_{n})$ is said to be strictly increasing if $f$ satisfies the following conditions:

• (1) $f(x_{1}, x_{2},\ldots , x_{n})\ge f(y_{1}, y_{2},\ldots , y_{n})$ whenever $x_{i}\ge y_{i}$ for $i=1,2,\ldots ,n;$

• (2) $f(x_{1}, x_{2},\ldots , x_{n})> f(y_{1}, y_{2},\ldots , y_{n})$ whenever $x_{i}> y_{i}$ for $i=1,2,\ldots ,n.$

Liu (2010a) introduced the following useful theorem to determine the inverse uncertainty distribution of the strictly increasing function of uncertain variables.

Theorem 1

(Liu 2010a) Let $\xi _{1}, \xi _{2}, \ldots , \xi _{n}$ be independent uncertain variables with regular uncertainty distributions $\varPhi _{1}, \varPhi _{2}, \ldots , \varPhi _{n}$, respectively. If $f$ is a strictly increasing function, then the uncertain variable

$$\begin{aligned} \xi =f(\xi _{1}, \xi _{2}, \ldots ,\xi _{n}) \end{aligned}$$

has an inverse uncertainty distribution

$$\begin{aligned} \varPsi ^{-1}(\alpha )=f(\varPhi ^{-1}_{1}(\alpha ),\varPhi ^{-1}_{2}(\alpha ),\ldots , \varPhi ^{-1}_{n}(\alpha )). \end{aligned}$$

Problem description

Given an undirected and simple graph $G=(V, E)$ with $n$ vertices, where $V=\{1, 2,\ldots , n\}$ represents the vertex set and $E=\{(i,j)\mid i\in V, j\in V,i<j\}$ denotes the edge set. Each vertex $i$ is associated with a weight $w_{i}$, and all the weights are presented by a vector ${\varvec{w}}=(w_{1}, w_{2},\ldots ,w_{n})$. A set of vertices $C\subset V$ is called a vertex cover if $i\in C$ or $j\in C$ for each edge $(i,j)\in E$. We define a binary decision variable $x_{i}$ for each vertex $i$ as follows:

$$\begin{aligned} x_{i}=\left\{ \begin{array}{cl} 1,&{}\text{ if } i\in C \\ 0,&{}\text{ otherwise, } \end{array}\right. \end{aligned}$$

which indicates whether the vertex $i$ is element of $C$ or not. It can be seen that the characteristic vector $\varvec{x}=(x_{1},x_{2},\ldots ,x_{n})$ corresponding to $C$ is a vertex cover if and only if

$$\begin{aligned} x_{i}+x_{j}\ge 1,\quad \quad \forall \quad \!\!\!\! (i,j)\in E. \end{aligned}$$

The class of all vertex covers of $G$ is denoted by $\fancyscript{C}$. Based on the above notations, the weight of a vertex cover $C$ is expressed by

$$\begin{aligned} W(C)=\displaystyle \sum _{i\in V }w_{i}x_{i},\quad C\in \fancyscript{C}. \end{aligned}$$

Then for a graph $G=(V,E)$, the minimum vertex cover weight is a function of the weight vector $\varvec{w}$, which is henceforward denoted by $f_{{MW}}$ in this paper. To be more clearly understood, the following definition is given.

Definition 1

Let $G=(V,E)$ be an undirected and simple graph. The minimum vertex cover weight $f_{{MW}}$ of the graph $G$ is a function of vertex weights, denoted by

$$\begin{aligned} f_{{MW}}(\varvec{w})=\min \{W(C)\mid C\in \fancyscript{C}\} \end{aligned}$$

and $f_{{MW}}(\varvec{w})$ is called the minimum weight function of the graph $G$.

Example 1

The graph $G=(V,E)$ is shown in Fig. 1. Assume that the vertex weights are crisp values $w_{i}, i= 1, 2, \ldots , 5,$ respectively. All the vertex covers are listed as follows

$$\begin{aligned} C_{1}&= \left\{ 1, 2, 5\right\} , C_{2}{=}\left\{ 1, 3, 4\right\} , C_{3}{=}\left\{ 2, 3, 4\right\} , C_{4}{=}\left\{ 2, 4, 5\right\} ,\\ C_{5}&= \left\{ 1, 2, 3, 4\right\} , C_{6}=\left\{ 1, 2, 3, 5\right\} , C_{7}=\left\{ 1, 3, 4, 5\right\} ,\\ C_{8}&= \left\{ 2, 3, 4, 5\right\} , C_{9}=\left\{ 1, 2, 4, 5\right\} , C_{10}=\left\{ 1, 2, 3, 4, 5\right\} . \end{aligned}$$

If we want to calculate the minimum vertex cover weight when the vertex weights are given, then we just need to compare the weights of the vertex covers $C_{1}, C_{2}, C_{3}, C_{4}.$

Fig. 1

Graph $G$ for Example 1

When $\varvec{w}=(w_{1},w_{2},w_{3},w_{4},w_{5})=(1, 2, 1, 2, 4)$, the weights of the vertex covers $C_{1}, C_{2}, C_{3}, C_{4}$ are 7, 4, 5, 8, respectively. Thus the vertex cover with the minimum weight is $\left\{ 1, 3, 4\right\}$, that is, $f_{{MW}}(\varvec{w})=4$.

If $\varvec{w}=(w_{1},w_{2},w_{3},w_{4},w_{5})=(1, 2, 3, 2, 2)$, then the weights of the vertex covers $C_{1}, C_{2}, C_{3}, C_{4}$ are 5, 6, 7, 6, respectively. Hence the vertex cover with the minimum weight is $\left\{ 1, 2, 5\right\}$, that is, $f_{{MW}}(\varvec{w})=5$.

In classic deterministic MWVCP, the weights of vertices are assumed to be crisp values. Unfortunately, such cases are rarely encountered in real-life decision making. If there are enough observed data, random MWVCP may be considered (see Ni 2012). However, in many cases, we are lack of observed data or observed data is invalid because of unexpected events have occurred. In these situations, some domain experts are invited to evaluate the belief degree of each vertex weight. As mentioned before, it is unsuitable to regard the subjective estimation weight data as random variables.

In this paper, the indeterminacy factor in graph $G=(V, E)$ is only considered on the weight of each vertex. We deal with this indeterminacy factor by using the uncertainty theory and assume that the weight of each vertex $i$ is a positive uncertain variable $\xi _{i}$, and all the uncertain variables $\xi _{i}$ are independent. Then all the uncertain weights are represented by a vector $\varvec{\xi }=(\xi _{1},\xi _{2},\ldots ,\xi _{n})$, and the minimum weight function is denoted by $f_{{MW}}(\varvec{\xi })$. Obviously, $f_{{MW}}(\varvec{\xi })$ is still an uncertain variable with respect to $\xi _{1},\xi _{2},\ldots ,\xi _{n}.$

Now, we give the concept of the $\alpha$-minimum cover among uncertain weight vertex covers, which is an optimal cover under some confidence level.

Definition 2

Let $G=(V,E)$ be an undirected and simple graph. The $C_{\alpha }$ is called the $\alpha$-minimum cover among uncertain weight vertex covers if

$$\begin{aligned}&{{\hbox {min}}}\left\{ \overline{W}\mid \mathcal {M}\left\{ W(C_{\alpha })\le \overline{W}\right\} \ge \alpha \right\} \\&\qquad \le {{\hbox {min}}}\left\{ \overline{W}\mid \mathcal {M}\left\{ W(C)\le \overline{W}\right\} \ge \alpha \right\} \end{aligned}$$

for any vertex cover $C$ of graph $G$, where $\alpha \in (0,1)$ is a predetermined confidence level.

As mentioned before, the minimum weight function $f_{{MW}}(\varvec{\xi })$ is an uncertain variable in a graph with uncertain vertex weights. Then, two problems are naturally produced. One is that what is the uncertainty distribution of $f_{{MW}}(\varvec{\xi })$? Another is that how can we get the $\alpha$-minimum cover among uncertain weight vertex covers? We will give the corresponding answers in “Uncertainty distribution of ${f_{MW}}({{\varvec{\xi }}})$” and “$\alpha$-minimum model”section, respectively.

Uncertainty distribution of ${f_{MW}}({{\varvec{\xi }}})$

Someone may ask whether there is a need to know the expression of the minimum weight function $f_{{MW}}(\varvec{\xi })$. In fact, it is not necessary. For the minimum weight function $f_{{MW}}(\varvec{\xi })$, we can get its inverse uncertainty distribution by means of the following theorem.

Theorem 2

Let $G=(V,E)$ be an undirected and simple graph with $n$ vertices. And we assume that vertex weights $\xi _{1}$, $\xi _{2}$, $\ldots$, $\xi _{n}$ are independent and positive uncertain variables with regular uncertainty distributions $\varPhi _{1}$, $\varPhi _{2}$, $\ldots$, $\varPhi _{n}$, respectively. Then the inverse uncertainty distribution of $f_{{MW}}(\varvec{\xi })$ is determined by

$$\begin{aligned} \varPsi ^{-1}(\alpha )=\displaystyle f_{{MW}}(\varPhi ^{-1}_{1}(\alpha ),\varPhi ^{-1}_{2}(\alpha ),\ldots ,\varPhi ^{-1}_{n}(\alpha )), \alpha \in (0,1). \end{aligned}$$

Proof

Assume that $f_{{MW}}(\varvec{\xi })$ is the minimum weight function of the graph $G$. It is clear that reducing the weight of each vertex leads to a smaller cover weight, i.e.,

$$\begin{aligned} f_{{MW}}(\varvec{w})<f_{{MW}}(\varvec{w^{'}}) \end{aligned}$$

whenever $\varvec{w}=(w_{1},w_{2},\ldots ,w_{n})$, $\varvec{w^{'}}=(w^{'}_{1},w^{'}_{2},\ldots ,w^{'}_{n})$ and $w_{i}< w^{'}_{i}$ for $i=1,2,\ldots ,n$; Moreover,

$$\begin{aligned} f_{{MW}}(\varvec{w})\le f_{{MW}}(\varvec{w^{'}}) \end{aligned}$$

whenever $\varvec{w}=(w_{1},w_{2},\ldots ,w_{n})$, $\varvec{w^{'}}=(w^{'}_{1},w^{'}_{2},\ldots ,w^{'}_{n})$ and $w_{i}\le w^{'}_{i}$ for $i=1,2,\ldots ,n$. Thus $f_{{MW}}$ is a strictly increasing function. Then we can easily obtain the inverse uncertainty distribution of $f_{{MW}}(\varvec{\xi })$ by Theorem 1. Thus the theorem is proved. $\square$

By using of Theorem 2, we can easily obtain the uncertainty distribution of $f_{{MW}}(\varvec{\xi })$ in a numerical sense. The following example illustrates this.

Example 2

We still use the graph $G=(V,E)$ shown in Fig. 1. Assume that

$$\begin{aligned} \xi _{1}=3,\quad \!\!\! \xi _{2}&= \mathcal{L}(1,2),\quad \!\!\! \xi _{3}=\mathcal{L}(2,3), \\ \xi _{4}&= \mathcal{Z}(2.5,3.5,4),\quad \xi _{5}=\mathcal{Z}(2,3,3.5). \end{aligned}$$

When $\alpha =0.9$, it is easy to get

$$\begin{aligned} \varPhi ^{-1}_{1}(0.9)&= 3,\quad \!\!\! \varPhi ^{-1}_{2}(0.9)=1.9,\\ \varPhi ^{-1}_{3}(0.9)&= 2.9,\quad \!\!\! \varPhi ^{-1}_{4}(0.9)=3.9,\quad \!\!\!\varPhi ^{-1}_{5}(0.9)=3.4 \end{aligned}$$

as shown in Fig. 2(a).

Fig. 2

Graph $G$ for Example 2

Then we obtain that

$$\begin{aligned}&\varPsi ^{-1}(0.9)\\&=f_{{MW}}(\varPhi ^{-1}_{1}(0.9),\varPhi ^{-1}_{2}(0.9),\\&\varPhi ^{-1}_{3}(0.9),\varPhi ^{-1}_{4}(0.9), \varPhi ^{-1}_{5}(0.9))\\&=f_{{MW}}(3,1.9,2.9,3.9,3.4). \end{aligned}$$

By comparing the weights of all the vertex covers shown in Example 1, we can see that the vertex cover with minimum weight is $\left\{ 1, 2, 5\right\}$, and the value of minimum weight function $f_{{MW}}(\varvec{\xi })$ is 8.3, i.e.,

$$\begin{aligned} \mathcal {M}\left\{ f_{{MW}}(\varvec{\xi })\le 8.3\right\} =\varPsi (8.3)=0.9. \end{aligned}$$

When $\alpha =0.2$, it is easy to get

$$\begin{aligned}&\varPhi ^{-1}_{1}(0.2)=3,\quad \varPhi ^{-1}_{2}(0.2)=1.2,\\&\varPhi ^{-1}_{3}(0.2)=2.2,\quad \varPhi ^{-1}_{4}(0.2)=2.9,\quad \varPhi ^{-1}_{5}(0.2)=2.4 \end{aligned}$$

as shown in Fig. 2(b).

Then we obtain that

$$\begin{aligned}&\varPsi ^{-1}(0.2)\\&=f_{{MW}}(\varPhi ^{-1}_{1}(0.2),\varPhi ^{-1}_{2}(0.2),\varPhi ^{-1}_{3}(0.2),\varPhi ^{-1}_{4}(0.2), \varPhi ^{-1}_{5}(0.2))\\&=f_{{MW}}(3,1.2,2.2,2.9,2.4). \end{aligned}$$

By comparing the weights of all the vertex covers shown in Example 1, we can see that the vertex cover with minimum weight is $\left\{ 2, 3, 4\right\}$, and the value of minimum weight function $f_{{MW}}(\varvec{\xi })$ is 6.3, i.e.,

$$\begin{aligned} \mathcal {M}\left\{ f_{{MW}}(\varvec{\xi })\le 6.3\right\} =\varPsi (6.3)=0.2. \end{aligned}$$

Generally, we can obtain the inverse uncertainty distribution $\varPsi ^{-1}(\alpha )$ for any $\alpha \in (0,1)$, and then get the uncertainty distribution $\varPsi$ equivalently.

$\alpha$-minimum Model

In “Problem description” section, the concept of the $\alpha$-minimum cover among uncertain weight vertex covers is proposed under the framework of uncertainty theory. In this section, we will construct an $\alpha$-minimum model for uncertain weight vertex covering problem. Taking advantage of some properties of uncertainty theory, the $\alpha$-minimum model can be transformed into the corresponding deterministic form.

Theorem 3

Let $G=(V,E)$ be an undirected and simple graph with $n$ vertices. And we assume that vertex weights $\xi _{1}$, $\xi _{2}$, $\ldots$, $\xi _{n}$ are independent and positive uncertain variables with regular uncertainty distributions $\varPhi _{1}$, $\varPhi _{2}$, $\ldots$, $\varPhi _{n}$, respectively. Then the $\alpha$-minimum cover among uncertain weight vertex covers of $G=(V,E)$ is just the minimum weight vertex cover of corresponding deterministic graph $\overline{G}=(\overline{V},\overline{E})$, where $\overline{V}=V$, $\overline{E}=E$, and the weight of each vertex $i\in \overline{V}$ is $\varPhi ^{-1}_{i}(\alpha )$.

Proof

According to Definition 2, the $\alpha$-minimum cover $C_{\alpha }$ is the optimal solution of the following uncertain programming model

$$\begin{aligned} \left\{ \begin{array}{ll} \displaystyle \min _{\varvec{x}}\quad \overline{W} \\ \hbox {subject to}:\\ \quad \qquad \!\mathcal {M}\left\{ \displaystyle \sum _{i\in V }\xi _{i}x_{i}\le \overline{W} \right\} \ge \alpha \\ \quad \qquad \! x_{i}+x_{j}\ge 1,\quad \!\! \forall \quad \!\!\!\! (i,j)\in E \\ \quad \qquad \! x_{i}\in \left\{ 0,1\right\} ,\quad \! \forall \quad \!\!\!\! i\in V. \end{array} \right. \end{aligned}$$

(1)

Since $\xi _{1}$, $\xi _{2}$, $\ldots$, $\xi _{n}$ are independent uncertain variables with regular uncertainty distributions $\varPhi _{1}$, $\varPhi _{2}$, $\ldots$, $\varPhi _{n}$, respectively. Then the model (1) can be equivalently transformed to the following deterministic model

$$\begin{aligned} \left\{ \begin{array}{ll} \displaystyle \min _{\varvec{x}}\quad \overline{W}\\ \hbox {subject to}:\\ \quad \qquad \!\displaystyle \sum _{i\in V }x_{i}\varPhi ^{-1}_{i}(\alpha )\le \overline{W}\\ \quad \qquad \!x_{i}+x_{j}\ge 1,\quad \!\! \forall \quad \!\!\!\! (i,j)\in E \\ \quad \qquad \!x_{i}\in \left\{ 0,1\right\} ,\quad \! \forall \quad \!\!\!\! i\in V. \end{array} \right. \end{aligned}$$

(2)

Clearly, model (2) is equivalent to

$$\begin{aligned} \left\{ \begin{array}{ll} \displaystyle \min _{\varvec{x}}\quad \displaystyle \sum _{i\in V }x_{i}\varPhi ^{-1}_{i}(\alpha )\\ \hbox {subject to}:\\ \quad \qquad \!x_{i}+x_{j}\ge 1, \quad \!\! \forall \quad \!\!\!\! (i,j)\in E \\ \quad \qquad \!x_{i}\in \left\{ 0,1\right\} , \quad \! \forall \quad \!\!\!\! i\in V. \end{array} \right. \end{aligned}$$

(3)

In fact, the solution of model (3) is just the minimum weight vertex cover of deterministic graph $\overline{G}=(\overline{V},\overline{E})$, where $\overline{V}=V$, $\overline{E}=E$, and the weight of each vertex $i\in \overline{V}$ is $\varPhi ^{-1}_{i}(\alpha )$. Hence the theorem is verified. $\square$

Remark 1

Some researchers employed the probability theory to study the MWVCP in indeterminacy environment, and they mainly used stochastic simulation and genetic algorithm to solve the problem (see Ni 2012). From the Theorem 3, we can translate the MWVCP in uncertain environment into the deterministic environment, which can be conveniently solved by optimization software packages, such as LINGO. This is also a reason why we deal with the MWVCP in indeterminacy environment by using uncertainty theory.

Numerical experiment

In order to illustrate the conclusions as presented above, we shall present the guard arrangement problem of museum as an example in this section. For the convenience of description, we summarize the problem as follows. Suppose that there are eight crossings and thirteen corridors in an exhibition hall, where an exhibition hall can be represented by a graph, and each crossing is denoted by a vertex and each corridor is denoted by an edge. Now, the task of the decision maker is to make the guard system such that all corridors are monitored and the total cost is minimized. At the beginning of this task, the decision maker needs to obtain the basic data, such as the number of visitor and the period of their visiting. However, due to economic reasons or technical difficulties, the decision maker cannot always get these data exactly. Under this condition, the usual way is to obtain the uncertain data by means of experience evaluation or expert advice.

Example 3

The exhibition hall is represented by a graph shown in Fig. 3. Assume that the costs of guard in each vertex $\xi _{i}$ are independent and positive uncertain variables, and the uncertainty distributions of them are listed in Table 1. The minimum total cost $f_{{MW}}$ with uncertainty distribution $\varPsi$. Our task is to find the following:

• (1) the $\alpha$-minimum cover with uncertain vertex weight when $\alpha$=0.9; And

  Fig. 3

  

  Graph $G$ for Example 3

• (2) the uncertainty distribution of $f_{{MW}}(\varvec{\xi }).$

Table 1 The distributions of $\xi _{i}$

When $\alpha$=0.9, we can calculate $\varPhi ^{-1}_{i}(0.9)$ for each $\xi _{i}$. The values are listed in Table 2.

Table 2 List of $\varPhi ^{-1}_{i}(0.9)$

Using the data in Table 2 and according to Theorem 3, we can construct a deterministic programming model

$$\begin{aligned} \left\{ \begin{array}{ll} \displaystyle \min _{\varvec{x}}\quad \displaystyle \sum _{i=1}^{8}x_{i}\varPhi ^{-1}_{i}(0.9)\\ \hbox {subject to}:\\ \quad \qquad \!x_{i}+x_{j}\ge 1,\quad \!\! i<j,\quad \!\! i,j=1,2,\ldots ,8\\ \quad \qquad \!x_{i}\in \left\{ 0,1\right\} ,\quad \! i=1,2,\ldots ,8. \\ \end{array} \right. \end{aligned}$$

(4)

By using of mathematical software (e.g., LINGO), the optimal solution of the model (4) can be obtained as ${\varvec{x}}^{*}=(1,0,1,0,1,1,1,0)^{T}$ and the minimum weight is 17. So $\varPsi (17)=\mathcal {M}\left\{ f_{{MW}}(\varvec{\xi })\le 17\right\} =0.9$. We denote the $0.9$-minimum cover among uncertain weight vertex covers as $\{1,3,5,6,7\}.$

By selecting different values of $\alpha$, we obtain the $\alpha$-minimum covers in Table 3. From Table 3, we find that $\alpha$ has an effect on the optimal solutions, and the weight of the minimum weight vertex cover increases while the confidence level is increasing.

Table 3 List of $\alpha$-minimum covers at different confidence levels

Conclusions

Indeterminacy factors often appear in the real world applications and uncertainty theory provides a new approach to deal with indeterminacy factors. In this paper, we have investigated the minimum weight vertex covering problem in uncertain environment. In order to construct uncertain programming model, the concept of $\alpha$-minimum cover among uncertain weight vertex covers is proposed. After that, the uncertainty distribution of the minimum weight of vertex cover is derived. Then an $\alpha$-minimum model for uncertain weight vertex covering problem is constructed. The $\alpha$-minimum model including uncertain vertex weights can be transformed into a corresponding deterministic form under the framework of uncertainty theory. At last, a numerical experiment is implemented to show the application of the model.

In comparison to the previous works, the main contributions of this paper can be summarized as the following two aspects: (1) As a new tool to deal with indeterminacy factors in the real world, uncertainty theory is introduced into the problem of minimum weight vertex covering. We have given the uncertainty distribution of the minimum weight of vertex cover, and have constructed an $\alpha$-minimum model for uncertain weight vertex covering problem. (2) Under a special case, the model can be turned into the deterministic form, and thus it can be handled within the framework of deterministic programming. In this way, we can find its solution by some classical methods.

It is worth saying that there are several other types of indeterminacy environments in the real systems. This paper investigates the minimum weight vertex covering problem in uncertain environment. The problem in other more complex environments may become new topics in our further research.