2
$\begingroup$

Given a undirected graph $G=(V,E)$ with $|V|=n$ and $|E|=2022n$ and some weight function $w\colon E\to \mathbb{R}$, and $0≤ w(e) ≤n$ for all $e∈E$,

Describe an algorithm that determines if the MST of $G$ only uses edges with an integer weight.

i got this question in exam 2 weeks ago and my solution didn't get any point (wrong solution). But i didn't really understand what wrong with it i will just write the main point of it here, and hope someone can point out/explain where is the problem in it.

My original solution :

  1. run "improved" DFS that save for each $v$ with his $π$ the "heaviest" non integer edge we found , the "heaviest" integer edge and the amount of non integer edge we found,
  2. i proved the MST cycle property same idea like this answer here and used property of uniqueness set of weight in any MST
  3. then i claim that while running DFS for each back discover => we close cycle => if we found integer heaviest $e$ edge and other non integer edge $e*$ between $v$ and $π[v]$ such as $w(e*)<w(e)$ => so $e*$ must appear in some MST => the algorism will stop and return that $G$ don't have MST with only integer value.

so it's total runtime will be $O(V+E)$ = > $O(n)$

the official solution run time is $O(E α(V))$ => $O(n α(n))$, where α is the inverse of the single-valued Ackermann function.

$\endgroup$
5
  • $\begingroup$ your proof that DFS maintains the cycle property is most likely incorrect, because DFS doesn't maintain that. Try rigrorously proving it, you would probably find a mistake in the proof. $\endgroup$ Mar 4 at 12:44
  • $\begingroup$ Btw, would you like a solution to the problem, or do you have the solution already? $\endgroup$ Mar 4 at 12:44
  • $\begingroup$ @AspiringMat thanks ! and that what I am try to do but why can't i maintain some pointer (like here stackoverflow.com/questions/12367801/…) ? and no i don't have any official solution for it $\endgroup$
    – sever
    Mar 4 at 12:54
  • $\begingroup$ Can we assume that you are able to take floors of real numbers in constant time? $\endgroup$
    – Steven
    Mar 4 at 13:49
  • $\begingroup$ @Steven i thinks yes $\endgroup$
    – sever
    Mar 4 at 13:51

3 Answers 3

5
$\begingroup$

The MST of $G$ is not well-defined since there might be multiple MSTs of a graph. However, it can be shown that:

Claim 1: either all MSTs use only edges with integer weights or none of them does.

Proof: Suppose towards a contradiction that there are two MSTs $T_1, T_2$ of $G$ such that $T_1$ only uses edges with integer weights while $T_2$ contains at least one edge $e$ with a weight in $\mathbb{R} \setminus \mathbb{Z}$.

Consider the fundamental cycle $C$ obtained by adding $e$ to $T_1$. Let $f$ be an arbitrary edge chosen from those having maximum weight in $C$. We cannot have $f=e$, since otherwise the edge of maximum weight in $C$ would be unique and hence $f$ would not belong to any MST. Moreover, we cannot have $f \neq e$ since otherwise the weight of $f$ must be larger than the weight of $e$ and hence $T_1-f+e$ is a spanning tree of $G$ that is lighter than $T_1$. $\square$

Let $I$ be the set of edges in $G$ having integer weights. The above claim tells us that, in order to solve your problem, it suffices to compute an arbitrary MST of $G$ and check whether it only uses edges in $I$. Consider a new graph $G'=(V, E')$ obtained from $G$ by reweighing each edge $e$ as follows: if the weight $w(e)$ of $e$ is an integer, let the new weight $w'(e)$ of $e$ be $2w(e)$. Otherwise, let the new weight $w'(e)$ be $2 \lfloor w(e) \rfloor + 1$. We can construct $G'$ in time $O(n)$ since $|E|=O(n)$ and we can take floors of real numbers in constant time, as per your clarification in the comments.

I claim the following:

Claim 2: there exists an MST of $G'$ that uses only edges with even weights if and only if there exists an MST of $G$ that uses only edges in $I$.

