Czy jest coś znanego na temat następującego problemu? Czy to w ogóle ma sens? Jak to jest nazywane? Czy jest to banalnie równoważne z jakimś innym problemem? Jaka jest złożoność czasu?
Biorąc pod uwagę nieukierowany (ogólny / płaski / ograniczony / itd.) Wykres G = (V, E), znajdź maksymalny podzbiór krawędzi E ', tak że G' = (V, E-E ') jest podłączony i dla każda krawędź e w E 'ma cykl nieparzystej długości w G zawierający e, który nie zawiera żadnej innej krawędzi w E'. (Rozważam tylko cykle proste, tzn. Dwa razy nie pojawia się wierzchołek)
Wydaje się to podobne do dzielenia na dwie części, ale wyniki, które tam widziałem, dotyczą minimalnej liczby wierzchołków / krawędzi, które należy usunąć, natomiast chcę maksymalnej liczby krawędzi, które można usunąć.
Na przykład następujący wykres:
* - * - *
/ \
* - * - * - *
\ /
* - * - *
Możemy wyciąć jedną z krawędzi ścieżki na środku, usuwając w ten sposób wszystkie nieparzyste cykle. Możemy jednak zrobić to lepiej, usuwając dwie krawędzie, jedną w górnej gałęzi i jedną w dolnej.