# A problem to maximize the number of edges in a cycle while minimizing the total weight

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.

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.