One part of a bipartite graph has max degree 3. Partition the other part to 3 ~equal subsets s.t. just a fraction of first part see all 3 subsets

Question

Let $d \gg 1$. Let $G:=(U, V, E)$ be some bipartite graph such that deg$(u) \le d$ for all $u\in U$ and deg$(v) \le 3$ for all $v \in V$.

Now, is it possible to color vertices in $U$ with 3 colors such that firstly, size of each color class is roughly $|U|/3$ and secondly, at most a fraction $\beta$ of vertices in $V$ have neighbours from all the 3 color classes?

Specially interesting is the case $d \sim 20000$, and $\beta \ll 1 /3$.

Motivation The motivation is from computational complexity. I am trying to simplify the proof or improve Thm. 5.1 of [1]. For d=3 (this is not our $d$), in the first paragraph you make instances of 3-SAT with $n$ variables, where each variable appears in at most 20000 clauses. So there are at most $20000/3$ clauses with 3 variables.

Now, let $U$ be the set of variables, and $V$ be the set of clauses, and there be an edge between $u\in U$ and $v \in V$ iff $u \in v$.

If I have the desired coloring, then the second paragraph and its overhead can (by a trick) be avoided.

In the third paragraph each color class corresponds to a block of variables. Therefore, the size of each color class should be roughly $n/3$.

On the other hand, for each clause that has neighbours from all the color classes, (applying another trick) one variable should appear in two blocks, increasing the size of blocks by at most $\beta n$. Therefore we need $\beta \ll 1 /3$.

[1] M. Patrascu and R. Williams. On the Possibility of Faster SAT Algorithms. In SODA, pages 1065–1075, 2010.

Answer 1

Let $G=(U,V,E)$ be a bipartite graph where $U=[n], V=\binom{[n]}{3}$, and there is an edge between $u \in U$ and $v \in V$ if and only if $u \in v$. Then $\deg(u)=\binom{n-1}{2}$ for all $u \in V$ and $\deg(v)=3$ for all $v \in V$. However, every colouring of $U$ with $3$ colours, such that each colour class has size roughly $\frac{n}{3}$ has about $\frac{n^3}{27}$ vertices in $V$ with neighbours from all three colour classes. This is about a $\frac{2}{9}$ fraction of all the vertices in $V$.

I do not think that a $\frac{2}{9}$ fraction can be considered almost none for any reasonable definition of almost none, so this is probably impossible.

Answer 2

Here is an integer programming formulation of your problem. Not sure if it can provide an analytical insight, but hope it helps someway.

Consider a matrix $X\in \{0,1\}^{|U|\times 3}$, with exactly one 1 in each row. Such a matrix would indicate the membership of each $u\in U$ to one of the 3 groups that you seek. The column sums of $X$ is the number of elements in the three groups. Since you want all the groups of size around $N/3$, a good measure of how off you are would be the maximum of the columns sums. Thus, you would want to minimize $\max_{1\leq j \leq 3} \left(\sum_{i=1}^N X(i,j)\right)$.

Secondly, for a $v\in V$, let $I_v=(i ~ |~ (u_i,v)\in E)$. Also let $X_{[I, :]}$ be the sub-matrix obtained by choosing rows in the index set $I$. Note that the $\sum_{j=1}^{3}\max_{1\leq i\leq |I_v|}{X_{[I, :]}(i,j)}$ denotes the number of groups that $v$ is a neighbour to. Ideally, you would want this to minimize this too.

With the above points, the IP takes the final form given by: $$ \min_{X}~~\max_{1\leq j \leq 3} \left(\sum_{i=1}^N X(i,j)\right) + \lambda\left(\sum_{v\in V} \sum_{j=1}^{3}\max_{1\leq i\leq |I_v|}{X_{[I, :]}(i,j)}\right) \\\\ \mbox{subject to} \hspace{1cm} X\in \{\{0,1\}\}^{|U|\times 3}. $$ Here $\lambda>0$ is a trade-off factor, which the user needs to set. You could put the second term in the cost function as a constraint as well.

For smaller instances, you can possibly try with a free IP solver. For very large instances, try solving the relaxed LP of this problem (by changing $\{0,1\}$ to $[0,1]$) and rounding off to get the groups. I'll also admit that the approximation ratio of this method is something that needs further investigation.