# Equivalent Characterizations of Some Graph Problems by Covering-Based Rough Sets

Authors: Shiping Wang; Qingxin Zhu; William Zhu; Fan Min
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Covering is a widely used form of data structures. Covering-based rough set theory provides a systematic approach to this data. In this paper, graphs are connected with covering-based rough sets. Specifically, we convert some important concepts in graph theory including vertex covers, independent sets, edge covers, and matchings to ones in covering-based rough sets. At the same time, corresponding problems in graphs are also transformed into ones in covering-based rough sets. For example, finding a minimal edge cover of a graph is translated into finding a minimal general reduct of a covering. The main contributions of this paper are threefold. First, any graph is converted to a covering. Two graphs induce the same covering if and only if they are isomorphic. Second, some new concepts are defined in covering-based rough sets to correspond with ones in graph theory. The upper approximation number is essential to describe these concepts. Finally, from a new viewpoint of covering-based rough sets, the general reduct is defined, and its equivalent characterization for the edge cover is presented. These results show the potential for the connection between covering-based rough sets and graphs.


---

## Body

## 1. Introduction

Covering is an extensively used form of data representation. As a generalization of classical rough set theory [1, 2], covering-based rough set theory [3, 4] was proposed to process this type of data. Due to its generality and universality, it has attracted much research interest. Covering reducts have been defined [5–9], approximation models [10–13] have been established, axiomatic systems [14–17] have been constructed, and generalization works [7, 18–21] have been conducted. In application, covering-based rough sets have been used in rule learning [22, 23], attribute reduction [24–26], feature selection [27, 28], and other fields [29–32].Graphs are important discrete structures consisting of vertices and edges that connect these vertices, and they can well describe the relationship among objects. Problems in almost every discipline can be addressed using graph models. However, some important problems in graphs are NP-hard optimization ones such as finding the minimal vertex cover [33] and edge cover [34]. Therefore, it is much necessary to equivalently characterize these problems with other approaches or forms in order to find other efficient solutions.In this paper, some graph concepts including vertex covers, independent sets, edge covers, and matchings are equivalently formulated using covering-based rough sets. First, a graph is represented with a covering, and an isomorphism from simple graphs without isolated vertices to a special type of coverings is constructed. Second, vertex covers, edge covers and matchings are equivalently described through the upper approximation number and independent sets with the lower approximation. Third, edge covers are also characterized by general reducts which are generalizations of the covering reduct. Furthermore, some graph problems are transformed into ones in covering-based rough sets. For instance, finding a minimal edge cover of a graph is equivalently converted to finding a minimal reduct of a covering.There are numerous applications concerning connections between covering-based rough sets and graphs. For example, chemical classification, job assignment, and production process arrangement can be well modeled by graphs. However, many of these practical problems are NP-hard. Due to equivalent characterizations of covering-based rough sets and graphs, these problems can be converted and addressed under the framework of covering-based rough sets. In this way, heuristic reduction algorithms [5–8] for them may be employed.The rest of this paper is arranged as follows. Section2 recalls some fundamentals related to covering-based rough sets and graph theory. In Section 3, the upper approximation number is presented, and its properties are studied. Section 4 represents graphs with coverings and establishes a one-to-one correspondence between a special type of coverings, and simple graphs without isolated vertices in an isomorphic sense. In Section 5, some important graph concepts including vertex covers, independent sets, edge covers, and matchings are formulated through the upper approximation number and lower approximation. Section 6 presents another equivalent characterization of edge covers by general reducts. In Section 7, this paper is concluded and further works are pointed out.


## 2. Basic Definitions

This section introduces some fundamental definitions related to covering-based rough sets and graphs.


### 2.1. Covering-Based Rough Sets

