A rough set method for the vertex cover problem in graph theory

Abstract

In this paper, we first establish a Multi-Relation Granular Computing model by a given graph, and point out that all the reducts of the constructed Multi-Relation Granular Computing model are exactly all the minimal vertex covers of the corresponding graph. Thus, the vertex cover problem in graph theory can be converted to the knowledge reduction problem in rough set theory. Based on the conversion, we then introduce methods for dealing with the knowledge reduction problem to solve the vertex cover problem. In particular, we introduce a kind of method called the heuristic reduction algorithm based on entropy.

Keywords

Graph vertex cover Granular Computing knowledge reduction entropy

1 Introduction

Rough set theory, proposed by Pawlak [18, 19], is a useful mathematical tool for dealing uncertain, inexact and fuzzy knowledge. It has been widely used in data analysis, data mining and artificial intelligence [2 , 33]. The original idea of rough set theory is based on the classification on the universe by an indiscernibility binary relation. Each object subset is approximated by a pair of definable sets called the lower and the upper approximations. The lower approximation is the greatest definable set contained in the given subset, while the upper approximation is the smallest definable set containing the given subset. Generally speaking, the upper approximation is larger than the lower approximation. If the lower approximation and the upper approximation of one object subset are just the same, then the subset is called a definable set; otherwise, called a rough set. Rough set-based data analysis starts from a data table called an information system. In an information system, there may be redundant knowledge and their removal can decrease the search space and improve some criteria. Thus, knowledge reduction problem(KRP) is essential in information systems analysis, which aims to compute a subset of relations (i.e., a reduct) while preserving or improving the classification ability of the total relations. Many approaches have been proposed for this issue, among those the one based on boolean logical operations can obtain all the reducts precisely[6].

In graph theory, there also exists an interesting and valuable topic called the vertex cover problem(VCP) [1 , 8], which has been widely used in reality life [23 , 37], e.g, the network measurement problem [31] and the site layout problem [23, 37]. The purpose of VCP is to select a minimum subset of vertices which can cover all the edges of a graph, i.e., each edge should be adjacent with some selected vertex. Similar to the situation of KRP, the boolean logical operations can also be employed to compute all the solutions or an optimal solution of the VCP. However, finding an optimal solution for a VCP has been proven to be an NP-hard problem. Therefore, many existing algorithms has been proposed to approximate the optimal solution from different viewpoints [1 , 7].

We can see that the theoretical foundation for dealing with both the KRP and VCP is the boolean logical operation. Inspired from this idea, this paper devotes to explore this connection and realizes the conversion between them. Our main works are given as follows. With respect to a given graph G = (V, E), we induce a Multi-Relation Granular Computing (GrC) model S_G = (U, A), where U and A are labeled as the object set and the relation set. The relation set A of the induced Multi-Relation GrC model is exactly the vertex set V of the graph G. We conclude that a vertex subset is a minimal vertex cover of the graph G if and only if it is a reduct of the induced Multi-Relation GrC model S_G. By the above method, we can convert the VCP to the KRP and use the existing efficient methods for the KRP to solve the VCP. For instance, the positive-region reduction method which keeps the positive region unchanged [29], the heuristic entropy reduction method in which the relations are selected one by one by a heuristic function [12], and the combination entropy reduction method in which the positive regions are combined with the entropy [22]. In this paper, we introduce the heuristic entropy reduction algorithm to deal with the VCP.

The rest of this paper is as follows. In Section 2, we give the frameworks of graph theory related with the VCP and rough set theory related with the KRP. In Section 3, we explore the connection between the VCP and the KRP through boolean logical operations. We construct a Multi-Relation GrC model induced by a graph whose all minimal vertex covers are exactly all the reducts of the induced Multi-Relation GrC model. In Section 4, we introduce a relatively efficient algorithm called heuristic algorithm based on entropy in rough set theory to compute a minimal vertex cover of a graph.

2 Preliminary knowledge in graph theory and rough set theory

In this section, we will review some basic concepts related to boolean logical operations, the vertex cover problem in graph theory, and the knowledge reduction problem in rough set theory.

2.1 Boolean logical operations

Boolean logical operations satisfy the following operation laws:

a ∨ a = a, a ∧ a = a;

a ∨ b = b ∨ a, a ∧ b = b ∧ a;

(a ∨ b) ∧ c = (a ∧ c) ∨ (b ∧ c), (a ∧ b) ∨ c

= (a ∨ c) ∧ (b ∨ c);

a ∧ (a ∨ b) = a, a ∨ (a ∧ b) = a.

A boolean expression that only contains conjunction (respectively, disjunction) operations is called a conjunction (respectively, disjunction) normal form. A conjunction (respectively, disjunction) normal form with the minimal number of variables in the boolean expression is called a minimal conjunction (respectively, disjunction) normal form.

2.2 The vertex cover problem in graph theory

In a graph G = (V, E), where V is the vertex set and E is the edge set of G, we say a vertex is one end of an edge if the vertex is adjacent with the edge. For two vertices u, v, if an edge e ∈ E is adjacent with u and v, u, v are called the ends of e, denoted as V (e) = {u, v}. A vertex covers an edge if the vertex is one end of the edge. A vertex subset is a vertex cover of a graph if the subset covers all the edges of the graph. A minimal vertex cover is a vertex cover such that any of its proper subsets is no longer a vertex cover. The vertex cover with the least vertex cardinal is the minimum vertex cover. Obviously, a minimum vertex cover is minimal, but not vice versa [3].

Let G = (V, E) be a graph. The boolean function of G is defined as follows: $F (G) = ⋀_{e \in E} {\lor V (e)},$ (1) where V (e) is the vertex set of the edge e ∈ E. The expression ∨V (e) is the disjunction of all the ends of edge e which means e can be covered by any of its ends. The expression ⋀_e∈E {∨ V (e)} is the conjunction of all end sets of the edges in G which means all the edges in G can be covered by a vertex set satisfying ⋀_e∈E {∨ V (e)}.

