Any graph $G$ can be seen as the sum of complete $k_i$-partite graphs?

Question

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 ?

Answer 1

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.