2
For each segment extract the two endpoints (remembering which segment they came from), now sort the endpoints by (say) lexicographical ordering. Any two endpoints that are the same are now adjacent. so, scan the sorted list, attache adjacent segments that share endpoints, and then read the cycle by following the resulting list like structure among the ...
1
Since it is asymptotic approximation and epsilon is a constant, for OPT big enough being 1 off is always good.
Let's put it another way. Either your optimal is smaller than 1/epsilon and you can find it within polynomial time. Or it is not and thus 1+1/OPT is better than 1+epsilon.
1
There is a polynomial time algorithm for this problem.
First, as pointed out by D.W., by Hall's theorem we can assume that there is a perfect matching between $A$ and $B$.
In particular, if there is no perfect matching then there is a subset $S$ with $|S| > |N(S)|$, and we can remove vertices from $S$ without affecting $N(S)$ until we get an answer.
Now ...
1
I know it is an older question but this research paper has a relatively straight forward O(m^(3/2)) algorithm for incrementally maintaining them: https://arxiv.org/pdf/1105.2397.pdf
Here is one with O(m) algorithm for decrementally maintaining them: https://arxiv.org/pdf/1901.03615.pdf (from 2019 and it improves on the O(m*sqrt(n)) algorithm of https://u.cs....
Only top voted, non community-wiki answers of a minimum length are eligible
