5
$\begingroup$

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:

enter image description here

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

enter image description here

Step 2: delete nodes 4 and 5

enter image description here

Step 3: delete nodes 1 and 6

enter image description here

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?

$\endgroup$

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The goal of the problem is to find a deletion-sequence that results in the optimal number of steps. In the case of the complete graph, the problem is trivial, since the optimal number of steps is obviously equal to the number of vertices, so you can delete the vertices one by one in any order. $\endgroup$
    – Stef
    Dec 14, 2022 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.