The Complexity of Feature Selection for Consistent Biclustering - Clustering Challenges in Biological Network - page 262

D-CB: Is there a set of features that ensures biclustering is consistent, i.e., satisfies
(13.13)-(13.14)?

Clearly, D-CB is in NP since the answer can be checked in O ( m ) time for a
given set of features.
Next, the KNAPSACK problem will be reduced to D-CB in polynomial time
to complete the proof.
In a knapsack instance, a finite set U 1 ,asize s ( u )

Z + and a value v ( u ) ∈ ∈

Z + for each u Z + , and a value goal K Z + are

∈ U 1 , a size constraint B ∈ ∈

given. The question is
KNAPSACK: Is there a subset U U 1 such that u∈U s ( u ) ⊆ ≤ B

and u∈U v ( u ) ≥ K ?
We can modify the knapsack problem as
Π: Is there a subset U ⊆

U such that

s ( u ) ≤ 0 (13.15)

u ∈ U

v ( u ) ≥ 0? (13.16)

u ∈ U

-complete, since KNAPSACK can be reduced to its
modified variant if we define U = U 1 ∪

Obviously, Π remains NP

t , s ( t )= − B ,and v ( t )= − K .

Defining s ( u )= s ( u )+ α , v ( u )= v ( u )+ β for each u ∈ U and it can easily

be seen that

u∈U s ( u )
|U |

s ( u ) ≤ 0 ⇔ ≤ α (13.17)

u ∈ U

u∈U v ( u )
|U |

v ( u ) ≥ 0 ⇔ ≥ β (13.18)

u ∈ U

In microarray data sets, negative a ij values usually correspond to “bad” data
points. Note that, by selecting sufficiently large α and β values (i.e., α>B and
β>K ), the reduction is valid for the case where a ij are nonnegative.
The inequality signs in (13.17)-(13.18) can be changed to strong inequality as
follows

u∈U s ( u )
|

u∈U s ( u )
|U |

≤ α ⇔ <α + 1 (13.19)

U |

u∈U v ( u )
|

u∈U v ( u )
|U |

≥ β ⇔ >β − 2 (13.20)

U |