Some NP-Complete Problems for Attribute Reduction in Consistent Decision Tables

Authors

  • Phan Dang Khoa Information Technology Institute Vietnam National University, Hanoi 144, Xuan Thuy, Cau Giay District Hanoi, Vietnam
  • Janos Demetrovics Institute for Computer Science and Control (SZTAKI) Hungarian Academy of Sciences 13-17, Kende u. H-1111 Budapest, Hungary
  • Vu Duc Thi Information Technology Institute Vietnam National University, Hanoi 144, Xuan Thuy, Cau Giay District Hanoi, Vietnam
  • Pham Viet Anh Hanoi University of Industry 298, Cau Dien St, Bac Tu Liem District Hanoi, Vietnam

Keywords:

Attribute Reduction, NP-Complete, Complexity, Consistent Decision Table, Rough Set Theory

Abstract

Over recent years, the research of attribute reduction for general decision
systems and, in particular, for consistent decision tables has
attracted great attention from the computer science community due to the
emerge of big data. It has been known that, for a consistent decision table,
we can derive a polynomial time complexity algorithm for finding a
reduct. In addition, finding redundant properties can also be done in polynomial
time. However, finding all reduct sets in a consistent decision table
is a problem with exponential time complexity. In this paper, we study
complexity of the problem for finding a certain class of reduct sets.
In particular, we make use of a new concept of relative reduct in the consistent
decision table. We present two NP-complete problems related to the proposed concept.
These problems are related to the cardinality constraint and the relative reduct set.
On the basis of this result, we show that finding a reduct with the smallest
cardinality cannot be done by an algorithm with polynomial time complexity.

Author Biography

Phan Dang Khoa, Information Technology Institute Vietnam National University, Hanoi 144, Xuan Thuy, Cau Giay District Hanoi, Vietnam

Information Technology Institute
Vietnam National University, Hanoi
144, Xuan Thuy, Cau Giay District
Hanoi, Vietnam

Downloads

Published

2022-04-13

Issue

Section

Articles