An optimal procedure for vertex elimination in a graph

Question

Figure: An example of my problem Hi everyone. I'm struggling with a problem, and I really appreciate any hint. I have attached picture of an example where vertex 1 and 2 are connected to multiple vertices (green circles and blue squares). I want to gradually eliminate some of these blue and green vertices such that the number of edges connected to vertex 1 or 2 does not exceed 4. Also, my objective is doing this with the minimum number of eliminations. So, let's define it mathematically. If $d_B$ and $d_G$ respectively denote the number of remaining blue squares and green circles after elimination, and also if $d_i$ denotes the connected edges to vertex $i$ after elimination, my problem is how to organize an optimal elimination procedure such that it maximizes $min(d_B,d_G)$ while it satisfies $d_i\leq4$ for $i=1,2$.

Answer 1

Definitions:

• $d_1^s = d_{1B}^s + d_{1G}^s$ the number of single edges to vertex 1: $d_{1B}$ and $d_{1G}$ are the number of single edges blue and green to vertex 1, respectively.

• $d_2^s= d_{2B}^s + d_{2G}^s$ the number of single edges to vertex 2.

• $d^d= d_{B}^d + d_{G}^d$ the number of double edges.

Now,

• The number of vertexs blue and green will be: $$N_B = d_{1B}^s + d_{2B}^s + d_{B}^d$$ $$N_G = d_{1G}^s + d_{2G}^s + d_{G}^d$$

• The number of edges to vertexs 1 and 2 will be: $$d_1 = d_1^s + d^d = d_{1B}^s + d_{1G}^s + d_{B}^d + d_{G}^d$$ $$d_2 = d_2^s + d^d = d_{2B}^s + d_{2G}^s + d_{B}^d + d_{G}^d$$

We can see: $$ N_B + N_G = d_1 + d_2 - d^d $$

Aims:

We are asked for an algorithm to get $d_1 \leq 4$ and $d_2 \leq 4$ as well as $N_B$ and $N_G$ subject to being the maximum value of $\text{min} (N_B, N_G)$.

We consider the case $d_1 = 4$ and $d_2 = 4$ and look for the maximum value of $\text{min} (N_B, N_G)$ subject to $ N_B + N_G = 8 - d^d $. The solution to this optimization problem is $N_B = N_G = \frac{8 - d^d}{2}$, but because they are integers, sometimes this is not possible, and our aim is to get: $$N_B = 4-\left.\frac{ d^d}{2}\right|_{\mathcal{Z}_{\text{sgn}(d_G^d-d_B^d)}}$$ $$N_G = 4-\left.\frac{d^d}{2}\right|_{\mathcal{Z}_{\text{sgn}(d_B^d-d_G^d)}}$$ where $x|_{\mathcal{Z}_+}$ is rounding the real $x$ to the next integer and $x|_{\mathcal{Z}_-}$ is rounding the real $x$ to the previous integer. We introduce this condition because if $d_G^d-d_B^d > 0$ sometimes it will be the only option to get $N_G = N_B + 1$ (for example if $d_G^b = 3$ and $d_B^b = 0$, we can only get $N_G = 3$ and $N_B = 2$).

Algorithm:

All this means that first, we will try to remove all possible double edges, because they decrease the final $N_B$ and $N_G$ which decrease $\text{min} (N_B, N_G)$. But also, keeping a similar number of $d_G^d \sim d_B^d$, because if we have only $4$ double edges of the same color, the other colour will have $0$ vertices at the end and $\text{min} (N_B, N_G) = 0$. I leave the practical implementation for you to think. Keep in mind also the cases when you are starting already with $d_1 + d_2 <8$, which would change the aiming condition.

Answer 2

Here is a formulation using integer programming (IP).

Sets and Parameters:

• $G$ = set of green vertices
• $B$ = set of blue vertices
• $N$ = set of all vertices ($=G\cup B$)
• $a_{kn} = 1$ if black vertex $k$ ($k\in\{1,2\}$) in the original network, $0$ otherwise

Decision Variables:

• $x_n = 1$ if we remove vertex $n\in N$, $0$ otherwise
• $y = $ minimum (over {blue,green}) number of vertices in each group

Formulation:

$$\begin{alignat}{2} \text{maximize} \quad & y && \\ \text{subject to} \quad & y \le \sum_{b\in B} (1-x_b) \\ & y \le \sum_{g\in G} (1-x_g) \\ & \sum_{n \in N} a_{kn}(1-x_n) \le 4 &\quad& \forall k\in \{1,2\} \\ & x_n \in \{0,1\} && \forall n\in N \end{alignat}$$

The objective function maximizes the minimum number of vertices in each group (what you called $min(d_B,d_G)$ in your question). The first two constraints say that $y$ (the minimum) must be less than or equal to each of the vertex sets, after removals. (Note that $1-x_b$ and $1-x_g$ equal 1 if we don't remove the node and 0 if we do.) The third constraint says that for each black vertex $k$, the total number of edges that are connected to $k$ ($a_{kn}=1$) and are attached to a vertex that has not been removed ($1-x_n$) must be less than or equal to 4.

Now you can code this in your modeling language of choice and solve it with any IP solver.