1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Taking the question as in the title (so, without the roughly and the almost), this is clearly impossible for $K_{3,3}$. $\endgroup$ Commented May 3, 2020 at 0:30
  • $\begingroup$ true, I need it for an algorithm, so I am interested in a sympathetic behaviour and roughly in almost would be enough. $\endgroup$ Commented May 3, 2020 at 7:25

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Give me 1 hour or 2 ... $\endgroup$ Commented May 3, 2020 at 11:03
  • $\begingroup$ I just edited the question. In fact $2/9$ can be pretty acceptable. But $d$ can begi $\endgroup$ Commented May 3, 2020 at 13:28
  • $\begingroup$ In that case, taking a random colouring by flipping a fair 3-sided coin for each vertex seems to work. The expected number of vertices in $V$ that see all three colours is $\frac{2}{9} |V|$. $\endgroup$
    – Tony Huynh
    Commented May 3, 2020 at 17:05
  • $\begingroup$ It's not straightforward for me to get the $2/9$ bound for the general case with random coloring, still thinking ... $\endgroup$ Commented May 4, 2020 at 13:48
  • 1
    $\begingroup$ For a fixed vertex of degree 3, there are 27 ways its neighbours can be colored, and 6 of them in which its neighbours are rainbow. Since the colouring is random, the probability the neighborhood is rainbow is 6/27=2/9. Then use linearity of expectation. $\endgroup$
    – Tony Huynh
    Commented May 4, 2020 at 14:47
1
$\begingroup$

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.

$\endgroup$

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.