I encountered the problem below and the only solution I came up with is branch and bound like that is used in TSP and I don’t think the bound I used is good enough. Are there any better idea on this?

Consider a graph $G$ that consists of an undirected bipartite graph and another vertex $O$ that is connected to all the other vertices. Assume the weight of the edges are positive and the weights obey the triangle inequality. Find a cycle in $G$ that involves $O$ s.t. the total weight is $\leq$ some given value $t$ and maximize the total number of vertices it passes through.


1 Answer 1


This is NP-complete, since an instance $(V,E)$ of the NP-complete problem Hamiltonian Path can be reduced to it: Turn each vertex in the original HP instance into a pair of vertices $a_i, b_i$ connected by a low-weight edge, with one vertex in each part of the bipartite graph, and add a high-weight edge $a_ib_j$ for each edge $v_iv_j$ in the original graph. Finally add $O$. Solve your instance and delete $O$: the original graph has a HP iff $2|V|−1$ edges remain.

All this is to say there is almost certainly no polynomial-time algorithm to solve your problem (since if there was, Hamiltonian Path, and every other NP-complete problem could also be solved in polynomial time). Adapting an algorithm for solving TSP sounds reasonable to me.


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.