Proof: Let $T$ be an an MST of $G'$ that only uses edges with an even weight. Consider an edge $f = (u,v) \not\in I$ and notice that, since $w'(f)$ is odd, $f$ does not belong to $T$. Let $P$ be the unique path between $u$ and $v$ in $T$. From the cycle property and the fact that $w'(e) \neq w'(f)$, it follows that all edges $e \in P$ satisfy $w'(e) < w'(f)$. As a consequence $w(e) = \frac{w'(e)}{2} < \frac{w'(f)}{2} = \lfloor w(f) \rfloor + \frac{1}{2} < \lceil w(f) \rceil$ which implies $w(f) > w(e)$. As a consequence $f$ cannot belong to any MST of $G$.

Let $T$ be a MST of $G$ that only uses edges in $I$. Consider an edge $f=(u,v)$ such that $w'(f)$ is odd and notice that $f$ does not belong to $T$. Let $P$ be the unique path between $u$ and $v$ in $T$. From the cycle property and the fact that $w(e) \neq w(f)$ it follow that all edges $e \in P$ satisfy $w(e) < w(f)$. Then: $w'(e) = 2w(e) < 2w(f) < 2\lfloor w(f) \rfloor + 2 = w'(f) + 1$, which implies $w'(f) > w(e)-1$. Since $w'(e)$ is even and $w'(f)$ is odd, we must have $w'(f) > w(e)$, and hence $f$ cannot belong to any MST of $G'$. $\square$

To check whether there is an MST of $G'$ that only uses edges of even length, compare the weight of a MST of $G'$ (with weight function $w'$) with the weight of a MST of the subgraph of $G'$ containing only the edges in $I$ (and weight function $w'$).

Since both these graphs contain $O(n)$ edges with weights between $0$ and $2n+1 = O(n)$, their MSTs can be computed in time $O(n)$.

$\endgroup$
2
  • $\begingroup$ Your proof of claim 2 seems to have some typos. In the first part, don't you mean to assume that T is an MST of G' (not of G)? Isn't the conclusion supposed to be that f (not e) cannot belong to any MST of G? In the second part, isn't the conclusion supposed to be that f (not e) cannot belong to any MST of G'? $\endgroup$ Mar 4 at 20:48
  • $\begingroup$ @JohnBollinger, thank you! $\endgroup$
    – Steven
    Mar 4 at 20:59
4
+50
$\begingroup$

A simple algorithm

Here is the simplest and fastest algorithm to determine the MST of $G$ only uses edges with an integer weight. It runs in $O(E\,\alpha(V))=O(n\,\alpha(n))$ time.

  1. Define weight function $w'\colon E\to \mathbb{N}$.
    • If $w(e)$ is an integer, $w'(e) =2w(e)$.
    • Otherwise, $w'(e) =2\lfloor w(e)\rfloor + 1$.
  1. Sort all edges by their weights given by $w'$, which can be done in $O(n)$ time by a counting sort since weights are integers between $0$ and $2n+1$ and $|E|=2022n$.
  2. Run Kruskal's algorithm on $(G, w')$ with the following tweak. When edge $e$ is about to be added, if $w(e)$ is not an integer (or, what is equivalent, $w'(e)$ is odd), return "No".
  3. Return "Yes".

Proof of correctness. Since the set of weights in any MST is uniquely determined by the weighted graph,

  • there exists one MST of $(G,w)$ that contains integer-weighted edges only $\iff$ every MST of $(G,w)$ contains integer-weighted edges only, and
  • there exists one MST of $(G,w')$ that contains even-weighted edges only $\iff$ every MST of $(G,w')$ contains even-weighted edges only.

Suppose we have $\sigma$, a run of Kruskal's algorithm on $(G, w)$. We can make $\sigma'$, a run of Kruskal's algorithm on $(G,w')$ exactly like $\sigma$ except that step of sorting edges. Whichever edge is considered by $\sigma$ at some step, the same edge will be considered by $\sigma'$ at the corresponding step. In particular, $\sigma$ selects an integer-weighted edge $\iff$ $\sigma'$ selects an even-weighted edge. This is possible since Kruskal's algorithm only concerns about "the relative largeness" of weights and $w'$ is consistent with $w$, i.e., $w(e_1)\le w(e_2)$ $\iff$ $w'(e_1)\le w'(e_2)$.

The correspondence from $\sigma$ to $\sigma'$ means that every MST of $(G, w)$ contains integer-weighted edges only $\iff$ every MST of $(G,w')$ contains even-weighted edges only. $\quad\checkmark$

What is wrong with your solution?

