Some NP-Complete Problems for Attribute Reduction in Consistent Decision Tables
Serdica Journal of Computing, Tome 14 (2020) no. 1-2, pp. 27-41.

Voir la notice de l'article dans Bulgarian Digital Mathematics Library

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.
Mots-clés : Attribute Reduction, NP-Complete, Complexity, Consistent Decision Table, Rough Set Theory 
@article{SJC_2020_14_1-2_a2,
     author = {Khoa, Phan Dang and Demetrovics, Janos and Thi, Vu Duc and Anh, Pham Viet},
     title = {Some {NP-Complete} {Problems} for {Attribute} {Reduction} in {Consistent} {Decision} {Tables}},
     journal = {Serdica Journal of Computing},
     pages = {27--41},
     publisher = {mathdoc},
     volume = {14},
     number = {1-2},
     year = {2020},
     language = {en},
     url = {https://geodesic-test.mathdoc.fr/item/SJC_2020_14_1-2_a2/}
}
TY  - JOUR
AU  - Khoa, Phan Dang
AU  - Demetrovics, Janos
AU  - Thi, Vu Duc
AU  - Anh, Pham Viet
TI  - Some NP-Complete Problems for Attribute Reduction in Consistent Decision Tables
JO  - Serdica Journal of Computing
PY  - 2020
SP  - 27
EP  - 41
VL  - 14
IS  - 1-2
PB  - mathdoc
UR  - https://geodesic-test.mathdoc.fr/item/SJC_2020_14_1-2_a2/
LA  - en
ID  - SJC_2020_14_1-2_a2
ER  - 
%0 Journal Article
%A Khoa, Phan Dang
%A Demetrovics, Janos
%A Thi, Vu Duc
%A Anh, Pham Viet
%T Some NP-Complete Problems for Attribute Reduction in Consistent Decision Tables
%J Serdica Journal of Computing
%D 2020
%P 27-41
%V 14
%N 1-2
%I mathdoc
%U https://geodesic-test.mathdoc.fr/item/SJC_2020_14_1-2_a2/
%G en
%F SJC_2020_14_1-2_a2
Khoa, Phan Dang; Demetrovics, Janos; Thi, Vu Duc; Anh, Pham Viet. Some NP-Complete Problems for Attribute Reduction in Consistent Decision Tables. Serdica Journal of Computing, Tome 14 (2020) no. 1-2, pp. 27-41. https://geodesic-test.mathdoc.fr/item/SJC_2020_14_1-2_a2/