As a generalization of partitions, coverings are with strong applicability and high universality. For example, a course consists of a number of students, and all courses form a covering of all students. Since a student can choose several courses, the covering is not necessarily a partition of all students. All students compose the set of research objects, namely, universe of discourse.Definition 1 (covering).
LetU be a universe of discourse and C a family of subsets of U. If none of subsets in C is empty and ⋃C=U, then C is called a covering of U.Each subset in a covering is called a covering block also called a basic concept in knowledge discovery, and each subset of a universe is called a concept. An important idea of covering-based rough sets is to approximate a concept using some basic ones. This idea is implemented by a pair of lower and upper approximations.Definition 2 (approximations [3]).
LetC be a covering of U. For all X⊆U,
(1)X*=⋃{K∈C∣K⊆X},X*=⋃{K∈C∣K⋂X≠∅}
are called the lower and upper approximations of X (with respect to C), respectively.The lower approximation provides a certainty, and the upper one offers a probability. If we suppose that the universe is all students selecting courses and the covering is the set of all courses, then for any subset of students, its lower approximation is those courses which all students select in the subset, and its upper approximation is those courses which some students select in the subset.Some covering blocks may be redundant; in other words, removing them has little effect on the approximation accuracy. For example, if a course is a required one and all students must select it, then removing it does not affect the lower approximation. The concept of the reducible element was proposed to describe those redundant covering blocks.Definition 3 (reducible element [35]).
LetC be a covering of U and K∈C. K is called reducible in C if K can be expressed as a union of some elements in C-{K}; otherwise, K is irreducible. All irreducible elements of C are called the reduct of C, denoted as Reduct(C).The reducible element well reveals the relationship between coverings and their lower approximations. In fact, two coverings generate the same lower approximation if and only if their reducts are the same.


### 2.2. Graphs

Graphs are discrete structures to model the correlation between data. Theoretically, a graph is an ordered pair consisting of vertices and edges that connect these vertices.Definition 4 (graph [36]).
A graphG=(V,E) consists of a nonempty set of vertices V and a set of edges E. Each edge has either one or two vertices associated with it, called its endpoints. Generally, we write e=uv or e=vu for an edge e with endpoints u and v.The simple graph is a main research objective of graph theory, and many practical problems can be represented with a simple graph.Definition 5 (simple graph [36]).
A simple graph is a graph without loops or multiple edges, where a loop is an edge whose endpoints are equal and multiple edges are edges having the same pair of endpoints.Graphs are visual and efficient tools to reveal the interrelation between data. Different graphs may have a certain internal relation. For this reason, isomorphism is introduced to express the relationship between graphs.Definition 6 (isomorphism [36]).
An isomorphism from one simple graphG=(V(G), E(G)) to another one H=(V(H), E(H)) is a bijection f:V(G)→V(H) such that uv∈E(G) if and only if f(u)f(v)∈E(H). We say that G is isomorphic to H, denoted as G≅H, if there exists an isomorphism from G to H.In a graph that represents a road network (with straight roads and no isolated vertices), we can interpret the problem of finding the minimal vertex cover as the problem of placing the minimal number of policemen to guard the entire road network. It is noted that an isolated vertex of a graph is a vertex that is not an endpoint of any edge.Definition 7 (vertex cover [36]).
LetG=(V,E) be a graph. A vertex cover of G is a set Q⊆V that contains at least one endpoint of any edge. The minimal size of vertex covers of G is denoted by β(G), simply by β.Definition 8 (independent set [36]).
LetG=(V,E) be a graph. An independent set of G is a set I⊆V, and any two vertices of I are not adjacent. The maximal size of independent sets of G is denoted by α(G), simply by α.Definition 9 (edge cover [36]).
LetG=(V,E) be a graph. L⊆E is called an edge cover of G if for all v∈V, there exists lv∈L such that v is its endpoint. The minimal size of edge covers is denoted by β′(G), simply by β′.Definition 10 (matching [36]).
LetG=(V,E) be a graph. A matching M in G is a set of pairwise no-adjacent edges. A maximal matching is a matching M of a graph with the property that if any edge not in M is added to M, it is no longer a matching. The maximal size of matchings of G is denoted by α′(G), simply by α′. A perfect matching is a matching which matches all vertices of the graph.


