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

Abstract EN

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.