10
$\begingroup$

We are given pairs of objects (say, numbers). Each object appears in at most $q$ pairs. Our goal is to distribute the pairs into equal-size bins, such that each object occurs in as few as possible different bins.

More precisely, we are interested in a function $f$ with the property that for every binary relation with $m$ pairs with at most $q$ pairs per object, there is a distribution of the pairs to $p$ bins, such that each bin receives $m/p$ pairs ($p$ should divide $m$), and no object occurs in more than $f(m,q,p)$ bins.

This question came up in our research on parallel query evaluation. One would expect that $m$ is large compared to $p$. The "right" size of $q$ is less clear. An interesting size for $q$ could be, e.g., $\sqrt{\frac{m}{p}}$. A function that does not depend on $q$, but only works for a certain range of $q$ would also be useful (but not $q=O(1)$).

Actually, we are after bounds of the form $p^{1-\epsilon}$, with $\epsilon>0$ as large as possible...

$\endgroup$
  • 3
    $\begingroup$ In graph terminology: given an integer $p$ and a graph $G=(V,E)$ with $m$ edges, with each vertex having degree at most $q$, find $p$ subgraphs $G_1, G_2, \ldots, G_p$ where $G_i=(V_i, E_i)$, such that $V=\bigcup_i V_i$, and $\{E_i\}_i$ is a partition of $E$ into $p$ parts each of size $m/p$, and each vertex $v\in V$ occurs in at most $k$ of the graphs $(\max_v |\{i : v\in V_i\}| \le k)$. Your goal is to minimize $k$. What's the best upper bound on $k$ you can show given $m$, $p$, and $q$? $\endgroup$ – Neal Young Jun 10 '17 at 5:40
  • $\begingroup$ That's right. In terms of graphs. The answer to the question is: $p$. Indeed, as written above, we are interested in bounds of the form $p^{1-\epsilon}$ and do not have any such bound for $\epsilon>0$. $\endgroup$ – Thomas S Jun 10 '17 at 11:18
  • $\begingroup$ A special case to get started: Let $n \ge 1$ be an odd integer. Can one partition the $n\choose 2$ edges of the complete graph $K_n$ into $n$ subsets of size $(n-1)/2$ such that, for each vertex, the number of subsets containing edges incident to that vertex is $O(n^{1-\epsilon})$, for some $\epsilon>0$? I bet yes for any $\epsilon<1/2$ --- take $n$ random vertex subsets of size $n^{1-\epsilon}$ each. Then with high probability each vertex is in about $n^{1-\epsilon}$ of the vertex subsets, and each pair $(i,j)$ is in about $n^{1-2\epsilon}$ of the subsets. Now assign the pairs to subsets... $\endgroup$ – Neal Young Jun 11 '17 at 17:24
  • $\begingroup$ In this case, the nodes can be first distributed into $\sqrt{n}$ sets of size $\sqrt{n}$ (think of intervals). Then each bin gets the product $I\times J$ of two such sets (I am considering the complete directed graph, whic is easier to state and asymptotically not much different). Hence, each vertex occurs in $\sqrt{n}$ bins, that is, $\epsilon=\frac{1}{2}$ in this case. $\endgroup$ – Thomas S Jun 11 '17 at 17:46
  • $\begingroup$ For the star graph ($n-1$ edges incident to one vertex $r$) the vertex $r$ has to be in each of the $p$ subgraphs, so for that case a bound less than $p$ is not possible. I guess that's why you restrict the max degree $q$? Maybe you could say something more definitive about that, since it seems to be a crucial assumption. Meanwhile, I left an observation (not an answer, but too big to fit as a comment!) as an answer below. $\endgroup$ – Neal Young Jun 12 '17 at 2:17
1
$\begingroup$

This is not an answer. It is just the somewhat trivial observation that WLOG you can relax the requirement that there be exactly $p$ edge subsets $\{E_i\}_i$ of exactly the same size, and instead just look for any number of edge subsets of of size $O(\textsf{the desired size})$. Maybe this helps think about the problem.

Fix any graph $G=(V,E)$ and integer $p\ge 1$. Let $s=\lceil |E|/p\rceil$

Lemma. Suppose there are subgraphs $\{G'_j=(V'_j,E'_j)\}_j$ such that $\{E'_j\}_j$ partitions $E$ into (any number of) parts of size $O(s)$. Let $$M = \max_{v\in V} |\{j : v\in V'_j\}|$$ be the maximum number of parts that any vertex is in.

Then there are $p$ subgraphs $\{G_i=(V_i,E_i)\}_i$ such that $\{E_i\}_i$ partitions $E$ into exactly $p$ parts each of size at most $s=\lceil |E|/p\rceil$, and $$\max_{v\in V} |\{i : v\in V_i\}| = O(M).$$

Proof. Starting with the sequence $E'_1, E'_2, \ldots, E'_{p'}$, replace each part $E'_j$ in the sequence by any ordered sequence of the edges contained in that part. Let $e_1, e_2, \ldots, e_m$ be the resulting sequence (a permutation of $E$ such that each part $E'_j$ is some "interval" $\{e_a, e_{a+1}, \ldots, e_b\}$ of edges in the sequence). Now partition this sequence into $p$ contiguous subsequences such that each except the last has size $s$, and let $E_i$ contain the edges in the $i$th contiguous subsequence. (So $E_i = \{e_{i\,s+1}, e_{i\,s+1}, \ldots, e_{(i+1)s}\}$ for $i<p$.)

By assumption each part $E'_j$ has size $O(s)$, and by design each part $E_j$ except the last part $E_p$ has size $s$, so (because of the way $\{E_i\}_i$ is defined) the edges in any given part $E'_j$ are split across $O(1)$ parts in $\{E_i\}_i$. This, and the assumption that each vertex occurs in at most $M$ of the parts in $\{E'_j\}_j$, imply that each vertex occurs in at most $O(M)$ of the parts in $\{E_i\}_i$. QED

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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