Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am terrible at these kinds of discrete math problems, so I am asking here the following problem: Given a connected graph $G$ with vertices V[i], find an ordering P[] of its vertices such that there exists an edge between V[P[1]] and V[P[2]], and there is an edge between V[P[3]] and V[P[4]], etc. Basically, the ordering should be such that each successive pair of vertices in the ordering are connected by an edge. Assume that a solution exists. I just need some algorithm to solve this problem, and it doesn't even necessarily have to be all that efficient since the graph will have at most something like 30 vertices.

For the curious: the context of this problem is in generating the ordering of indices of a sparse matrix to guarantee the existence of a block 2x2 LDL^T factorization. The graph corresponds to the non-zero pattern of a diagonal-block of the matrix with zero diagonal, and I need to guarantee that all the 2x2 blocks are full rank.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

This is maximal matching problem, solvable in polynomial time by Edmond's algorithm.

share|improve this answer
    
So, I have existing code to compute minimum weight perfect matchings. Can I adapt that for this purpose? –  Victor Liu Jan 2 '12 at 1:32
    
@Victor: If the code is for general graphs, yes (in fact it's exactly this problem), if only for bipartite ones, I suppose no. –  sdcvvc Jan 2 '12 at 1:36
    
It's for complete graphs. I guess for each edge, I set the weight to zero, and for non-existent edges, I set the weight to a very big number. –  Victor Liu Jan 2 '12 at 1:39
    
@Victor: Yes, in this case it's the same problem and you can also set the weight to 0 or to a big number. –  sdcvvc Jan 2 '12 at 1:42

What you want is a Hamiltonian path. Finding out whether they even exist for a given graph is NP-complete, so don't expect any smart algorithm to surface. The 30-vertex case might be solvable by brute force, though.

Edit: oops, didn't notice that it was only every other step in the sequence that had to align with an edge. In that case what you want is a minimum edge cover, or a perfect/near-perfect matching, which can be found in polynomial time -- see the linked Wikipedia article.

If you have an odd number of vertices, I suppose you can afford the last vertex in the ordering not to touch any specific edge; a completely naive approach to that would be to iterate through the vertices until you find one such that the graph minus that vertex can be coverered by $\frac{|V|-1}{2}$ edges.

share|improve this answer
    
I'm not sure if what I require is a Hamiltonian path since V[P[2]] does not need to be connected to V[P[3]]. –  Victor Liu Jan 2 '12 at 1:12
    
Ah, didn't notice that. Edited. –  Henning Makholm Jan 2 '12 at 1:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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