Vertex deletion algorithm with connected constraint

Question

While working on a job distribution problem, I ended up hitting a graph problem that I can't seem to get a foothold on.

Consider a not-necessarily connected graph, like one shown below. Each step, we can delete up to N vertices from the graph, but can't delete two nodes if they are connected, only one or neither of the pair. Goal is to minimize the number of steps required to delete all vertices.

Example graph:

For example, for N=2, at step 1, we cannot delete 1 and 2 (as they are connected), but we can delete 1 and 5, since they are not connected. An example sequence of steps:

Step 1: delete nodes 0 and 2

Step 2: delete nodes 4 and 5

Step 3: delete nodes 1 and 6

And so on. There are "bad" sequences of steps, for example deleting all size 1 components before anything else. Any suggestions on where to learn more about this, or ways to generally solve this problem?

Answer 1

This problem is known as mutual exclusion scheduling. This problem is NP-hard for all $N \geq 3$ [1].

When $N = 2$, this is equivalent to the minimum edge cover problem on the complement graph. It is solvable in polynomial time by a graph matching algorithm.

This problem can also be viewed as a graph coloring problem, called $\ell$-bounded $k$-coloring. Bodleander and Fomin [2] showed this problem is polynomial-time solvable for bounded treewidth graphs.

• [1] Baker, Brenda S., and Edward G. Coffman Jr. "Mutual exclusion scheduling." Theoretical Computer Science 162.2 (1996): 225-243.
• [2] Bodlaender, Hans L., and Fedor V. Fomin. "Equitable colorings of bounded treewidth graphs." Theoretical Computer Science 349.1 (2005): 22-30.

Answer 2

If a graph has $n$ vertices then there is the obvious upper bound of $n$ steps where one vertex is removed in each step.

If a disconnected graph $G$ is composed of several connected components, the total number of steps required to remove all the vertices from $G$ is equal to the number of steps required to remove the connected component that requires the most steps to remove all its vertices as each connected component can be considered independently and the vertex removals from each connected component can be completed in one step.

Now consider the case of a connected graph. If there is a cut vertex, then it will be optimal to remove one of the cut vertices. The number of vertices in the largest connected component will be at most $n-2$. So if a graph has a cut vertex, it can be removed in $n-1$ steps.

Other than this, there isn't a better upper bound for graphs in general. Consider the complete graph, $K_t$. Removing any vertex results in the graph $K_{t-1}$ and only one vertex can be removed as every vertex is connected to every other vertex. So for $n$ vertices, there is always a graph that requires $n$ steps to remove.