Разбиение графа на узло-непересекающиеся циклы

Связанная проблема: Теорема Веблена утверждает, что «граф допускает разложение цикла тогда и только тогда, когда оно четное». Циклы являются ребрами непересекающимися, но не обязательно узлы непересекающимися. Другими словами, «множество ребер графа можно разбить на циклы тогда и только тогда, когда каждая вершина имеет четную степень».

Моя проблема: Интересно, кто-нибудь изучал разбиение графа на узло-непересекающиеся циклы. То есть разбить вершины графа G на V 1 , V 2 , ⋯ , V k , и каждый подграф, индуцированный V i, является гамильтоновым.$V$$G$$V_1, V_2, \cdots, V_k$$V_i$

NP-сложный или легкий?

Более связанная проблема: разбиение на треугольник является NP-полным. (Страница 68 из «Компьютеры и неразрешимость»)

Спасибо за ваш совет заранее. ^^

Разбиение на вершинно-непересекающиеся циклы - это то же самое, что 2-регулярный подграф, более известный как 2-фактор. Его можно найти (если он существует) за полиномиальное время с помощью алгоритма, основанного на сопоставлении. Например, смотрите эту ссылку .

ETA, ноябрь 2013: из комментариев ниже видно, что сокращение от источника, указанного выше, неверно. Однако утверждение о том, что проблема может быть сведена к идеальному сопоставлению, остается верным. Правильная редукция содержится в WT Tutte (1954), «Краткое доказательство теоремы о факторе для конечных графов», Canadian J. Math. 6: 347–352 .

Заменить каждую вершину со степенью d полным двудольным графом G v = K d $v$$d$ , и представьте каждое реброuvисходного графа ребром из одной вершины G u в одну вершину G v (на стороне двудольного раздела сdвершинами) таким образом, чтобы каждая вершина G v на той стороне двунаправленного шва есть ровно один такой инцидент с краем.$G_v=K_{d,\,d-2}$$uv$$G_u$$G_v$$d$$G_v$

Тогда идеальное соответствие в модифицированном графе должно соответствовать вершинам на их стороне двудольного раздела G v с d - 2 из d вершин на другой стороне, оставляя ровно две свободные вершины, которые должны быть сопоставлены с их соседи в других подграфах G u . Таким образом, идеальные соответствия модифицированного графа соответствуют 1-к-1 с покрытиями циклов исходного графа.$d-2$$G_v$$d-2$$d$$G_u$