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

Question

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.

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.