0
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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.

$\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.