3
$\begingroup$

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.

Example Graph

|cite|improve this question
$\endgroup$
  • $\begingroup$ Integer labels are predefined. $\endgroup$ – Vladimir Bogachev Dec 5 '19 at 11:59
6
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

First, let us solve the decision problem:

can we remove vertices such that the smallest group will have at least $T$ vertices?

This can be answered in a greedy fashion. At each step, pick an inconsistent edge $u,v$ (i.e., $u$ and $v$ have different labels) such that one of the vertices belong to a minimum size group, delete the vertex that belongs to a group which has more than $T$ vertices. If both have more than $T$ vertices delete one of them arbitrarily. If both have $T$ vertices return fail. Update the datastructre to reflect the deletion of the vertex, and repeat this step until all the inconsistent edges are removed.

Now you can solve the original problem by doing a binary search on $T$, and find the maximum value $T$ for which we have a success.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ If the two groups both have more than $T$ vertices it is not clear which vertex should be removed. This is not something you can decide locally. If for an edge $(u,v)$ we decide to remove $u$ (but could also have chosen to remove $v$), it can turn out later that this was a bad choice. $\endgroup$ – Tom van der Zanden Dec 5 '19 at 12:42
  • $\begingroup$ you can choose either one $\endgroup$ – Ameer Jewdaki Dec 5 '19 at 12:45
  • $\begingroup$ Consider the following graph, which consists of $5$ connected components, which are $4$ loose edges and $1$ loose vertex (numbers are labels): $1-2,1-4,1-4,2-2,1$. $T=2$. When the algorithm considers edge $1-2$ it has free choice between $1$ and $2$ because there are $3$ vertices with label $2$ and $4$ vertices with label $1$. However, the choice to delete $1$ is wrong because we will get a fail when processing the $1-4$ edge. $\endgroup$ – Tom van der Zanden Dec 5 '19 at 12:55
  • $\begingroup$ can you make a distinction between vertex and labels? I'm not sure how your example graph looks like $\endgroup$ – Ameer Jewdaki Dec 5 '19 at 12:58
  • 1
    $\begingroup$ If the edge between vertices with labels $1$ and $2$ is processed first it will arbitrarily delete one of them but this is incorrect, as the vertex with label $2$ must be deleted. $\endgroup$ – Tom van der Zanden Dec 5 '19 at 13:02

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.