## 2.1. Covering-Based Rough Sets

As a generalization of partitions, coverings are with strong applicability and high universality. For example, a course consists of a number of students, and all courses form a covering of all students. Since a student can choose several courses, the covering is not necessarily a partition of all students. All students compose the set of research objects, namely, universe of discourse.Definition 1 (covering).
LetU be a universe of discourse and C a family of subsets of U. If none of subsets in C is empty and ⋃C=U, then C is called a covering of U.Each subset in a covering is called a covering block also called a basic concept in knowledge discovery, and each subset of a universe is called a concept. An important idea of covering-based rough sets is to approximate a concept using some basic ones. This idea is implemented by a pair of lower and upper approximations.Definition 2 (approximations [3]).
LetC be a covering of U. For all X⊆U,
(1)X*=⋃{K∈C∣K⊆X},X*=⋃{K∈C∣K⋂X≠∅}
are called the lower and upper approximations of X (with respect to C), respectively.The lower approximation provides a certainty, and the upper one offers a probability. If we suppose that the universe is all students selecting courses and the covering is the set of all courses, then for any subset of students, its lower approximation is those courses which all students select in the subset, and its upper approximation is those courses which some students select in the subset.Some covering blocks may be redundant; in other words, removing them has little effect on the approximation accuracy. For example, if a course is a required one and all students must select it, then removing it does not affect the lower approximation. The concept of the reducible element was proposed to describe those redundant covering blocks.Definition 3 (reducible element [35]).
LetC be a covering of U and K∈C. K is called reducible in C if K can be expressed as a union of some elements in C-{K}; otherwise, K is irreducible. All irreducible elements of C are called the reduct of C, denoted as Reduct(C).The reducible element well reveals the relationship between coverings and their lower approximations. In fact, two coverings generate the same lower approximation if and only if their reducts are the same.


## 2.2. Graphs

Graphs are discrete structures to model the correlation between data. Theoretically, a graph is an ordered pair consisting of vertices and edges that connect these vertices.Definition 4 (graph [36]).
A graphG=(V,E) consists of a nonempty set of vertices V and a set of edges E. Each edge has either one or two vertices associated with it, called its endpoints. Generally, we write e=uv or e=vu for an edge e with endpoints u and v.The simple graph is a main research objective of graph theory, and many practical problems can be represented with a simple graph.Definition 5 (simple graph [36]).
A simple graph is a graph without loops or multiple edges, where a loop is an edge whose endpoints are equal and multiple edges are edges having the same pair of endpoints.Graphs are visual and efficient tools to reveal the interrelation between data. Different graphs may have a certain internal relation. For this reason, isomorphism is introduced to express the relationship between graphs.Definition 6 (isomorphism [36]).
An isomorphism from one simple graphG=(V(G), E(G)) to another one H=(V(H), E(H)) is a bijection f:V(G)→V(H) such that uv∈E(G) if and only if f(u)f(v)∈E(H). We say that G is isomorphic to H, denoted as G≅H, if there exists an isomorphism from G to H.In a graph that represents a road network (with straight roads and no isolated vertices), we can interpret the problem of finding the minimal vertex cover as the problem of placing the minimal number of policemen to guard the entire road network. It is noted that an isolated vertex of a graph is a vertex that is not an endpoint of any edge.Definition 7 (vertex cover [36]).
LetG=(V,E) be a graph. A vertex cover of G is a set Q⊆V that contains at least one endpoint of any edge. The minimal size of vertex covers of G is denoted by β(G), simply by β.Definition 8 (independent set [36]).
LetG=(V,E) be a graph. An independent set of G is a set I⊆V, and any two vertices of I are not adjacent. The maximal size of independent sets of G is denoted by α(G), simply by α.Definition 9 (edge cover [36]).
LetG=(V,E) be a graph. L⊆E is called an edge cover of G if for all v∈V, there exists lv∈L such that v is its endpoint. The minimal size of edge covers is denoted by β′(G), simply by β′.Definition 10 (matching [36]).
LetG=(V,E) be a graph. A matching M in G is a set of pairwise no-adjacent edges. A maximal matching is a matching M of a graph with the property that if any edge not in M is added to M, it is no longer a matching. The maximal size of matchings of G is denoted by α′(G), simply by α′. A perfect matching is a matching which matches all vertices of the graph.


