Given an undirected graph $G$ with $n$ vertice and $m$ edges, can we construct $p$ complete $k_i$-partite graphs, where $p$ is finite (of course) and each vertex appears at most a constant number of times, satifying " the sum of such $p$ complete $k_i$-partite graphs is $G$ " ? Moreover, such construction can be done in poly-time ?
1 Answer
I think the answer to your first question is "no".
In particular, if you take a random bipartite graph $G=([n],[n],E)$ where $Pr[(i,j)\in E] = 1/2$ for each pair $(i,j)$, the answer is no with probability close to 1.
I am interpreting your first question as follow:
Given any graph $G$, is it always possible to find a collection of subgraphs such that
- each subgraph is a complete $k$-partite graph for some $k$,
- each edge in $G$ occurs in at least one of the subgraphs, and
- each vertex in $G$ occurs in at most a constant number of the subgraphs?
Proof. Fix $n$. Let $G$ be the random graph described above.
Since $G$ is bipartite any complete $k$-partite subgraph has to be bipartite.
First, I claim that with probability $1-o(1)$, every complete bipartite subgraph of $G$ has at most $4n$ edges.
(Here's why. For any pair of subsets $L\subseteq [n]$ and $R\subseteq [n]$ with $|L\times R| \ge 4n$, the probability that the complete bipartite subgraph with edge set $L\times R$ is in $G$ is $2^{-|L\times R|} \le 2^{-4n}$. There are fewer than $2^n\times 2^n = 4^n$ such pairs $L$ and $R$, Thus, by the naive union bound, the probability that any of the corresponding subgraphs is present in $G$ is at most $4^n 2^{-4n} \le 2^{-2n}$.)
Also, with probability $1-o(1)$, the graph $G$ has at least $n^2/4$ edges.
Thus, with probability $1-o(1)$, every complete bipartite subgraph in $G$ has at most $4n$ edges, and $G$ has at least $n^2/4$ edges. Assume this happens.
Now suppose for contradiction that a collection of subgraphs with the desired properties exists. Each of the subgraphs has edge set $L\times R$ for some pair of subsets $L$ and $R$. In $G$, direct all the edges in $L\times R$ from the larger side to the smaller side (to the left if $|L|\le |R|$, and to the right otherwise). Since $|L\times R|\le 4n$, the smaller of $L$ or $R$ must have size at most $2\sqrt n$.
Since each vertex is in $O(1)$ of the subgraphs, each vertex now has $O(\sqrt n)$ edges directed out of it. But all edges are directed one way or the other, so the number of edges in $G$ is at most the number of vertices times the maximum out-degree of any vertex, that is, at most $O(n\sqrt n)$. This contradicts the graph having at least $n^2/4$ edges.