3
$\begingroup$

I'm trying to understand the algorithm described in "Degree constrained minimum spanning tree problem: a learning automata approach" (Javad Akbari Torkestani, The Journal of Supercomputing; April 2013, Volume 64, Issue 1, pp 226–249).

Given a undirected graph $G = (V, E)$, a weight function $w: E \rightarrow R$ and a value $d \ge 2$, the algorithm finds a spanning tree where each vertex has degree $\le d$ and try to minimize the weight of the spanning tree.

It's seems that for a complete graph the algorithm always create trees that are paths, it is weird since creating only paths does not explore the search space well. Considering that the algorithm find good trees it must do a good exploration of the search space. Note that all graphs in the test set used to evaluate the algorithm are complete.

Consider for example a complete graph with 5 vertices $(v_1, v_2, v_3, v_4, v_5)$. Suppose the algorithm chooses the root $v_1$ and first action is $v_2$ (that is, the $(v_1, v_2)$ edge). In the second iteration, $i = 2$, $A_2$ actions are update (line 6) to avoid cycles, so $A_2 = \{v_3, v_4, v_5\}$. Suppose that the action $v_3$ is selected, so the edge $(v_2, v_3)$ is added to the three. In the next iteration $i = 3$, and $A_3$ is update to $A_3 = \{v_4, v_5\}$, and so on, producing a path. In my understating, a path will always be produced independently of which vertex is chosen in each iteration, this is because the lines 23-24 (and 18-20) will not be executed for a complete graph. What I'm missing here?

I implemented the algorithm and it always produces paths. The results does not match the results in the paper...

The question is: how can the algorithm produce a tree that is not a path if the input graph is complete?


The algorithm description is in section 3.2. Here is a overview of the algorithm followed by the pseudo-code:

In this paper, a decentralized learning automata-based heuristic is presented to find a near optimal solution to the DCMST problem. In this method, each graph vertex is equipped with a learning automaton selecting its incident edges as the actions. This algorithm is composed of several stages and at each stage it constructs a degree-constrained spanning tree at random. To avoid the formation of a cycle, LACT uses variable action-set learning automaton and temporarily removes the actions corresponding to the already selected edges. LACT starts the tree construction process at the root node and each vertex randomly selects one of its incident edges, if any. The selected edge is penalized if its weight is greater than the minimum weight selected by the given vertex so far. It is rewarded otherwise. The vertex at the other end of the selected edge continues the tree construction process and this is repeated until a degree-constrained spanning tree is formed subject to the degree constraint. Each vertex locally decides on the optimality of its selected edges. As the proposed algorithm proceeds, for each vertex, the choice probability of the minimum weight incident edge converges to one. The convergence of the proposed algorithm to the optimal (or ε-optimal) solution is theoretically proved.

lact

$\endgroup$
  • $\begingroup$ Why is it weird to produce a path? Maybe the optimal solution is a path. Do you have an example where a path is not the optimal solution (where there is some other spanning tree that satisfies all the requirements and has an even lower weight)? $\endgroup$ – D.W. Oct 7 '16 at 19:49
  • $\begingroup$ Take for example any complete graph with a unconstrained mst X that is not a path, if d = |V|, then, the algorithm should be capable of finding X. $\endgroup$ – malbarbo Oct 7 '16 at 20:00
  • $\begingroup$ Have you been able to construct an explicit counterexample? Anyway, if I understood the introduction correctly, it looks like the paper only appears to claims it provides a heuristic that finds an approximate solution; based on a quick skim, it doesn't seem to claim that it is guaranteed to find the optimal solution. $\endgroup$ – D.W. Oct 7 '16 at 20:02
  • $\begingroup$ V = [0, 1, 2, 3], w(0, 1) = w(0, 2) = w(0, 3) = 0, w(1, 2) = w(2, 3) = w(3, 1) = 1. The mst is (0, 1), (0, 2), (0, 3) with weight 0, but the algorithm (as I understand it) finds a tree with weight 1. Consider d = 3. $\endgroup$ – malbarbo Oct 7 '16 at 20:07
  • $\begingroup$ The algorithm can find a tree with weight 1, 2 or 3, but not 0 (the only tree with weight 0 is not a path). $\endgroup$ – malbarbo Oct 8 '16 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.