## 3. The Upper Approximation Number of Covering-Based Rough Sets

Covering-based rough sets are studied qualitatively, and they are short of quantitative approaches. The following definition presents a measure to conduct the quantitative analysis. This measure is also a bridge between covering-based rough sets and graphs.Definition 11 (upper approximation number [37, 38]).
LetC be a covering of U. One can define, for all X⊆U,
(2)fC(X)=|{K∈C∣K⋂X≠∅}|.fC(X) is called the upper approximation number of X and fC, the upper approximation number function with respect to C. When there is no confusion, we omit the subscript C.The above definition presents the upper approximation number with respect to a covering. Note that this concept can be defined similarly on any subcovering or family of subsets of a universe.Example 12.
LetU={a,b,c,d}, K1={a,b}, K2={a,b,c}, K3={c,d}, and C={K1,K2,K3}. If X={a,d} and Y={c,d}, then f(X)=|{K1,K2,K3}|=3 since K1⋂X≠∅, K2⋂X≠∅, and K3⋂X≠∅. Similarly, f(Y)=2.The following proposition shows some properties of the upper approximation number and its connections with covering-based rough sets.Proposition 13.
LetC be a covering of U and f the upper approximation number function. Then the following properties hold for all X,Y⊆U,(1)
f(∅)=0, f(U)=|C|,(2)
ifX⊆Y, then f(X)≤f(Y),(3)
for allu∈U, f({u})≥1,(4)
f(X⋃Y)+f(X⋂Y)≤f(X)+f(Y).When a covering is included in another one, their corresponding upper approximation numbers present a similar characteristic.Proposition 14.
LetC1 and C2 be two coverings of U. If C1⊆C2, then fC1(X)≤fC2(X) for all X⊆U.A partition can be equivalently characterized by the upper approximation number. A covering is a partition if and only if the upper approximation number of the set with only one element is equal to one.Proposition 15.
LetC be a covering of  U. Then C is a partition of U if and only if f({u})=1 for all u∈U.The upper approximation number plays an important role in both conducting quantitative analyses on covering-based rough sets and building connections between them and graphs.


## 4. Graphs Represented with Coverings

In this section, we convert a graph to a covering in order to construct a platform for solving graph problems using covering-based rough sets. The following definition points out an approach to representing a simple graph with a family of subsets of vertices.Definition 16.
LetG=(V,E) be a simple graph. One can define a family F(G) of subsets of vertices of G as follows: for all x,y∈V,
(3){x,y}∈F(G)⟺xy∈E.According to Definition16, a graph can be described with a family of subsets of its vertices. We say the family of subsets of vertices is induced by the graph. The following proposition presents the characteristics of the family of subsets of vertices.Proposition 17.
LetG=(V,E) be a simple graph. Then F(G) is a covering of  V if and only if G has no isolated vertices.Proof.
(⇒): If F(G) is a covering of V, that is, ⋃F(G)=V, then for all v∈V, there exists v′∈V such that {v,v′}∈F(G); that is, vv′∈E. Hence, G has no isolated vertices.
(⇐): If G has no isolated vertices, then for all v∈V, there exists v′∈V such that vv′∈E; that is, {v,v′}∈F(G). Thus, V=⋃v∈V‍{v}⊆⋃v∈V‍{v,v′}⊆⋃F(G)⊆V. Hence, ⋃F(G)=V; in other words, F(G) is a covering of V.According to Proposition17, a simple graph without isolated vertices can be characterized by a covering of its vertices. Therefore, the family of the vertices induced by a graph is denoted by C(G). In fact, any edge subset of a graph can also be represented with a covering or a subcovering. For example, if S is an edge subset of a graph, then we can define C(S) as follows:
(4)∀u,v∈V,{u,v}∈C(S)iffuv∈S.In the rest of this paper, a graph is a simple one without isolated vertices unless otherwise stated. The following example illustrates the graph and its covering.Example 18.
LetG=(V,E) be the graph as shown in Figure 1. Then C(G)={{a,b},{a,d},{b,c},{b,e},{b,g},{c,h},{c,f},{d,g},{d,e},{e,h},{e,f}}.Figure 1
A simple graph.The following proposition explores the relationship between two graphs inducing the same covering. In fact, two different graphs induce the same covering if and only if they are isomorphic. Isomorphic graphs can be regarded as the same in graph theory. In other words, in an isomorphic sense, a one-to-one correspondence between coverings whose elements have only two objects and graphs is established.Proposition 19.
LetG, H be two graphs and C(G), C(H) the coverings induced by G, H. Then C(G)=C(H) if and only if G≅H.


