Let $G=(A,V)$ be directed acyclic graph. We say that two vertices $u,v$ is semi-independent if there is no directed path from $u,v$ or vice versa. Find the set of subsets $\{S_1,\ldots, S_k\}$ of pairwise semi-independent vertices with $k$ as small as possible such that any pair of semi-independent vertices contains in at least one $S_i$ for some $i$.
I just came up with this problem when I am trying to solve my homework. One trivial solution is to take all pair of semi-independent but $k$ is very large in this case. Does anyone have any answer or a bound? Many thanks for your help!
I believe this amounts to computing the edge clique cover number of a complete multi-partite graph, which is not trivial.
To see this, first call two vertices $u$ and $v$ strongly connected if there is a directed path from $u$ to $v$, and from $v$ to $u$ (thus, it is the opposite of semi-independent). It is not hard to show that this is a transitive relation, i.e. if $u,v$ are strongly connected and $v,w$ also are, then $u,w$ are strongly connected.
Consider the graph $H$ in which the vertices are $V(G)$, and $u,v$ share an edge iff they are strongly connected. It follows from the transitivity property that $H$ is consists in a set of vertex-disjoint cliques. Consider the complement $H^c$ of $H$. Then $H^c$ is a complete multipartite graph (see definition here) in which edges represent semi-independent pairs.
Now, an $S_i$ subset must correspond to a clique in $H^c$. Moreover, you want every edge of $H^c$ to be covered by some $S_i$.
Finding the minimum number of cliques that covers every edge is called the edge clique cover number. In the special case of complete multipartite graphs such as $H^c$, to my knowledge no precise values are known. Some bounds are known though - you can check here in Section 3.2 for some details.