patternMinor
Vertex deletion algorithm with connected constraint
Viewed 0 times
vertexwithalgorithmconnectedconstraintdeletion
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#156167, answer score: 6
Revisions (0)
No revisions yet.