## 5. Graph Problems by the Upper Approximation Number

Independent sets, vertex covers, matchings, and edge covers of a graph are important concepts, and they stem abstractly from some practical problems. For instance, the maximal matching is from the job assignment problem. But some of them such as finding a minimal vertex cover are typical examples of NP-hard optimization problems. Therefore, there is much necessity to equivalently characterize these concepts. The following proposition presents a sufficient and necessary condition for the vertex cover through the upper approximation number.Proposition 20.
LetG=(V,E) be a graph and C(G) the covering induced by G and Q⊆V. Then Q is a vertex cover of G if and only if fC(G)(Q)=|C(G)|.Proof.
(⇒): For all {x,y}∈C(G), according to Definition 16, xy∈E. Since Q⊆V is a vertex cover of G, x∈Q or y∈Q which imply fC(G)(Q)≥|C(G)|. Conversely, fC(G)(Q)≤|C(G)| is straightforward. To sum up, it proves that fC(G)(Q)=|C(G)|.
(⇐): Since fC(G)(Q)=|C(G)|, for all {x,y}∈C(G), x∈Q or y∈Q. According to Definition 16, for all xy∈E, x∈Q or y∈Q. Therefore, Q is a vertex cover of G.In fact, in Proposition20, fC(G)(Q)=|C(G)| can be replaced with fC(G)(Q)=|C(E)|, since |C(G)|=|C(E)| for any graph, where |C(E)| denotes the number of edges. Therefore, based on the relationship between covering-based rough sets and graphs, a vertex cover of a graph can be described equivalently through the upper approximation number. Naturally, the minimal size of independent sets can also be represented by covering-based rough sets.Proposition 21.
LetG=(V,E) be a graph and β the minimal size of vertex covers of G. Then β=min{|Q|:fC(G)(Q)=|C(G)|}.Proof.
According to Definition7 and Proposition 20, it is straightforward.The above proposition shows that finding a minimal vertex cover of a graph is equivalently transformed into finding a minimal subset whose upper approximation number is equal to the cardinality.Example 22.
LetG=(V,E) be the graph as shown in Figure 1. Suppose that Q={b,d,f,h}, then fC(G)(Q)=|C(G)|. For all Q′⊆V and |Q′|<|Q|, fC(G)(Q′)<|C(G)|. Then the minimal vertex cover is β=|Q|=4, and a maximal vertex cover is presented in Figure 2.Figure 2
Maximal vertex cover.The following proposition indicates that an independent set of a graph can also be formulated equivalently with the lower approximation operator. In fact, a subset of vertices of a graph is an independent set if and only if its lower approximation is empty.Proposition 23.
LetG=(V,E) be a graph and I⊆V. Then I is an independent set of G if and only if I*=∅ where I*=⋃{K∈C(G)|K⊆I}.Proof.
(⇒): Since I is an independent set of G,  any two vertices of I are not adjacent which implies that {x,y}⋂I≠{x,y}, for all xy∈E. Hence, I*=∅.
(⇐): Since I*=∅, then {x,y}⋂I≠{x,y}, which implies that no two elements of I are adjacent. Hence, I is an independent set of G.Proposition 24.
LetG=(V,E) be a graph and α the maximal size of independent sets. Then α=max{|I|:I⊆V, and I*=∅}.Proof.
According to Definition8 and Proposition 23, it is straightforward.The above proposition indicates that finding a maximal independent set is converted to finding a maximal subset keeping its lower approximation empty. The following example illustrates independent sets of a graph and its connection with the lower approximation.Example 25.
LetG=(V,E) be the graph as shown in Figure 1. Suppose that I={a,c,e,g}, then I*=∅. For all I′⊆V and |I′|>|I|, I*′≠∅. Then the maximal size of independent sets is α=|I|=4, and a maximal independent set is presented in Figure 3.Figure 3
Maximal independent set.A matching of a graph can also be represented with the upper approximation number. In fact, an edge subset of the edges of a graph is a matching if and only if the upper approximation number of these sets having only one element is not less than one.Proposition 26.
LetG=(V,E) be a graph and M⊆E. Then M is a matching of G if and only if fC(M)({v})≤1 for all v∈V.Furthermore, the perfect matching of a graph is concisely characterized by the upper approximation number.Proposition 27.
LetG=(V,E) be a graph and M⊆E. Then M is a perfect matching of G if and only if fC(M)({v})=1 for all v∈V.Proposition 28.
LetG=(V,E) be a graph and α′the maximal size of matchings of G. Then α′=max{|M|:M⊆E and fC(M)({v})≤1 for all v∈V}.Example 29.
LetG=(V,E) be the graph as shown in Figure 1. Suppose that M={ab,cf,dg,eh}, then C(M)={{a,b},{c,f},{d,g},{e,h}}. Therefore, M is a maximal matching of G since fC(M)({v})≤1 for all v∈V. In fact, it is also a perfect matching. The matching is presented in Figure 4.Figure 4
A maximal matching.Proposition 30.
LetG=(V,E) be a graph and L⊆E. Then L is an edge cover of G if and only if fC(L)({v})≥1 for all v∈V.Proof.
(⇒): If L is an edge cover of G, then for all v∈V, there exists v′∈V such that vv′∈E, that is, {v,v′}∈C(L). Hence, fC(L)({v})≥1.
(⇐): If for all v∈V, fC(L)({v})≥1, then there exists v′∈V such that {v,v′}∈C(L); that is, vv′∈E. Thus, L is an edge cover of G.Proposition 31.
LetG=(V,E) be a graph and β′ the minimal size of edge covers of G. Then β′=min{|L|:L⊆E and fC(L)({v})≥1 for all v∈V}.


