patternMinor
Removing vertices from a labelled graph
Viewed 0 times
graphremovingfromlabelledvertices
Problem
Let $G$ be an undirected graph with each vertex labeled with an integer. Is there an algorithm to remove a subset of vertices such that in the resulting graph with deleted vertices no vertices with different integer labels are connected with an edge, but also among all groups of vertices labeled with the same integer, the size of the smallest group (i.e., the number of vertices) is maximum possible?
For example, in the following picture there is a graph with v1, v7, v8, v9 labeled with 0 and the rest of the vertices labeled with 1. We can either remove v1 and will have 3 vertices labeled with 0 and 5 vertices labeled with 1, thus the size of the smallest group being 3. Or we can remove v4, v3 and v2, then we will have 4 vertices labelled with 0 and 2 vertices labelled with 1, thus the size of the smallest group being 2. We can remove isolated vertices too, but it will either decrease or wont change the size of the smallest group, so this isn't useful. Overall number of vertices removed is of no interest, it's just the size of the smallest group.
For example, in the following picture there is a graph with v1, v7, v8, v9 labeled with 0 and the rest of the vertices labeled with 1. We can either remove v1 and will have 3 vertices labeled with 0 and 5 vertices labeled with 1, thus the size of the smallest group being 3. Or we can remove v4, v3 and v2, then we will have 4 vertices labelled with 0 and 2 vertices labelled with 1, thus the size of the smallest group being 2. We can remove isolated vertices too, but it will either decrease or wont change the size of the smallest group, so this isn't useful. Overall number of vertices removed is of no interest, it's just the size of the smallest group.
Solution
The problem is $NP$-complete by reduction from $3$-SAT. In the reduction, the goal will be to have at least one vertex of each labeled class left.
For every variable, we create $2$ vertices linked by an edge that have unique colors. Which of these two vertices we delete will determine the truth value of this variable. We create an additional copy of this gadget, which is not connected to anything else but allows us to conserve one vertex of the opposite color class.
For every clause with $3$ literals, we create a clique on $3$ vertices (corresponding to the $3$ literals), each with unique colors. We must delete all but one of the vertices from this gadget, and the vertex which is not deleted signifies which literal causes the clause to be satisfied. We create two further copies of this gadget, which are not connected to anything else but (similarly to the variable gadgets) allow us to conserve vertices of the unused color classes.
We now connect every vertex whose preservation denotes making a true (resp. false) assignment to a variable to the literals which are incompatible with that assignment.
For a clause with $2$ literals we do the same, except with $2$ (instead of $3$) cliques on $2$ (instead of $3$) vertices.
For every variable, we create $2$ vertices linked by an edge that have unique colors. Which of these two vertices we delete will determine the truth value of this variable. We create an additional copy of this gadget, which is not connected to anything else but allows us to conserve one vertex of the opposite color class.
For every clause with $3$ literals, we create a clique on $3$ vertices (corresponding to the $3$ literals), each with unique colors. We must delete all but one of the vertices from this gadget, and the vertex which is not deleted signifies which literal causes the clause to be satisfied. We create two further copies of this gadget, which are not connected to anything else but (similarly to the variable gadgets) allow us to conserve vertices of the unused color classes.
We now connect every vertex whose preservation denotes making a true (resp. false) assignment to a variable to the literals which are incompatible with that assignment.
For a clause with $2$ literals we do the same, except with $2$ (instead of $3$) cliques on $2$ (instead of $3$) vertices.
Context
StackExchange Computer Science Q#118100, answer score: 6
Revisions (0)
No revisions yet.