# Prove choosing $\lceil\frac{V}{2}\rceil$ vertices accounts for at least $\frac{3}{4}$ of edges

Give a polynomial-time algorithm that finds $\lceil\frac{V}{2}\rceil$ vertices that collectively account for at least $\frac{3}{4}$ of the edges in an arbitrary undirected graph.

The algorithm I have come up with is a greedy algorithm that iterates through the graph choosing the node with the largest number of incident edges and then updating the adjacent vertices with their new incident edge count.

I am fairly confident this algorithm will work, however I am struggling with the proof that I will always account $\frac{3}{4}$ of the edges.

What I have so far is that because the sum of the degrees of all the edges in the graph is equal to $2E$ then on average every node will contribute at least a degree of $\frac{2E}{n}$ to that summation. $\frac{2E}{n}\times\frac{n}{2}$ vertices provides me with just $E$. Is this correct or am I missing something?

• Is the graph assumed to be connected? Otherwise, taking $2n$ vertices as $n$ pairs with just one edge between the vertices of each pair is a counterexample. (Not to mention how bad it gets if vertices of degree zero are allowed.) Commented May 14, 2014 at 15:11
• Well actually you can pick $V/2 = n$ vertices, one in each pair, and these vertices collectively account for all the edges. Degree zero vertices don't seem to pose a problem either, as you simply never choose them. Commented May 14, 2014 at 15:16
• @manuellafond You're right, of course. I must have reversed an inequality in my head somehow (argh). Commented May 14, 2014 at 15:17
• What you are missing is the concern that if you just pick the highest population vertices you may get most of the edges twice and too many not at all. For example, take $K_4+K_3$ The naive algorithm takes all the vertices of the $K_4$ and only gets $6$ edges out of $9$. Of course, you can take three vertices in the $K_4$ and one from the $K_3$ and succeed. You need to show you can always do that. Commented May 14, 2014 at 15:32
• @RossMillikan I interpreted the description of the algorithm differently: After picking each vertex, remove it and its adjacent edges from the graph. In that case, after picking the first vertex in your example, you're left with $K_3+K_3$. Pick two more, and you're left with $K_2+K_2$, and you have accounted for $3+2+2=7$ edges out of $9$ already. Commented May 14, 2014 at 15:39

Your reasoning is incorrect because when you select a vertex you remove it and its incident edges in which case the total number of edges decreases. If you stick to the original edges then you would be double-counting some of the edges since two vertices may cover the same edge, so you would get a lower bound of $\frac{1}{2}E$, which isn't good enough.