## 6. Graph Problems by General Reduct

This section presents another view to represent graph problems with covering-based rough sets. First of all, we define the generally reducible element of a covering, which is an extension of the reducible element in the literature [35].


### 6.1. General Reduct

Pawlak defined category reducts for knowledge reduction and rule extraction [39]. Zhu and Wang [35] proposed the reducible element to remove the redundancy and keep the essence. Some forms of reducible elements are defined and applied to rule learning [6] and other fields [12, 14]. The following definition proposes generally reducible elements to characterize graph concepts including edge covers and matchings.Definition 32 (generally reducible element).
LetC be a covering of U and K∈C. K is called a generally reducible element in C if C-{K} is also a covering of U; otherwise, K is called a generally irreducible element.Definition 33 (general reduct).
LetC be a covering of U and C′⊆C. C′ is called a general reduct of C, if ⋃‍C′=U and for all K′∈C′, K′ is a generally irreducible element of C′.Example 34.
LetU={a,b,c,d} and C={K1,K2,K3,K4}, where K1={a,b}, K2={a,c}, K3={a,b,c}, and K4={d}. Then K1, K2 and K3 are generally reducible elements of C; however, K1 and K2 are irreducible elements of C. And C1={K1,K2,K4} and C2={K3,K4} are general reducts of C.The following proposition shows that the generally reducible element is an extension of the reducible element. In other words, if a covering block is reducible, then it is generally reducible.Proposition 35.
LetC be a covering of  U and K∈C. If K is a reducible element of C, then K is a generally reducible element of C.Remark 36.
The generally reducible element is an extension of the reducible element; however, the general reduct is not an extension of the reduct. The following counterexample illustrates this argument.
LetU={a,b,c} and C={K1,K2,K3} where K1={a,b}, K2={b,c}, and K3={a,c}. Therefore, Reduct(C)=C; however, Reduct(C) is not a general reduct of C. In fact, the general reducts of C are C1={K1,K2}, C2={K1,K3}, and C3={K2,K3}.