Theorem 1. [3] LetG = (V, E) be a graph,F (G) be the boolean function of G. A vertex subsetB ⊆ Eis a minimal vertex cover iff ∧Bis a conjunction normal form in the minimal disjunction normal form ofF (G).

Theorem 1 indicates that one can obtain all the minimal vertex covers of a given graph just by using boolean logical operations to convert the boolean function F (G) to a minimal disjunction normal form which contains some minimal conjunction normal forms as variables. Each minimal conjunction normal form is just a minimal vertex cover of G. The following example illustrates the operation process.

Example 1. Let G₁ = (V, E) be a graph as shown in Fig. 1, where E = {e₁, e₂, e₃} , V (e₁) = {v₁, v₂} , V (e₂) = {v₂, v₃} andV (e₃) = {v₂, v₄}.

The boolean function of G₁ is F (G₁) = (v₁ ∨ v₂) ∧ (v₂ ∨ v₃) ∧ (v₂ ∨ v₄) .

Using boolean logical operations to convert F (G₁) to a minimal disjunction normal form is given as follows:

F (G₁) = ((v₁ ∧ v₂) ∨ (v₁ ∧ v₃) ∨ v₂ ∨ (v₂ ∧ v₃))∧ (v₂ ∨ v₄) = (v₂ ∨ (v₁ ∧ v₃)) ∧ (v₂ ∨ v₄) = v₂ ∨ (v₂∧v₄) ∨ (v₁ ∧ v₂ ∧ v₃) ∨ (v₁ ∧ v₃ ∧ v₄) = v₂ ∨ (v₁ ∧ v₃ ∧ v₄).

By Theorem 1, we can obtain all the minimal vertex covers: {v₂} , {v₁, v₃, v₄}. The minimum vertex cover is {v₂}.

2.3 Knowledge reduction problem (KRP) in Multi-Relation Granular Computing models

Rough set theory is one of the most successful tools for handling uncertain information. Information on rough set theory is manifested in the form of information table, or information system. An information system contains data about objects of interest that are characterized by a finite set of attributes, and is usually represented by a triple S = (U, A, {V_a | a ∈ A}) [18, 19], where:

U is a nonempty finite set of objects called the domain set;

A is a nonempty finite set of attributes such that a : U → V_a for any a ∈ A, i.e., a (x) ∈ V_a, x ∈ U, where V_a is called the domain of attribute a.

An information system S = (U, A, {V_a | a ∈ A}) is usually written as S = (U, A) simplicity.

Each nonempty subset B ⊆ A in an information system (U, A) determines an indiscernibility relation as follows: $R_{B} = {(x, y) \in U \times U | a (x) = a (y), \forall a \in B} .$ Since R_B is an equivalence relation on U, it forms a partition U/R_B = {[x] _B | x ∈ U} , where [x] _B is the equivalence class determined by x with respect to B, i.e., [x] _B = {y ∈ U | (x, y) ∈ R_B} .

A partition U/R_B is also called a knowledge, and an information table can be seen as an defined equivalence relation cluster, i.e. knowledge base [28].

With the theoretical development and the widening application regions of rough set theory, relations in information systems have no longer limited to equivalence relations but more general situations [10 , 30]. From the viewpoint of granular computing, Lin and Yao studied a granular computing model under binary relations and proposed a framework for set approximation in the granular computing model [14– 17 , 35]. In the following, we present the notion of granular computing model.

Definition 1. [17, 32] Suppose U is the universe and A is a nonempty finite set of binary relations on U.

For a binary relation a ∈ A and an object x ∈ U, N_a (x) = {y ∈ U | (x, y) ∈ a} is called the neighborhood of x under a;

N_A (x) = ∩ _a∈AN_a (x) is called the neighborhood of x under A;

Pair (U, A) is called a Multi-Relation Granular Computing (GrC) model.

Attribute reduction also called knowledge reduction is one of the basic contents in rough set theory. In a Multi-Relation GrC model, there are always redundant binary relations and removing them has no influence on the representation of concepts. From this point of view, in the following, we introduce the notion of knowledge reduction in a Multi-Relation GrC model.

Definition 2. Let (U, A) be a Multi-Relation GrC model and B ⊆ A. If N_B (x) = N_A (x) for any x ∈ U, then B is called a consistent set of the Multi-Relation GrC model. If B is a consistent set and any of its proper subsets is no longer a consistent set, then B is called a reduct of the Multi-Relation GrC model. Let RED be the family of all reducts of the Multi-Relation GrC model, any a ∈ ∩ _C∈REDC is called a core of the Multi-Relation GrC model.

We can see that a reduct of a Multi-Relation GrC model is a minimal subset of relations which remains the original neighborhood of each object. In other words, a reduct keeps the neighborhood discernibility between each pair of objects. In the following, similar to information systems based on equivalence relation, we define the discernibility set of a pair of objects in Multi-Relation GrC models as same as the discernibility set in information systems.

Definition 3. Let (U, A) be a Multi-Relation GrC model with U = {x₁, . . . , x_n}. For any x_i, x_j ∈ U,

d (x_i, x_j) = {a ∈ A | x_j ∉ N_a (x_i)} is called the discernibility set of (x_i, x_j);

$D = (d (x_{i}, x_{j}) | 1 \leq i, j \leq n)$ is called the discernibility matrix of the Multi-Relation GrC model (U, A).

It should be noted that in a discernibility matrix, the discernibility relation between each pair of objects is determined explicitly. Therefore, a Multi-Relation GrC model and its discernibility matrix correspond one to one.

The reducts and consistent sets can be characterized by the discernibility matrix $D$ . In the following, a reduction method based on discernibility matrix is proposed to compute all the reducts of a Multi-Relation GrC model.

