2
$\begingroup$

Let's say we have a bipartite graph $G=(V_1\dot\cup V_2,E)$.

We're now looking for a two-coloring (red/blue) of the vertices of $V_1$, so that for all vertices $v\in V_2$ the sum of edges coming from red vertices differs at most by 1 from the sum of edges coming from blue vertices.

In other words, we're looking for a two-coloring $c:V_1\to\{-1,1\}$ so that the following formula holds: $$ \forall v\in V_2:\left( \sum_{v'\in V_1\\\{v,v'\}\in E}c(v')\in \{-1,0,1\}\right) $$

My question: Is finding such a two-coloring (or showing that no such two-coloring exists) NP-complete?

There's a (somewhat) linear algebra formulation of this problem, though it doesn't seem to be very helpful:

Let $V_1 = \{v_1,...,v_n\}$. Then we can define for every vertex $v\in V_2$ the row vector $(k_{1,v},...,k_{n,v})$ with $$k_{i,v} =\begin{cases} 1,&\text{if } \{v_i,v'\}\in E\\ 0,&\text{else}\end{cases}$$.

If we now let $c_i\in \{-1,1\}$ be the color of vertex $v_i$, then the requirements for the two-coloring can be written as: $$ \forall v\in V_2:\qquad (k_{1,v},...,k_{n,v}) \cdot \pmatrix{c_1\\...\\ c_n} \in \{-1,0,1\} $$ or equivalently with $V_2 = \{v'_1,...,v'_m\}$: $$ \pmatrix{k_{1,v'_1}&...&k_{n,v'_1}\\...&...&...\\ k_{1,v'_m}&...&k_{n,v'_m}} \cdot \pmatrix{c_1\\...\\ c_n} \in \{-1,0,1\}^m $$

$\endgroup$
1
  • $\begingroup$ Sounds like discrepancy... $\endgroup$ Apr 2, 2020 at 18:11

1 Answer 1

2
$\begingroup$

Your bipartite graph describes a set system whose elements are the vertices in $V_1$ and whose sets are the vertices in $V_2$. Your condition is the same as asking whether the discrepancy is at most $1$.

If all sets have even size (i.e., all vertices in $V_2$ have even degree), then the discrepancy is always even, and so you are interested in whether a given set system in which each set has even size has discrepancy zero. It turns out that this is NP-hard even if all sets have size 4. This problem is known as Max-2-2-Set-Splitting.

There are much stronger NP-hardness results on discrepancy, such as Tight hardness results for minimizing discrepancy by Charikar, Newman and Nikolov. You can find pointers on Max-2-2-Set-Splitting there.

$\endgroup$
1
  • $\begingroup$ The set formulation is way cleaner than what I had cooked up there. Quite a let down though that there are such strong negative results (though it is interesting as well) $\endgroup$
    – Sudix
    Apr 2, 2020 at 19:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.