### 6.2. Equivalent Characterization of Graph Problems by General Reducts

The following proposition explores the relationship between general reducts and edge covers of a graph. In fact, an edge subset of a graph is an edge cover if and only if it contains at least one general reduct.Proposition 37.
LetG=(V,E) be a graph and L⊆E. L is an edge cover of G if and only if there exists a general reduct G of C(G) such that G⊆C(L).Proof.
(⇒): If L⊆E is an edge cover, then for all v∈V, there exists lv=vv′∈L, such that v is its endpoint. This proves for all v∈V that there exists v′∈V such that {v,v′}∈C(L). Thus, V=⋃v∈V‍{v}⊆⋃v∈V‍{v,v′}⊆⋃C(L)⊆V. Then, ⋃C(L)=V. Hence, there exists G⊆C(L), such that G is a general reduct of C(L). So G is also a general reduct of C(G). Therefore, there exists a general reduct of G of C(G) such that G⊆C(L).
(⇐): If there exists a general reduct G of C(G) such that G⊆C(L), then C(L) is a covering of V. Hence, for all v∈V, there exists v′∈V, such that {v,v′}∈C(L); that is, vv′∈L. Hence, v is an endpoint of lv=vv′. Therefore, L is an edge cover of G.According to Proposition37, edge covers of a graph can be characterized by general reducts. In other words, finding a minimal edge cover of a graph is transformed equivalently into finding a minimal reduct of a covering.Proposition 38.
LetG=(V,E) be a graph. Then β′=min{|G|:G is a general reduct of C(G)}.Proof.
According to Proposition37, it is straightforward.Matchings of a graph can also be described using the generally reducible element.Proposition 39.
LetG=(V,E) be a graph and M⊆E. If M is a matching of G, then for all K∈C(M), K is a generally reducible element of C(G).Proposition39 shows a necessary condition for a matching of a graph by the generally reducible element. The following proposition further presents the characteristic of matchings using covering-based rough sets. In fact, an edge subset is a matching if and only if there exists an order such that those elements in the set can be reducible one by one according to the order.Proposition 40.
LetG=(V,E) be a graph, M⊆E, and |M|=m. Then M is a matching of G if and only if there is a permutation of elements of C(M) such that Ki∈C(M) is a generally reducible element of C(G)-{K1,…,Ki-1} for i=1,…,m.


## 6.1. General Reduct

Pawlak defined category reducts for knowledge reduction and rule extraction [39]. Zhu and Wang [35] proposed the reducible element to remove the redundancy and keep the essence. Some forms of reducible elements are defined and applied to rule learning [6] and other fields [12, 14]. The following definition proposes generally reducible elements to characterize graph concepts including edge covers and matchings.Definition 32 (generally reducible element).
LetC be a covering of U and K∈C. K is called a generally reducible element in C if C-{K} is also a covering of U; otherwise, K is called a generally irreducible element.Definition 33 (general reduct).
LetC be a covering of U and C′⊆C. C′ is called a general reduct of C, if ⋃‍C′=U and for all K′∈C′, K′ is a generally irreducible element of C′.Example 34.
LetU={a,b,c,d} and C={K1,K2,K3,K4}, where K1={a,b}, K2={a,c}, K3={a,b,c}, and K4={d}. Then K1, K2 and K3 are generally reducible elements of C; however, K1 and K2 are irreducible elements of C. And C1={K1,K2,K4} and C2={K3,K4} are general reducts of C.The following proposition shows that the generally reducible element is an extension of the reducible element. In other words, if a covering block is reducible, then it is generally reducible.Proposition 35.
LetC be a covering of  U and K∈C. If K is a reducible element of C, then K is a generally reducible element of C.Remark 36.
The generally reducible element is an extension of the reducible element; however, the general reduct is not an extension of the reduct. The following counterexample illustrates this argument.
LetU={a,b,c} and C={K1,K2,K3} where K1={a,b}, K2={b,c}, and K3={a,c}. Therefore, Reduct(C)=C; however, Reduct(C) is not a general reduct of C. In fact, the general reducts of C are C1={K1,K2}, C2={K1,K3}, and C3={K2,K3}.


## 6.2. Equivalent Characterization of Graph Problems by General Reducts

The following proposition explores the relationship between general reducts and edge covers of a graph. In fact, an edge subset of a graph is an edge cover if and only if it contains at least one general reduct.Proposition 37.
LetG=(V,E) be a graph and L⊆E. L is an edge cover of G if and only if there exists a general reduct G of C(G) such that G⊆C(L).Proof.
(⇒): If L⊆E is an edge cover, then for all v∈V, there exists lv=vv′∈L, such that v is its endpoint. This proves for all v∈V that there exists v′∈V such that {v,v′}∈C(L). Thus, V=⋃v∈V‍{v}⊆⋃v∈V‍{v,v′}⊆⋃C(L)⊆V. Then, ⋃C(L)=V. Hence, there exists G⊆C(L), such that G is a general reduct of C(L). So G is also a general reduct of C(G). Therefore, there exists a general reduct of G of C(G) such that G⊆C(L).
(⇐): If there exists a general reduct G of C(G) such that G⊆C(L), then C(L) is a covering of V. Hence, for all v∈V, there exists v′∈V, such that {v,v′}∈C(L); that is, vv′∈L. Hence, v is an endpoint of lv=vv′. Therefore, L is an edge cover of G.According to Proposition37, edge covers of a graph can be characterized by general reducts. In other words, finding a minimal edge cover of a graph is transformed equivalently into finding a minimal reduct of a covering.Proposition 38.
LetG=(V,E) be a graph. Then β′=min{|G|:G is a general reduct of C(G)}.Proof.
According to Proposition37, it is straightforward.Matchings of a graph can also be described using the generally reducible element.Proposition 39.
LetG=(V,E) be a graph and M⊆E. If M is a matching of G, then for all K∈C(M), K is a generally reducible element of C(G).Proposition39 shows a necessary condition for a matching of a graph by the generally reducible element. The following proposition further presents the characteristic of matchings using covering-based rough sets. In fact, an edge subset is a matching if and only if there exists an order such that those elements in the set can be reducible one by one according to the order.Proposition 40.
LetG=(V,E) be a graph, M⊆E, and |M|=m. Then M is a matching of G if and only if there is a permutation of elements of C(M) such that Ki∈C(M) is a generally reducible element of C(G)-{K1,…,Ki-1} for i=1,…,m.


## 7. Conclusions and Further Works

In this paper, we presented equivalent characterizations for some important problems in graph theory from the viewpoint of covering-based rough sets. These problems included vertex covers, independent sets, edge covers, and matchings of a graph, where finding a minimal vertex cover was NP-hard. The equivalent characterizations indicated covering-based rough sets approaches to these problems. Moreover, graph concepts such as vertex connectivity and graph approaches such as shortest path algorithms were available to study covering-based rough sets. In future works, we will apply these interesting theoretical results not only to algorithm design for some graph problems but also to unsupervised learning, especially bipartite graph clustering and spectral clustering.



---

*Source: 519173-2013-05-22.xml*