The step 2 of your solution is, I believe, the correct observation that
every MST only uses integer-weighted edges $\iff$ every non-integer-weighted edge is the unique heaviest edge of some cycle that contains it (the cycle property).

However, step 3 of your solution may classify whether a non-integer-weighted edge has the cycle property the wrong way, since the "heaviest" non-integer-weighted edge and the "heaviest" integer-weighted edge saved so far at step 1 might not be applicable to the cycle found at step 3. Even it is, that non-integer-weighted edge might be the unique heaviest edge on another cycle. As mentioned by AspiringMat, you will not be able to prove the classification of edges by your algorithm is correct.

I cannot see how we can improve a DFS so as to rectify the problem above.

One correct way is to use the simple algorithm above, which finds the lightest edge among all non-integer-weighted edges that do not have that cycle property ("lightest" and "cycle property" are with respect to $w'$, and "non-integer-weighted" is with respect to $w$) if there are such edges.

$\endgroup$
0
2
$\begingroup$

Here is one way to do it. First get all the integer edges $E_{\mathbb{Z}}=\{e_1, ..., e_k\}$ in $O(m)=O(n)$ time. Since their weights are integers and bounded by $O(n)$, you can use bucket sort/radix sort to sort them in $O(n)$ time.

Now run Kruskal's algorithm on the sorted $E_{\mathbb{Z}}$. This takes $O(n\alpha(n))$. So now you have a MST $T$ that only uses the integral edges.

To verify that $T$ is indeed an MST for $E$, loop over the remaining edges $e=(u,v)$ in $E-E_{\mathbb{Z}}$ and verify that $w(u,v)$ is the maximum weight edge in the cycle in $T+\{e\}$ (since otherwise $T$ wouldn't be an MST). This step can be done in $O(n)$ by preprocessing $T$ and answering each query in $O(1)$ time.

So in total you get $O(n\alpha (n))$

More details on the Preprocessing step:

Here is how it works, for a given tree $T$, a line tree $L_T$ satisfies the following rules:

  1. $L_T$ has the same vertices as $T$.
  2. The maximum weight on the path between vertices $v$ and $u$ is the same for trees $T$ and $L_T$
  3. $L_T$ is just a line (so we can choose the order of the vertices on the line and the weights of edges between neighbouring vertices, but nothing else).

If you have a Line tree, answering the query can be done in $O(n)$ time and $O(1)$ preprocessing using range maximum/minimum queries.

To construct a line tree, pick the maximum edge $e$ in $T$ and remove it. This breaks $T$ into two trees. Now recursively calculate the line tree for both subtrees, and join them to the endpoints of $e$. This can be done in $O(n)$ time if you return the line trees recursively as a linked list. You can prove by induction that the line tree generated satisfies all $3$ rules.

$\endgroup$
8
  • 2
    $\begingroup$ "This step can be done in $O(n)$ by preprocessing $T$ and answering each query in $O(1)$ time". Can you elaborate? I could answer each query in $\log(n)$ time but not $O(1)$ time. $\endgroup$
    – John L.
    Mar 4 at 19:14
  • 1
    $\begingroup$ @AspiringMat, would you mind expanding a bit about the pre-processing needed for T in order to be able to to answer such queries in constant time? Also, is it possible to color the edges (let's say red for the edges in T), and then checking in linear time whether there exists a red edge which is the heaviest in a cycle instead (if so, T is not a MST of G)? $\endgroup$
    – Yuval
    Mar 4 at 19:21
  • $\begingroup$ To perform your radix sort in O(n) time, the number of digits in the integer weights would need to be O(1), yes? But it's not. The best upper bound we have on the weights is n, which has O(log n) digits, so I think your radix sort costs O(n log n). $\endgroup$ Mar 4 at 21:27
  • 1
    $\begingroup$ @Yuval added more details on the query $\endgroup$ Mar 5 at 7:29
  • 1
    $\begingroup$ @sbk Root the tree $T$ at any arbitrary root $r$. You can pre calculate the maximum edge under each node of the tree recursively in $O(n)$. Calculate the maximum edge on each of the subtrees, and your own maximum edge would be the maximum of all those. This can be precalculated in $O(n)$ time so that when you are constructing $L_T$, you have access to the maximum edge of the current subtree in $O(1)$ time. $\endgroup$ Mar 5 at 11:24

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.