But if you keep track of the number of edges $E$, at step 1 it decreases by a factor of at least $\frac{2}{n}$ because the highest degree is at least $\frac{2E}{n}$, and at step 2 it decreases by a factor of $\frac{2}{n-1}$ for exactly the same reason. So $E$ is multiplied by at most $\frac{n-2}{n}$ and then $\frac{n-3}{n-1}$ and then ... After $\frac{1}{2}n$ steps (for even $n$; you can check that it's looser for odd $n$) $E$ would have been multiplied by at most $\frac{ (\frac{1}{2}n) (\frac{1}{2}n-1) } { n (n-1) }$, which would give the bound you want, and $\frac{3}{4}n$ is an asymptotically tight cutoff ratio because it is asymptotically achieved by the complete graph.

• Could you expand on the asymptotically tight part? I can see how keeping track of the edges at each iteration helps choose the most efficient nodes, but I'm not getting the asymptotic convergence you are mentioning. Commented May 14, 2014 at 18:20
• What is the product of the ratios $\frac{n-2}{n} \frac{n-3}{n-1} \cdots$ after $\frac{1}{2}n$ steps? As for asymptotically tight I was referring to $\frac{1}{4}$ being the optimal cutoff ratio, because for a complete graph the remaining number of edges will always be approximately $\frac{1}{4}$ of the original. Commented May 15, 2014 at 1:08
• Yes that's nicely done. You can see from here ($f$ is the number of edges left after the algorithm is done) : wolframalpha.com/input/… that $f \leq E \cdot (1/4 - 1/(4(n - 1))$, which goes to $E/4$ as $n$ tends to infinity (though no concrete value of $n$ makes this bound tight). Commented May 16, 2014 at 16:43

There is an amazingly simple randomized algorithm for this: sample $|E|\cdot k$ random subsets of size $|V|/2$ and return the one with highest number of incident edges. It works in $O\big(|E|^2\cdot k\big)$ time and returns a correct answer with probability $1-1/e^k$.

Unfortunately the proof is not so simple...

The proof:

For simplicity, let's assume that $n = |V|$ is even. We can do this, because we can always add an isolated vertex, which could be then discarded after obtaining a solution.

First, let's prove that is possible. Take a random subset $S \subset V$ of $n/2$ vertices, what is the expected number of edges incident to $S$? Observe that for any given edge three things could happen: both endpoints are in $S$, one endpoint is in $S$ or no endpoint is in $S$. Define accordingly:

\begin{align} \newcommand{inc}{\mathrm{inct}} \inc_0(S) &= \big\{e \in E\ \big|\ e \text{ has no endpoint in }S\big\},\\ \inc_1(S) &= \big\{e \in E\ \big|\ e \text{ has exactly one endpoint in }S\big\},\\ \inc_2(S) &= \big\{e \in E\ \big|\ e \text{ has exactly two endpoints in }S\big\}. \end{align}

These sets are disjoint, so summing the last two we get (in the derivation the set $S$ isn't quantified, because the numbers are the same for all)

\begin{align} \mathbb{E}X &= \mathbb{E}\Big(|\inc_1(S)| + |\inc_2(S)|\Big) \\ &= \sum_{e \in E} \mathbb{P}(e \in \inc_1(S)) + \mathbb{P}(e \in \inc_2(S)) \\ &= \sum_{(v_1,v_2) \in E} \mathbb{P}(v_1 \in S \land v_2 \notin S) + \mathbb{P}(v_1 \notin S \land v_2 \in S) + \mathbb{P}(v_1 \in S \land v_2 \in S) \\ &\stackrel{\!\!(\spadesuit)}{=} \sum_{(v_1,v_2) \in E} \mathbb{P}(v_1 \in S)\cdot\mathbb{P}(v_2 \notin S) + \mathbb{P}(v_1 \notin S)\cdot\mathbb{P}(v_2 \in S) + \mathbb{P}(v_1 \in S)\cdot\mathbb{P}(v_2 \in S) \\ &= \sum_{(v_1,v_2) \in E} \frac{1}{2}\cdot\frac{1}{2}+\frac{1}{2}\cdot\frac{1}{2}+\frac{1}{2}\cdot\frac{1}{2} = \frac{3}{4}|E| \end{align}

The expected number of incident edges is $\frac{3}{4}|E|$, so there has to be some subset of $V$ which realizes at least this number (i.e. maximum couldn't be smaller than the average).

One important point in this derivation is the equality marked by $(\spadesuit)$ where we apply, among others, $$\mathbb{P}(v_1 \in S \land v_2 \notin S) = \mathbb{P}(v_1 \in S)\cdot\mathbb{P}(v_2 \notin S),$$ which we can use only if the choice of $v_1$ and $v_2$ in $S$ were independent.

Now this raises a concern, because if we were to pick whether $v \in S$ or not independently with $\mathbb{P}(v \in S) = \frac{1}{2}$, then there is a slight chance that these will all "fire" at the same time and the resulting set wouldn't be a valid $S$, while at the same time it might be the one which bounces up the expected value so high.

Fortunately, we need only pairwise independence, and that allows us to pick a distribution which ensures that $S$ as $n/2$ vertices. In other words, it doesn't matter how we choose elements of $S$, the only thing we need is $P(v \in S) = \frac{1}{2}$ and pairwise independence.

Also, we know that $X \leq |E|$, so $Y = |E|-X$ is a non-negative random variable and we can use the Markov inequality. Moreover, $|X|$ is discrete, so

\begin{align} \mathbb{P}(X < \tfrac{3}{4}|E|) &= \mathbb{P}\Big(X \leq \tfrac{3}{4}|E|-\tfrac{1}{4}\Big) \\ &= \mathbb{P}\Big(Y \geq |E|-\tfrac{3}{4}|E|+\tfrac{1}{4}\Big) \\ &= \mathbb{P}\Big(Y \geq \tfrac{1}{4}|E|+\tfrac{1}{4}\Big) \\ &\leq \frac{\mathbb{E}Y}{\tfrac{1}{4}|E|+\tfrac{1}{4}} = \frac{\tfrac{1}{4}|E|}{\tfrac{1}{4}|E|+\tfrac{1}{4}} \\ &= \frac{|E|}{|E|+1} \end{align}

that is,

$$\mathbb{P}(X \geq \tfrac{3}{4}|E|) \geq \frac{1}{|E|+1}$$

and

\begin{align} \mathbb{P}(\text{we will find $S$ in $(|E|+1)k$ searches}) &\geq 1-\left(\frac{|E|}{|E|+1}\right)^{(|E|+1)k} \\ &= 1-\left(1+\frac{-1}{|E|+1}\right)^{(|E|+1)k} \\ &\geq 1-\frac{1}{e^k} \end{align}

Conclusion:

To find an appropriate set $S$ with probability $(1-\varepsilon)$ sample $|E| \log \frac{1}{\varepsilon}$ random subsets and pick the one with the highest number of incident edges.

I hope this helps $\ddot\smile$