1
$\begingroup$

I am trying to design a parallel scheduling algorithm based on a constraint graph $G=(V,E)$ in which each node represents a task and each edge $e=(v_1, v_2)$ signifies, that tasks $v_1$ and $v_2$ can not be executed in parallel. Each task is executed exactly once, so the problem is finding "good" independent sets $V_i$, so that

$$ \bigcup_{i=1}^{k} V_i = V\\ $$

with all independent sets $V_i, V_j$ being pairwise disjoint. Since MaxIS is NP-Hard my approach would be solving MIS repeatedly (finding some maximal independent set, removing those vertices and start again until the Graph is empty). I know that in the worst case of $G$ being a clique this approach would yield $n$ iterations, however in my instance i would have the guarantee that the number of neighbors of each node would be upper-bound by $c \ll |V|$.

My question is: Given such a $c$ is there any upper bound on the number of necessary steps $k$?

$\endgroup$
2
1
$\begingroup$

A partition of a graph into independent set is the same as graph coloring. Therefore we can reformulate your question as follows:

Can we bound the chromatic number of a graph in terms of its maximum degree?

If every vertex has at most $c$ different neighbors, then the chromatic number is at most $c+1$, and this can be achieved using a greedy approach: scan the vertices in an arbitrary order, and color each vertex in a color different from all its already colored neighbors (this will always succeed since there are $c+1$ possible colors and only $c$ potential already colored neighbors).

There are graphs with maximum degree $c$ which have chromatic number $c+1$, for example the clique $K_{c+1}$ on $c+1$ vertices, so this bound is tight.

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