Theorem 2.Let (U, A) be a Multi-Relation GrC model withU = {x₁, . . . , x_n} and $D = (d (x_{i}, x_{j}) | 1 \leq i,$ j ≤ n) be the discernibility matrix. ThenB ⊆ Ais a consistent set of the Multi-Relation GrC model iff it satisfiesB∩ d (x_i, x_j) ≠ ∅ for anyd (x_i, x_j)≠ ∅.

Proof. ⇒ Suppose B is a consistent set. Then for any x_i ∈ U, it holds N_B (x_i) = N_A (x_i). That means for any x_j ∈ U, if x_j ∉ N_A (x_i), then x_j ∉ N_B (x_i). It equals to that if there is a ∈ A satisfying x_j ∉ N_a (x_i), then there exists a relation a′ ∈ B satisfying x_j ∉ N_a′ (x_i). With the fact of x_j ∉ N_a (x_i) and x_j ∉ N_a′ (x_i), we have that a, a′ ∈ d (x_i, x_j) and d (x_i, x_j)≠ ∅. Moreover, with the fact of a′ ∈ B, we have B∩ d (x_i, x_j) ≠ ∅.

⇐Suppose B∩ d (x_i, x_j) ≠ ∅ for any d (x_i, x_j)≠ ∅. Then a′ ∈ B satisfying x_j ∉ N_a′ (x_i), which follows x_j ∉ N_B (x_i). Moreover, d (x_i, x_j)≠ ∅ equals to x_j ∉ N_A (x_i). Thus, we have if x_j ∉ N_A (x_i), then x_j ∉ N_B (x_i). That means N_B (x_i) ⊆ N_A (x_i). On the other hand, since B ⊆ A, it is obvious that N_A (x_i) ⊆ N_B (x_i). Therefore, N_B (x_i) = N_A (x_i), which means B is a consistent set. This completes the proof.

Corollary 1.Let (U, A) be a Multi-Relation GrC model withU = {x₁, . . . , x_n} and $D = (d (x_{i}, x_{j}) | 1 \leq i,$ j ≤ n) be the discernibility matrix.B ⊆ Ais a reduct iff it is a minimum set satisfyingB∩ d (x_i, x_j) ≠ ∅ for anyd (x_i, x_j)≠ ∅.

Proof. From Theorem 2, it is obvious.

In information systems based on equivalence relation, an efficient theoretical reduction method is based on boolean logical operations. If d (x_i, x_j)≠ ∅, the partial pair (x_i, x_j) can be distinguished by any relation in d (x_i, x_j), thus through ∨d (x_i, x_j), x_i and x_j can be distinguished. The expression ∧ {∨ d (x_i, x_j)} is the conjunction of all ∨d (x_i, x_j) which implies that each partial pair (x_i, x_j) can be distinguished by it. These also apply to Multi-Relation GrC models. Thus, one can obtain all the reducts of a Multi-Relation GrC model by computing the discernibility function: $F (\bar{a_{1}}, . . ., \bar{a_{m}}) = \land {\lor (d (x_{i}, x_{j})) | d (x_{i}, x_{j}) \neq \emptyset},$ (2) where ∨ (d (x_i, x_j)) is a disjunction operation among the elements in d (x_i, x_j) and $\bar{a_{i}}$ is the corresponding boolean variable for each relation a_i ∈ A. In the following example, we employ the discernibility matrix and discernibility function to compute the reducts of a Multi-Relation GrC model.

Example 2. Let (U, A) be a Multi-Relation GrC model with U = {x₁, x₂, x₃, x₄}, A = {a₁, a₂, a₃} and the neighborhoods {N_{a
_i} (x_j) | x_j ∈ U, a_i ∈ A} of each object under each relation be presented in a square table as shown in Table 1.

Based on the neighborhoods of all objects in Table 1, the discernibility matrix of the Multi-Relation GrC model can be uniquely determined. In the first row of Table 1, we have x₁ ∈ N_{a
₁} (x₁) , N_{a
₂} (x₁) and N_{a
₃} (x₁), hence d₁₁ =∅. Moreover, x₂ ∈ N_{a
₁} (x₁), N_{a
₂} (x₁) and N_{a
₃} (x₁), so d₁₂ =∅; x₃ ∉ N_{a
₁} (x₁), thus d₁₃ = {a₁}; x₄ ∉ N_{a
₁} (x₁) and N_{a
₂} (x₁), so d₁₄ = {a₁, a₂}. Similarly, we can obtain the discernibility matrix of the Multi-Relation GrC model as shown in Table 2.

By Table 2, we can obtain the discernibility function: $\begin{matrix} F (\bar{a_{1}}, . . ., \bar{a_{5}}) & = & \land {\lor (d (x_{i}, x_{j})) | d (x_{i}, x_{j}) \neq \emptyset} \\ = & a_{1} \land (a_{1} \lor a_{2}) \land a_{2} \land (a_{2} \lor a_{3}) . \end{matrix}$

Using boolean logical operations, we can obtain: $F (\bar{a_{1}}, . . ., \bar{a_{5}}) = a_{1} \land a_{2} \land (a_{2} \lor a_{3}) = a_{1} \land a_{2} .$

Hence the Multi-Relation GrC model has only one reduct: {a₁, a₂}.

3 The induced Multi-Relation Granular Computing model by a graph

From the above discussion, we know that all the reducts of a Multi-Relation GrC model can be obtained by computing the discernibility function and all the minimal vertex covers of a given graph can also be obtained by computing the boolean function. Assume that if the noempty discernibility sets in a Multi-Relation GrC model are exactly all the end sets of the edges in a graph, then, by using boolean logical operations, the discernibility function of the Multi-Relation GrC model and the boolean function of the graph can obtain the same result. i.e., all the reducts of the Multi-Relation GrC model are just all the minimal vertex covers of the graph. Base on it, in this section, we first induce a Multi-Relation GrC model by a graph whose all end sets of edges are exactly all the nonempty discernibility sets of the induced Multi-Relation GrC model and give an example to illustrate it. We then discuss the relationship between them.

