4
$\begingroup$

I had this question on a problem set recently, but I wasn't sure how to solve it.

Given a complete weighted undirected graph $G$, here are two "algorithms" to find a Hamiltonian path:

  • greedy: start at one vertex at random, and greedily choose the edge that leads to an unvisited vertex with smallest weight
  • anti-greedy: start at one vertex at random, and greedily choose the edge that leads to an unvisited vertex with largest weight

The question is, does there exist a $G$ so the anti-greedy algorithm is better than the greedy algorithm (smaller path weight)?

$\endgroup$
10
  • 1
    $\begingroup$ Have you tried constructing such a graph? $\endgroup$ Commented Mar 9, 2021 at 18:52
  • $\begingroup$ @YuvalFilmus I tried to make a graph where we could "lead" the greedy algorithm into a web of large edge weights and we could "lead" the anti-greedy algorithm into a web of small edge weights, but the problem I encountered was that the graph is complete, so the greedy algorithm moves into the small edge weight web and the anti-greedy algorithm moves into the large edge weight web eventually. This is just an idea, not very rigorous though. $\endgroup$
    – wxnopyt
    Commented Mar 9, 2021 at 19:27
  • 1
    $\begingroup$ What happens if you just put a minutes sign in front of the weights? $\endgroup$ Commented Mar 9, 2021 at 19:58
  • $\begingroup$ My bad, the weights of the edges should be positive. I'll edit the question to reflect this. $\endgroup$
    – wxnopyt
    Commented Mar 9, 2021 at 20:01
  • $\begingroup$ I couldn't find a satisfying answer, but I found that there is no such $G$ with $5$ vertices… (I found a contradiction for each of the 18 potential hamiltonian paths starting from 0, without loss of generality…). At least, that's that! $\endgroup$
    – Nathaniel
    Commented Mar 9, 2021 at 21:45

1 Answer 1

5
$\begingroup$

No.


In fact, we can prove the following stronger proposition.

Claim. Given a complete weighted undirected graph, a run of the greedy algorithm on it and a run of the anti-greedy algorithm on it, the $i$-th heaviest edge chosen by the greedy algorithm weighs no more than the $i$-th heaviest edge chose by the anti-greedy algorithm, for all valid $i$.

Proof. It is enough (and necessary) to show, given any weight $w$, the number of edges chosen by the greedy algorithm that weigh more than $w$ is no more than the number of edges chosen by the anti-greedy algorithm that weigh more than $w$.

Fix an arbitrary weight $w$. Let $\overrightarrow{u_1v_1}$, $\overrightarrow{u_2v_2}$, $\cdots$, $\overrightarrow{u_kv_k}$ be the edges chosen by the greedy algorithm that weigh more than $w$, in the same order as they were chosen by the greedy algorithm. Assume $k\ge1$; otherwise we are done.

Note that $u_1, u_2, \cdots, u_k$ and $v_k$ are distinct, since they are the starting vertex of distinct edges and the ending point of the last edge, respectively. Let $u_{k+1}=v_k$.

Consider any two vertex $u_p$ and $u_q$ such that the greedy algorithm visits $u_p$ earlier than $u_q$, i.e., $p<q$. We know $\overrightarrow{u_pv_p}$ weighs no more than $\overrightarrow{u_pu_q}$ since it weighs the least among all edges from $u_p$ to unvisited nodes. Since $\overrightarrow{u_pv_p}$ weighs more than $w$, so does $\overrightarrow{u_pu_q}$. We have just proved the simple and critical observation that all edges among $u_1, u_2,\cdots,u_{k+1}$ weigh more than $w$.

The anti-greedy algorithm will visit each vertex in $u_1, u_2, \cdots, u_{k+1}$ soon or later, since it will find a hamilton path. Consider the $m$-th time when the anti-greedy algorithm have just visited such a node. If $m\lt k+1$, then there is at least another such node that has not been visited, which means the next edge it will choose must weigh no less than the edge to that unvisited node, which weighs more than $w$ as we just proved above. That is, for each of the first $k$ times the anti-greedy algorithm must choose an edge that weigh more than $w$. $\quad\checkmark$

$\endgroup$
6
  • $\begingroup$ "hamilton path" should have been "hamiltonian path". "starting vertex" should have been "starting vertices". $\endgroup$
    – John L.
    Commented Mar 10, 2021 at 23:50
  • $\begingroup$ Nice proof, I'm wondering about the first step though ("Given any weight $w$..."). It seems sufficient, but it's not necessary: 1+1+8=10 > 3+3+3=9 even though when choosing $w=2$ we have the latter sequence with 3 edges > 2 vs. 1 for the former. Could you expand on the sufficiency? $\endgroup$ Commented Mar 11, 2021 at 3:50
  • 1
    $\begingroup$ @j_random_hacker Thanks. Yes, you are right that condition is not necessary for the sum of one sequence be smaller than the sum of another sequence. However, my proof is about the stronger claim, "the $i$-th heaviest edge chosen by the greedy algorithm weighs no more than the $i$-th heaviest edge chose by the anti-greedy algorithm, for all valid $i$". $\endgroup$
    – John L.
    Commented Mar 11, 2021 at 4:02
  • 1
    $\begingroup$ Suppose the i-th heaviest edge chosen by the greedy algorithm weighs is $w_i$. Let $w=w_i$. The number of edges chosen by the greedy algorithm that weigh more than $w$ is no less than $i$. So there are no less than $i$ edges chosen by the anti-greedy algorithm that weigh more than $w$. That means the i-th heaviest edge chose by the anti-greedy algorithm is at least $w$. So, it is suffices to show "given any weight $w$, the number of edges chosen by the greedy algorithm that weigh more than $w$ is no more than the number of edges chosen by the anti-greedy algorithm that weigh more than $w$". $\endgroup$
    – John L.
    Commented Mar 11, 2021 at 4:29
  • $\begingroup$ Thanks, I realise now that the sufficiency and necessity claims were about the stronger claim, not the original claim as I had mistakenly thought. Yes, your explanation of sufficiency is clear now (certainly for edges with distinct weights, I haven't thought carefully about the case where equal-weight edges are allowed), and the other direction is also clear, as is the fact that the inital claim implies greedy never produces a greater sum. $\endgroup$ Commented Mar 11, 2021 at 5:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.