Сложность нахождения максимального взвешенного джойна в графе

Подмножество ребер $J\subseteq E(G)$ в неориентированном графе $G$ называют джойном, если не более половины ребер каждого цикла графа $G$ содержится в $J$. Рассмотрена задача нахождения джойна максимального веса: при заданных графе $G$ и реберном взвешивании $c:E(G)\to\mathbf R$ найти джойн максимального веса. Показано, что данная задача является NP-трудной в случае произвольных графов и 0,1-весов. Установлено также, что в случае последовательно-параллельных графов и произвольных весов рассматриваемая задача может быть решена за время $O(n^3)$, где $n$ –число вершин в графе.
Библиогр. 7.