In the following, we construct a Multi-Relation GrC model for a given graph.

Given a graph G = (V, E) with V = {a₁, a₂, . . . , a_m} and E = {e₁, e₂, . . . , e_k}. For unifying symbols, here we use a_i, 1 ≤ i ≤ m instead of v_i to represent the vertices, and for convenience, we use e ∈ E to represent its end set V (e) in the following. The induced Multi-Relation GrC model of the graph G can be constructed by the following steps:

Label an object set U = {x₁, x₂, . . . , x_|U|};

Label a relation set A = V = {a₁, a₂, . . . , a_m};

Construct a discernibility matrix $D = (d (x_{i}, x_{j}) | i, j < | U |)$

where d (x_i, x_j) is denoted as the discernibility set of the pair (x_i, x_j) as shown in Table 3.

(4) We obtain a Multi-Relation GrC model S_G = (U, A) induced by the given graph G, where U is the arbitrarily labeled object set, A is the relations set which is just the vertex set V, and d (x_i, x_j) is the discernibility set of the objects pair (x_i, x_j) ∈ U × U.

i.e. d (x_i, x_j) = ${\begin{matrix} e_{(i - 1) \times | U | + j - i + 1}, & (i - 1) \times | U | + j - i \leq k \\ and 1 \leq j < i; \\ \emptyset, & (i - 1) \times | U | + j - i \leq k \\ and j = i; \\ e_{(i - 1) \times | U | + j - i}, & (i - 1) \times | U | + j - i \leq k \\ and i < j \leq | U |; \\ \emptyset, & (i - 1) \times | U | + j - i > k . \end{matrix}$

For the above construction, we have several illustrations as follows:

(a) In the above construction, Step (3) regards all e_t (1 ≤ t ≤ k) as the nonempty discernibility sets of the object pairs. This is a key step which can determine the neighborhood of each object. ∅ is assigned to the diagonal entries d (x_i, x_i) (1 ≤ i ≤ |U|) of the discernibility matrix and e₁, . . . , e_k are assigned to the undiagonal entries d (x_i, x_j) (i ≠ j) one by one until the last element e_k is assigned. Then ∅ is associated to the rest elements in $D$ .

(b) Each pair of objects is associated with one discernibility set, thus |U| objects need at least |U| × (|U|-1) discernibility sets. |U| needs to satisfy |U| × (|U|-1) ≥ k, which is equal to that $| U | \geq \frac{1 + \sqrt{1 + 4 k}}{2}$ . Here we take $| U | = \frac{1 + \sqrt{1 + 4 k}}{2}$ when 1 + 4k is complete square like 9,25,81,121,169,..., and otherwise $| U | = [\frac{1 + \sqrt{1 + 4 k}}{2}] + 1$ .

(c) From the above discussion, a Multi-Relation GrC model can be uniquely determined by a given discernibility matrix. Thus, from step (3), we can obtain the induced Multi-Relation GrC model (U, A) in which the neighborhood of each object under each relation is N_{a
_i} (x_j) = {x_t ∈ U | a_i ∉ d (x_j, x_t)}, 1 ≤ i ≤ m, 1 ≤ j ≤ |U|,1 ≤ t ≤ |U|.

In the following example, we illustrate how to construct the induced Multi-Relation GrC model of a given graph.

Example 3. Given a graph G₂ = (V, E) with V = {a₁, a₂, a₃, a₄, a₅, a₆} and E = {e₁ = {a₁, a₂} , e₂ = {a₂, a₃} , e₃ = {a₂, a₄} , e₄ = {a₄, a₅} , e₅ = {a₅, a₆}} as shown in Fig. 2. The construction of the induced Multi-Relation GrC model S_{G
₂} = (U, A) is described as follows:

(1) Since k = |E|=5, $| U | = [\frac{1 + \sqrt{1 + 4 k}}{2}] + 1 = [\frac{1 + \sqrt{1 + 4 \times 5}}{2}] + 1 = 3$ , thus label an object set U = {x₁, x₂, x₃};

(2) Label a relation set A = V = {a₁, a₂, a₃, a₄, a₅, a₆};

(3) Construct the discernibility matrix $D$ : ∅ is assigned to d (x₁, x₁), d (x₂, x₂) and d (x₃, x₃); e₁ is assigned to d (x₁, x₂); e₂ is assigned to (x₁, x₃); e₃ is assigned to d (x₂, x₁); e₄ is assigned to d (x₂, x₃) and e₅ is assigned to d (x₃, x₁). Because e₅ is the last one, ∅ is assigned to d (x₃, x₂). Consequently, we can obtain the discernibility matrix D as shown in Table 4.

(4) Because a Multi-Relation GrC model can be uniquely determined by a discernibility matrix, we now obtained the induced Multi-Relation GrC model S_{G
₂} = (U, A) where U = {x₁, x₂, x₃}, A = {a₁, a₂, a₃, a₄, a₅, a₆} and the discernibility matrix $D$ is as shown in Table 4.

By Table 4, we can obtain the discernibility function:

$F (\bar{a_{1}}, . . ., \bar{a_{6}}) = (a_{1} \lor a_{2}) \land (a_{2} \lor a_{3}) \land (a_{2} \lor a_{4}) \land (a_{4} \lor a_{5}) \land (a_{5} \lor a_{6})$

Using boolean logical operations to compute the reducts, we can obtain:

$F (\bar{a_{1}}, . . ., \bar{a_{6}}) = (a_{1} \land a_{3} \land a_{4} \land a_{5}) \lor (a_{2} \land a_{5}) \lor (a_{1} \land a_{3} \land a_{4} \land a_{6}) \lor (a_{2} \land a_{4} \land a_{6})$ .

Hence, {a₁, a₃, a₄, a₅}, {a₂, a₅}, {a₁, a₃, a₄, a₆} and {a₂, a₄, a₆} are four reducts of the induced Multi-Relation GrC model (U, A) and {a₂, a₅} is the unique minimum reduct.

The relationship between the graph G = (V, E) and its induced Multi-Relation GrC model S_G = (U, A) is described as follows.

Theorem 3. A vertex subset of a graph is a minimal vertex cover if and only if it is a reduct of the induced Multi-Relation GrC model by the graph.

Proof. For a given graph G = (V, E), by the above construction, all the discernibility sets of the induced Multi-Relation GrC model are exactly all the end sets of the edges of the graph G, it follows that the boolean function of the graph G in the equation (1) and the discernibility function of the induced Multi-Relation GrC model in the equation (2) are just the same. And through boolean operations, they can obtain the same results. Thus, we can easily to conclude that all the reducts of the induced Multi-Relation GrC model are exactly the minimal vertex covers of the graph G.

Corollary 2. A vertex subset of a graph is a minimum vertex cover if and only if it is a minimum reduct of the induced Multi-Relation GrC model by the graph.

Proof. It is straghtforward by Theorem 3.

Theorem 3 implies that the SCP in graph theory and the KRP in rough set theory can be converted to each other.

Thus, in Example 3, we can conclude that {a₁, a₃, a₄, a₅}, {a₂, a₅}, {a₁, a₃, a₄, a₆} and {a₂, a₄, a₆} are four minimal vertex covers and {a₂, a₅} is the unique minimum vertex cover of the graph G₂.

4 A heuristic minimum vertex cover algorithm based on entropy for the VCP

In this paper, based on the conversion, we aim to use the existing methods for dealing with the KRP in rough set theory to deal with the VCP in graph theory. Such as the discernibility matrix based reduction method, the positive-region based reduction method, the information entropy based heuristic reduction method which can gradually reduce the time required by eliminating either unlikely possibilities or irrelevant states, or by selecting the required relations gradually [10 , 20]. Entropy was firstly introduced into reduction method by Skowron [24], then Slezak used it to deal with the reduction problem in information system and Wang et al. introduced the conditional entropy into decision system [30], Liang et al. defined a kind of entropy and applied it to compute a reduct [12], Qian et al. developed a common accelerator into entropy reduction with which the data needed computing is gradually reduced in the process of the algorithm [22]. To measure the uncertainty of knowledge in Multi-Relation GrC model, Hu et al. proposed a kind of neighborhood entropy [9] as follows.

Definition 4. Let (U, A) be a Multi-Relation GrC mode with U = {x₁, x₂, . . . , x_n}. For any subset B ⊆ A, the neighborhood entropy of B is defined as: $NH (B) = - \frac{1}{n} \sum_{i = 1}^{i = n} \log \frac{| N_{B} (x_{i}) |}{n},$ where N_B (x_i) is the neighborhood of x_i under the relation set B and | • | denotes the cardinality of a set.

The basic effect of the entropy is to compare two classes of knowledge and to measure the uncertainty degree of one class of knowledge with respect to another.

Definition 5. [9] Let (U, A) be a Multi-Relation GrC model with U = {x₁, x₂, . . . , x_n}. B, C ⊆ A, the condition neighborhood entropy of B to C is defined as: $NH (B | C) = - \frac{1}{n} \sum_{i = 1}^{i = n} \log \frac{| N_{B \cup C} (x_{i}) |}{| N_{C} (x_{i}) |},$ where N_B∪C (x_i) is the neighborhood of x_i under the relation set B ∪ C.

In a Multi-Relation GrC model, we have the following descriptions for the relations.

Definition 6. Let (U, A) be a Multi-Relation GrC model and RED be the family of all reducts. For a relation a ∈ A, according to the importance of relations for constructing a reduct, the relation a is broadly classified into three parts:

a is a core iff for any reduct R ∈ RED, a ∈ R, i.e. a ∈ ∩ RED;

a is unnecessary iff for any reduct R ∈ RED, a ∉ R, i.e. a ∈ (A - ∪ RED);

a is relative necessary iff a belongs only part of the reducts, i.e. a ∈ (∪ RED - ∩ RED).

For a relation a ∈ B ⊆ A, we say a is dispensable in B iff for any x ∈ U, N_B-{a} (x) = N_B (x); Otherwise, a is indispensable.

Theorem 4.LetS = (U, A) be a Multi-Relation GrC model,a ∈ A,

a is a core iff a is indispensable in A,

a is unnecessary iff a is dispensable in B for all consistent sets B that contains a,

a is relative necessary iff a is dispensable in A, and there exists a consistent set B which contains a such that a is indispensable in B.

Proof. (1) ⇒ Assume, by contradiction, that a is a core, but a is dispensable in A, then N_A-{a} (x) = N_A (x). Hence A - {a} is a consistent set, it follows that there exists a reduct B ⊆ A - {a} and a ∉ B which implies a is not a core.

⇐ If a is not a core, we have that there exists a reduct B satisfying a ∉ B. Thus B ⊂ A - {a} ⊂ A and N_A (x) ⊆ N_A-{a} (x) ⊆ N_B (x) for all x ∈ U. Note that N_B (x) = N_A (x), therefore N_A-{a} (x) = N_A (x), a is dispensable in A, and this is a contradiction with.

(2) ⇒ In fact for any consistent set a ∈ B, there exists a reduct C ⊆ B and if a is unnecessary, it follows a ∉ C, then C ⊂ B - {a} ⊂ B. Since N_C (x) = N_B (x) = N_A (x) for any x ∈ U, it follows that N_A (x) = N_B (x) ⊆ N_B-{a} (x) ⊆ N_C (x) = N_A (x), thus N_B-{a} (x) = N_B (x). So a is dispensable in B.

⇐ For any reduct C, we can see that B = C ∪ {a} is a consistent set. If a is dispensable in B, then N_B-{a} (x) = N_B (x) = N_A (x), that is N_C-{a} (x) = N_B (x) = N_A (x) for any x ∈ U. Therefore C - {a} is consistent, moreover C is a reduct, thus C - {a} = C, that is a ∉ C, so a is unnecessary.

(3) We may conclude it from (1) and (2).

The followings characterize the relations from the view point of neighborhood entropy.

Lemma 1.LetS = (U, A) be a Multi-Relation GrC model.B ⊆ A, NH (A | B) =0 ⇔ N_B (x) = N_A (x) for all x ∈ U.

Proof. In the Multi-Relation GrC model S = (U, A) referred in this paper, we always have x ∈ N_a (x) for all x ∈ U, a ∈ A, thus |N_a (x) |≠0.

⇒ By Definition 6,

$NH (A | B) = - \frac{1}{n} Σ_{x \in U} \log \frac{| N_{B} (x) \cap N_{A} (x) |}{| N_{B} (x) |}$ . Since $- \log \frac{| N_{B} (x) \cap N_{A} (x) |}{| N_{B} (x) |} \geq 0$ , if NH (A | B) =0, then $- \log \frac{| N_{B} (x) \cap N_{A} (x) |}{| N_{B} (x) |} = 0$ for all x ∈ U, it follows $\frac{| N_{B} (x) \cap N_{A} (x) |}{| N_{B} (x) |} = 1$ , besides N_B (x) ⊇ N_A (x), so N_B (x) = N_A (x) for any x ∈ U.

⇐ If N_B (x) = N_A (x) for all x ∈ U, then $\frac{| N_{B} (x) \cap N_{A} (x) |}{| N_{B} (x) |} = 1$ . By Definition 6, NH (A | B) =0.

Theorem 5.LetS = (U, A) be a Multi-Relation GrC model. For anyB ⊆ A,

B is a consistent set iff NH (A | B) =0;

B is a reduct iff NH (A | B) =0 and NH (A | (B - {a})) ≠0 for all a ∈ B.

Proof. (1) From Lemma 1, it is concluded.

(2) It holds from (1).

Theorem 6.LetS = (U, A) be a Multi-Relation GrC model. For anya ∈ B ⊆ A,

ais dispensable inBiffNH (B | (B - {a})) =0.

ais indispensable inB iff NH (B | (B - {a})) ≠0,

Proof. (1) ⇒ If a is dispensable in B, then N_B-{a} (x) = N_B (x) for all x ∈ U. It follows

$\log \frac{| N_{B} (x) \cap N_{(B - {a})} (x) |}{| N_{(B - {a})} (x) |} = 1 for all x \in U .$ Therefore,

NH (B | (B - {a})) =

$- \frac{1}{n} Σ_{x \in U} \log \frac{| N_{B} (x) \cap N_{(B - {a})} (x) |}{| N_{(B - {a})} (x) |} = 0 .$

⇐ If

NH (B | (B - {a})) =

$- \frac{1}{n} Σ_{x \in U} \log \frac{| N_{B} (x) \cap N_{(B - {a})} (x) |}{| N_{(B - {a})} (x) |} = 0$ , then $\log \frac{| N_{B} (x) \cap N_{(B - {a})} (x) |}{| N_{(B - {a})} (x) |} = 1$ for all x ∈ U, it follows N_B-{a} (x) ⊆ N_a (x) and with the fact of N_B-{a} (x) ⊆ N_B (x), then N_B-{a} (x) = N_B (x), thus a is dispensable.

(2) It is obvious from (1).

Theorem 7.LetS = (U, A) be a Multi-Relation GrC model. For anya ∈ A,

ais a core iffNH (A | (A - {a})) ≠0,

ais unnecessary iffNH (A | B) =0 ⇒ NH (A | (B - {a})) =0 for any B ⊆ A,

ais relative necessary iffNH (A | (A - {a})) =0 and there exists someB ⊆ Athat containsasuch thatNH (A | B) =0 and NH (A | (B - {a})) ≠0.

Proof (1) From Theorem 4.(1), a is indispensable in A⇔ a is a core. From Theorem 6.(2), a is indispensable⇔ NH (A | (A - {a})) ≠0. Therefore, a is core iff NH (A | (A - {a})) ≠0.

(2) From Theorem 5.(1), NH (A | B) =0 ⇔ B is a consistent set, NH (A | (B - {a})) =0 ⇔ (B - {a}) is a consistent set. The sufficiency condition means that if B is a consistent set, then (B - {a}) is also consistent, witch implies a is unnecessary.

(3) It holds from (1) and (2).

For a Multi-Relation GrC model S = (U, A) and two relation sets B, C ⊆ A, we say that B is finer than C if any x ∈ U satisfies N_B (x) ⊆ N_C (x), denoted by B ⪯ C.

Theorem 8.LetS = (U, A) be a Multi-Relation GrC model.B, C, D ⊆ A, if B ⪯ C, then NH (B | D) ≥ NH (C | D).

Proof. If B ⪯ C, then for any x ∈ U, N_B (x) ⊆ N_C (x), so $\frac{| N_{D} (x) \cap N_{B} (x) |}{| N_{D} (x) |} \leq \frac{| N_{D} (x) \cap N_{C} (x) |}{| N_{D} (x) |} \leq 1$ . By Definition 6, $\begin{matrix} NH (B | D) = - \frac{1}{n} Σ_{x \in U} \log \frac{| N_{D} (x) \cap N_{B} (x) |}{| N_{D} (x) |} \\ \geq - \frac{1}{n} Σ_{x \in U} \log \frac{| N_{D} (x) \cap N_{C} (x) |}{| N_{D} (x) |} \\ = NH (C | D) . \end{matrix}$

Corollary 3.LetS = (U, A) be a Multi-Relation GrC model.B, C, D ⊆ A, ifB ∪ D ⪯ C ∪ D, then NH (B | D) ≥ NH (C | D).

Proof. If B ∪ D ⪯ C ∪ D, it follows for any x ∈ U, N_D∪B (x) ⊆ N_D∪C (x), so $\frac{| N_{D} (x) \cap N_{B} (x) |}{| N_{D} (x) |} \leq \frac{| N_{D} (x) \cap N_{C} (x) |}{| N_{D} (x) |} \leq 1$ . By Definition 6, $\begin{matrix} NH (B | D) = - \frac{1}{n} Σ_{x \in U} \log \frac{| N_{D} (x) \cap N_{B} (x) |}{| N_{D} (x) |} \\ \geq - \frac{1}{n} Σ_{x \in U} \log \frac{| N_{D} (x) \cap N_{C} (x) |}{| N_{D} (x) |} \\ = NH (C | D) . \end{matrix}$

Corollary 3 means that for a fixed relation set D, when we add another relation set B or C to D, respectively, if B ∪ D are finer than C ∪ D, then NH (B | D) ≥ NH (C | D). Hence, we could use the neighborhood entropy to measure the uncertainty degree of one set of relations to another.

We give a heuristic reduction algorithm based on neighborhood entropy as followings. In the algorithm, the relation is selected one by one according to its uncertainty degree which is measured by the neighborhood entropy.

Algorithm 1. A reduction algorithm based on neighborhood entropy for a Multi-Relation GrC model. Input: A Multi-Relation GrC model S = (U, A) Output: A reduct red

1: Let red =∅;

2: Compute NH (A | (A - {a})), if NH (A | (A - {a})) ≠0, then let red = red ∪ {a} for all a ∈ A;

3: If red =∅, then {

31: Compute NH ({a}), for all a ∈ A;

32: Let NH ({a₀}) = max {NH ({a}) | a ∈ A};

33: Let red = {a₀},

}

4: While (NH (A | red) ≠0){

41: Compute

NH ({a} | red) for all a ∈ (A - red);

42: Let

NH ({a₀} | red) = max {NH ({a} | red),

for all a ∈ (A - red)};

43: Let red = red ∪ {a₀},

}

5: Return red.

From Theorem 7.(1), NH (A | (A - {a}))≠0 ⇔ a is a core. So step 2 picks all cores. From Corollary 3, if {a} ∪ red ⪯ {b} ∪ red, then NH ({a} | red) ≥ NH ({b} | red). We can say that step 4 picks the relation which maximizes NH ({a} | red) in the remaining relation set (A - red).

Example 4. (Continued with Example 3) Compute a reduct of the induced Multi-Relation GrC model in Example 3 with Algorithm 1.

1: Let red =∅;

2: Compute and obtain NH (A | (A - {a})) =0, for all a ∈ A, thus red =∅;

3: Since red =∅, then{

31: Compute NH ({a}), for all a ∈ A;

32: Obtain

NH ({a₂}) = max {NH ({a}) | a ∈ A};

33: Let red = {a₂};

}

4:(1)Since NH (A | {a₂}) ≠0, then {

41: compute

NH ({a} | {a₂}) for all a ∈ (A - {a₂});

42: Obtain that

NH ({a₅} | {a₂}) = max {NH ({a} | {a₂})

for all a ∈ (A - {a₂})};

43: Let red = {a₂} ∪ {a₅};

}

(2)Since NH (A | {a₂, a₅}) =0, step 4 ends;

5. Return a reduct {a₂, a₅}, the algorithm ends.

The result {a₂, a₅} obtained by Algorithm 1 is one of the reducts obtained in Example 3. Thus, we can see that Algorithm 1 is feasible to compute a reduct in a Multi-Relation GrC model.

Theorem 3 means a vertex subset of a graph is a minimal vertex cover if and only if it is a reduct of the induced Multi-Relation GrC model by the graph. So, {a₂, a₅} is also a minimal vertex cover of the graph G₂ in Example 3. Thus, Algorithm 1 can also be used to compute a minimal vertex cover of a graph just needing to convert the graph to its induced Multi-Relation GrC model firstly.

For convenience, here we summarize the processes by using the proposed rough set method to compute a minimal vertex cover of a graph in Algorithm 2.

Algorithm 2. A heuristic minimal vertex cover algorithm based on entropy for the VCP

Input: A graph

Output: A minimal vertex cover

step 1: Construct the induced Multi-Relation GrC model respected to the graph;

step 2: Compute a reduct of the induced Multi-Relation GrC model by Algorithm 1;

step 3: Return the reduct.

Given a graph G = (V, E) with V = {a₁, a₂, . . . , a_m} and E = {e₁, e₂, . . . , e_k}, the time complexity of step 1 and step 2 are $O (([\frac{1 + \sqrt{1 + 4 k}}{2}] + 1)^{2} m)$ and $O (([\frac{1 + \sqrt{1 + 4 k}}{2}] + 1)^{2} m)$ , respectively, so the time complexity of Algorithm 2 is $O (([\frac{1 + \sqrt{1 + 4 k}}{2}] + 1)^{2} m)$ .

5 Conclusions

In this study, we have converted the vertex cover problem in graph theory to the knowledge reduction problem in rough set theory and introduce a reduction algorithm to deal with the vertex cover problem. Thus, we have connected rough set theory with classical optimization theory and used the rough set-based methods to deal with the optimization problems. Moreover, there are many kinds of reduction algorithms in rough set theory. Based on the conversion, all these reduction algorithms can be used to deal with the vertex cover problem.

As we know, the vertex cover problem in graph theory has wide applications. Based on the conversion, the application of rough set theory can be expanded in some degree. There are many different types of optimization problems. Connecting them with data mining issues and realizing mutual utilization of methods from different fields are parts of our further works.

Footnotes

Acknowledgments

The authors thank the anonymous referees for their valuable comments and suggestions.

This work is supported by grants from the National Natural Science Foundation of China (Nos. 61379021, 61272021, 61303131, 61573321) and the Department of Education of Fujian Province (Nos. JA13202, JK2013027, JK2014028).

This work is also supported by Research start-up fee of Zhejiang Ocean University.

References

Bazgan

, Toubaline

and Tuza

, The most vital nodes withrespect to independent set and vertex cover, Discrete AppliedMathematics159(17) (2011), 1933–1946.

Berry

and Sigayret

, Representing a concept lattice by agraph, Discrete Applied Mathematics144(1-2) (2004), 27–42.

Bondy

and Murty

, Graph theory with application, Macmillan Press Ltd, 1976.

Bourgeois

, Escoffier

and Paschos

, Approximation of maxindependent set, min vertex cover and related problems bymoderately exponential algorithms, Discrete AppliedMathematics159(17) (2011), 1954–1970.

Chen

and Li

, An application of rough sets to graph theory, Information Sciences201 (2012), 114–127.

Chen

, Li

and Lin

, Computing connected components ofsimple undirected graphs based on generalized rough sets, Knowledge-Based Systems37 (2013), 80–85.

Gandhi

, Halperin

, Khuller

, Kortsarz

and SrinivasanAn

, improved approximation algorithm for vertex cover with hardcapacities, Journal of Computer and System Sciences72(2006), 16–33.

Harant

, Henning

, Rautenbach

and Schiermeyer

, Theindependence number in graphs of maximum degree three, Discrete Mathematics308(23) (2008), 5829–5833.

, Zhang

, Pan

, An

and Pedrycz

, Measuringrelevance between discrete and continuous features based onneighborhood mutual information, Expert Systems withApplications38 (2011), 10737–10750.

10.

and Cercone

, Learning in relational databases: A roughset approach, Computational Intelligence11(2) (1995), 323–338.

11.

Liang

, Chin

, Dang

and Yam

, A new method for measuring uncertainty and fuzziness in rough set theory, International Journal of General Systems31(4) (2002), 331–342.

12.

Liang

and Qian

, Information granules and entropy theory ininformation systems, Science in China Series F: InformationSciences51(10) (2008), 1427–1444.

13.

Liang

and Xu

, The algorithm on knowledge reduction inincomplete information systems, International Journal ofUncertainty, Fuzziness and Knowledge-Based Systems10(1) (2002), 95–103.

14.

Lin

T.Y.

, Neighborhood systems and relational database, Proceedings of CSC’88, 1988.

15.

Lin

T.Y.

, Topological and fuzzy rough sets, in: Slowinski

(Ed.), Intelligent Decision Support: Handbook of Applicationsand Advances of the Rough Sets Theory, Kluwer Academic Publishers, Boston, 1992, pp. 287–304.

16.

Lin

T.Y.

, Neighborhood systems and approximation in relationaldatabases and knowledge bases, Proceedings of the FourthInternational Symposium on Methodologies of Intelligent Systems, Poster Session, 1989, pp. 75–86.

17.

Lin

T.Y.

, Granular computing: Practices, theories, and future directions, Encyclopedia on Complexity of Systems Science, Springer, 2009, pp. 4339–4355.

18.

Pawlak

, Rough sets, International Journal of Computer andInformation Sciences11(5) (1982), 341–356.

19.

Pawlak

, Rough sets: Theoretical aspects of reasoning aboutdata, Kluwer Academic Publishers, Dordrecht, MA, 1991.

20.

Qian

and Liang

, Combination entropy and combinationgranulation in rough set theory, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems16(2) (2008), 179–193.

21.

Qian

, Liang

and Dang

, Converse approximation and ruleextraction from decision tables in rough set theory, Computers and Mathematics with Applications55(8) (2008), 1754–1765.

22.

Qian

, Liang

, Pedrycz

and Dang

, Positive approximation:An accelerator for attribute reduction in rough set theory, Artificial Intelligence174(9-10) (2010), 597–618.

23.

Shi

, He

and Xu

, An algorithm for seeking monitornodesnetwork traffic based on adjacency matrix, Journal ofComputer Research and Development46 (2009), 370–374.

24.

Skowron

and Rauszer

, The discernibility matrices andfunctions in information systems, in: Slowiński

(Ed.), Intelligent Decision Support, Handbook of Applications and Advances of the Rough Sets Theory, Kluwer, Dordrecht, 1992, pp. 331–362.

25.

Tan

, Li

and Lin

, Extended results on the relationshipbetween information systems, Infomation Sciences290(2015), 156–173.

26.

Tan

, Li

and Lin

, Connections between covering-based roughsets and concept lattices, International Journal ofApproximate Reasoning56 (2015), 43–58.

27.

Tsang

, Chen

and Yeung

, Approximations and reducts withcovering generalized rough sets, Computers and Mathematicswith Applications56(1) (2008), 279–289.

28.

Wang

, Rough set theory and knowledge acquisition, Xi’an Jiaotong University Publishing Company, Xi’an, 2001.

29.

Wang

, Yu

and Yang

, Decision table reduction based on conditional information entropy, Chinese Journal of Compute25(7) (2002), 759–766.

30.

Wang

and Wang

, Reduction algorithms based on discernibilitymatrix: The ordered attributes method, Journal of ComputerScience and Technology16(6) (2001), 489–504.

31.

Yang

, Wu

and An

, Internet network measurement theory and application, People’s Posts and Telecommunications Press, 2009.

32.

Yang

and Yang

, Rough set model based on neighborhood system, Journal of Nanjing University of Science and Technology36 (2012), 291–295.

33.

Yao

, Two views of the theory of rough sets in finite universes, International Journal of Approximate Reasoning15(4) (1996), 291–317.

34.

Yao

, Relational interpretations of neighborhood operators andrough set approximation operators, Information Sciences111(1) (1998), 239–259.

35.

Yao

, Neighborhood systems and approximate retrieval, Information Sciences176(23) (2006), 3431–3452.

36.

Zhang

and Qiu

, Uncertain decision-making based on roughset, Qinghua University Press, 2005.

37.

Zhao

, Guo

, Qian

and Qu

, On the problem of how to placethe observers in passive testing, Journal of ComputerResearch and Development42(10) (2005), 1815–1819.