3 votes
Accepted

Balanced set coloring

I think this question is closely related to the term discrepancy. Here is the defintion. Given a universe $U$ a collection of sets $\mathcal{A}=\{S_i\}$ and a function $\varphi:U\to\{-1,1\}$. For $S\...
TheHolyJoker's user avatar
2 votes
Accepted

Which hypergraphs can be simplified by alternatively removing a hyperedge and an isolated vertex?

It is NP-complete to decide if a hypergraph admits an elimination sequence. The reason is that it can be seen to be equivalent to the following problem: given $n$ subsets of $\{1,2,\dots, n\}$ (...
Niranjan Kumar's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible