0
$\begingroup$

When attempting to set up an ILP formulation for a weight-minimal cubic spanning tree (i.e. one with vertex degrees either 1 or 3) I needed connectivity constraint, but misremembered the contents of this answer to another question I had posed. I thought that the solution was based on degree sums and so played around a bit and arrived at the following iteration:

  • $\omega^0(v_i):=0\quad \forall v_i\in V$
  • $\omega^1(e_{ij}):=1\quad \forall e_{ij} \in E$
  • $\omega^{2k}(v_i)\ =\ \sum_{j}\omega^{2k-1}(e_{ij})$
  • $\omega^{2k+1}(e_{ij})\ =\ \omega^{2k}(v_i)+\omega^{2k}(v_j)$

As it turned out, that iteration yields a tour-elimination constraints, that are different from the MTZ constraints but they require a reformulation of TSP problems as optimal Hamilton path problems.

The image shows a worked example with and without a disconnected cycle and, as can be seen, after a certain number of iterations the maximum of the $\omega^{2k+1}(e_{ij})$ of the connected linear graph lags behind the disconnected one that has a cyclic component; the highlighted powers of two make the different behavior more visible:

worked example for graph iteration

Caveat: The number of constraints is bigger than in the MTZ formulation and besides that, the value of the constants factors can depend super-polynomially on the number of iterations.
For those reasons I doubt that my findings are of any relevance for the practical solution of TSP problem instances, even if their size is moderate.


Questions:

  • has the described graph iteration already been encountered before?

  • what is the limit behavior of the generated edge weights, i.e. what can be said about the set of edges of non-regular graphs, that (in the limit) generate the maximal values (for regular graphs the answer is of course trivial)?

$\endgroup$
  • $\begingroup$ If you represent the omega functions by vectors, and call by A an edge-vertex incidence matrix, and B its transpose, then each function is of a power of BA (or AB) times either a unit vector or vector of degrees of the appropriate length. In this formulation I imagine it has been explored, but I have no references for you. Gerhard "Leaves The Analysis To You" Paseman, 2018.06.09. $\endgroup$ – Gerhard Paseman Jun 9 '18 at 21:04
  • $\begingroup$ Upon further consideration, one of the products above should be the adjacency matrix of the (I assume simple loopless and undirected) graph plus a diagonal matrix D with the jth diagonal entry the degree of vertex v_j. So the w2k functions on the vertices considered as vectors should be powers of (A+D) on the vector of vertex degrees, and w2k+1 easily derived from these. I know nothing about graph Laplacians or similar constructs derived from adjacency matrices, but I would look through that literature for connections to your dynamic. Gerhard "Did Not Leave It Alone" Paseman, 2018.06.09. $\endgroup$ – Gerhard Paseman Jun 9 '18 at 22:56
  • $\begingroup$ Indeed, if you change w0 to be the vector with coefficients 1/2 instead of 0, you can start the recursion from this constant nonzero vector. Gerhard "Not Seeing W0 Used Otherwise" Paseman, 2018.06.09. $\endgroup$ – Gerhard Paseman Jun 9 '18 at 23:00
  • $\begingroup$ Finally, approaching but not answering your question, the edge version of your matrix is (E + 2I), which is a square matrix indexed by pairs of edges, with the sum having 2's on the diagonal, 1's when two different edges share a vertex, and 0 otherwise. This may relate to dual graphs or line graphs, but I am guessing here. However, behaviours of powers of matrices like (E+2I) have been analyzed, and suggest to me the topic of incidence structures for your situation. Gerhard "Hopefully Those Are Enough Guesses" Paseman, 2018.06.09. $\endgroup$ – Gerhard Paseman Jun 9 '18 at 23:11
  • $\begingroup$ @GerhardPaseman thank you for the interesting feedback. That gives me some directions for further search. $\endgroup$ – Manfred Weis Jun 10 '18 at 6:55

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.