Correct implementation of binary relevance

I have questions regarding Binary Relevance implementation.

How to treat multi-label problem with empty class? (I have instance that cannot have any label). Should I introduce new label "NoLabel" in this case?

But there is an expensive way to solve this by using 2^{# Labels} -1 +1 multi-class classifier. 2^{# Labels} -1 is for direct mapping to binary relevance, and +1 is for the "No Label" Label.