2
$\begingroup$

I have the the following problem.

Say we have a graph $G = (V,E)$ where all $e \in E$ have positive weight, and $E$ can be separated in to two disjoint sets $E = A \cup B$. We have to find a spanning tree such that we minimize total weight but also we can only use a maximum of $c$ edges in $B$.

I feel like this is just Prim/Kruskal with an additional condition in the main if condition, but is that correct? I think we can still use a greedy algorithm but do not know how to show correctness.

$\endgroup$
2
$\begingroup$

Let us take Kruskal's algorithm for an example. Apparently, OP refers to the adjusted version such that when we choose among edges of equal weight, we will pick the ones in $A$ before the ones in $B$ as long as at least one edge in $A$ is left available. If the MST we arrive in the end has no more than $c$ edges in $B$, then that MST is the output. Otherwise, the output is empty, indicating no such MST has been found. Let us name this algorithm $A$-favoured Kruskal's algorithm.

To prove that $A$-favoured Kruskal's algorithm will find a satisfying MST whenever there is one is, in fact, not trivial even if we have been enlightened with or especially when we are distracted by the general techniques on how to prove greedy algorithm is correct.

Here goes my proof. Let us fix the weighted graph $G$ so that we will often be referring to $G$ implicitly. Let $R$ be a particular run of Kruskal's algorithm that produces $m$, an MST. Let $RA$ be a particular run of $A$-favoured Kruskal's algorithm that produce $ma$, another MST. ($RA$ may or may not be the same as $A$ and $ma$ may or may not be the same as $m$). Suppose $w_1\lt w_2\lt\cdots$ is the increasing sequence of all distinct edge weights. Break up the while loop of $R$ into smaller loops $R_1\lt R_2\lt\cdots$. For each $i$, $R_i$ iterates over all edges of weight $w_i$. For each such edge, $R_i$ adds it to the growing forest if it connects two different trees and ignores it otherwise. Let $F_i$ be the forest obtained at the end of $R_i$. Let $E_0=G$. For $i\gt0$, let graph $E_i$ has the same vertices as $G$ and all edges of $G$ except the edges of weights greater than $w_i$.

Using induction on $i > 0$, we can see that each connected component of $F_i$ (, which is a tree) is its corresponding connected component of $E_i$ minus some edges (the edges that were discarded because they did not connect different connected components(trees)). Let $g_i$ be the number of edges in $A$ of weight $w_i$ that are selected into $m$ during $R_i$. We can see that $g_i$ cannot bigger than $h_i$, the largest number of edges in $A$ of weight $w_i$ that can be added to $H_{i-1}$ without causing a cycle. In fact, $h_i$ is the decrease from the number of connected components in $E_{i-1}$ to the number of connected components in $E_{i-1}$ with all edges in $A$ of weight $w_i$ added. So $h_i$ depends only on $G$, $A$ and $i$. Note that $g_i$ will be $h_i$ if $R$ is actually a run of $A$-favoured Kruskal's algorithm, such as $RA$. So $$\#\{\text{edges in } A \text{ and } m\} = \sum_{i}g_i \leq \sum_{i}h_i = \#\{\text{edges in } A \text{ and } ma\}$$

Note that all MSTs can be found by Kruskal's algorithm. For a proof, you can check any MST is reachable by any MST algorithm with some minor exceptions. So we have shown that of all MSTs, $ma$ has the most edges in $A$. Since the number of edges in $ma$ is the same, $ma$ has the least edges in $B$. Proof is completed.

Indeed, we have proved more. Any run of $A$-favoured Kruskal's algorithm will produce an MST with the same number of edges with any given weight in $A$ and in $B$.

$\endgroup$

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.