The general α-decomposition problem of fuzzy relations

This paper deals with a general α  -decomposition problem of fuzzy relations, which can be stated as follows: given a fuzzy relation R∈F(X×Y)R∈F(X×Y), determine two fuzzy relations Q∈F(X×Z)Q∈F(X×Z) and T∈F(Z×Y)T∈F(Z×Y) such that R=QαT, where X (resp. Y) is a finite set. Firstly we point out that every fuzzy relation R is always generally α-decomposable, and give an algorithm to construct Q and T   with R=QαT for a given R  . Secondly, we show that the general content ρ(R)ρ(R) with ρ(R)=min{|Z|:R=QαT,Q∈F(X×Z),T∈F(Z×Y)} is equal to the chromatic number of the simple graph FR generated by R  . Therefore, finding an exact algorithm for calculating ρ(R)ρ(R) is an NP-complete problem.