Implementing spanning_tree_distribution proved to have some NetworkX difficulties and one algorithmic difficulty. Recall that the algorithm for creating the distribution is given in the Asadpour paper as

1. Set $\gamma = \vec{0}$.
2. While there exists an edge $e$ with $q_e(\gamma) > (1 + \epsilon) z_e$:
• Compute $\delta$ such that if we define $\gamma’$ as $\gamma_e’ = \gamma_e - \delta$, and $\gamma_f’ = \gamma_f$ for all $f \in E\ \backslash {e}$, then $q_e(\gamma’) = (1 + \epsilon/2)z_e$.
• Set $\gamma \leftarrow \gamma’$.
3. Output $\tilde{\gamma} := \gamma$.

Now, the procedure that I laid out in my last blog titled Entropy Distribution Setup worked well for the while loop portion. All of my difficulties with the NetworkX API happened in the q inner function.

After I programmed the function, I of course needed to run it and at first I was just printing the gamma dict out so that I could see what the values for each edge were. My first test uses the symmetric fractional Held Karp solution and to my surprise, every value of $\gamma$ returned as 0. I didn’t think that this was intended behavior because if it was, there would be no reason to include this step in the overall Asadpour algorithm, so I started to dig around the code with PyCharm’s debugger. The results were, as I suspected, not correct. I was running Krichhoff’s tree matrix theorem on the original graph, so the returned probabilities were an order of magnitude smaller than the values of $z_e$ that I was comparing them to. Additionally, all of the values were the same so I knew that this was a problem and not that the first edge I checked had unusually small probabilities.

So, I returned to the Asadpour paper and started to ask myself questions like

• Do I need to normalize the Held Karp answer in some way?
• Do I need to consider edges outside of $E$ (the undirected support of the Held Karp relaxation solution) or only work with the edges in $E$?

It was pretty easy to dismiss the first question, if normalization was required it would be mentioned in the Asadpour paper and without a description of how to normalize it the chances of me finding the correct’ way to do so would be next to impossible. The second question did take some digging. The sections of the Asadpour paper which talk about using Krichhoff’s theorem all discuss it using the graph $G$ which is why I was originally using all edges in $G$ rather than the edges in $E$. A few hints pointed to the fact that I needed to only consider the edges in $E$, the first being the algorithm overview which states

Find weights ${\tilde{\gamma}}_{e \in E}$

In particular the $e \in E$ statement says that I do not need to consider the edges which are not in $E$. Secondly, Lemma 7.2 starts by stating

Let $G = (V, E)$ be a graph with weights $\gamma_e$ for $e \in E$

Based on the current state of the function and these hints, I decided to reduce the input graph to spanning_tree_distribution to only edges with $z_e > 0$. Running the test on the symmetric fractional solution now, it still returned $\gamma = \vec{0}$ but the probabilities it was comparing were much closer during that first iteration. Due to the fact that I do not have an example graph and distribution to work with, this could be the correct answer, but the fact that every value was the same still confused me.

My next step was to determine the actual probability of an edge being in the spanning trees for the first iteration when $\gamma = \vec{0}$. This can be easily done with my SpanningTreeIterator and exploits the fact that $\gamma = \vec{0} \equiv \lambda_e = 1\ \forall\ e \in \gamma$ so we can just iterate over the spanning trees and count how often each edge appears.

That script is listed below

import networkx as nx

edges = [
(0, 1),
(0, 2),
(0, 5),
(1, 2),
(1, 4),
(2, 3),
(3, 4),
(3, 5),
(4, 5),
]

G = nx.from_edgelist(edges, create_using=nx.Graph)

edge_frequency = {}
sp_count = 0
for tree in nx.SpanningTreeIterator(G):
sp_count += 1
for e in tree.edges:
if e in edge_frequency:
edge_frequency[e] += 1
else:
edge_frequency[e] = 1

for u, v in edge_frequency:
print(
f"({u}, {v}): {edge_frequency[(u, v)]} / {sp_count} = {edge_frequency[(u, v)] / sp_count}"
)

This output revealed that the probabilities returned by q should vary from edge to edge and that the correct solution for $\gamma$ is certainly not $\vec{0}$.

References#

A. Asadpour, M. X. Goemans, A. Mardry, S. O. Ghran, and A. Saberi, An o(log n / log log n)-approximation algorithm for the asymmetric traveling salesman problem, Operations Research, 65 (2017), pp. 1043-1061.