我在 mathoverflow 但沒有運氣：
找到一個連通的2因子是$ NP $ -complete，因為它等於漢密爾頓循環問題。我對在立方圖中找到兩個頂點不相交的$（| V |/2）$ - 循環的復雜性感興趣。
我懷疑它是$ NP $ -complete，但我無法找到參考。另外，在平面立方二分圖中找到兩個具有相等基數的頂點不相交$（| V |/2）$ - 周期的復雜性是多少？是$ NP $ -complete？
提供參考是非常感謝的。 $ NP $ -completeness是指問題的決策版本。
我認為，正如評論中所述，問題是在立方圖中找到兩個周期長度為$ | V |/2 $的2因子。 這個問題是NP完全的：
1）立方圖中的HC是NP完全的。
2）以下問題HC'也是NP完全的：給定一個立方圖$ G $和一個邊緣$ e $ 在$ G $中，是否存在通過$ e $的哈密頓循環。我們可以將HC減少到它：給定一個圖$ G $，用一個三角形替換一個任意頂點（左手邊），另一個頂點（右邊）：
將此新圖表稱為$ G'$。 $ G'$是Hamiltonian iff $ G $。此外，如果$ G'$是哈密頓量，那麽對於任何紅色邊緣，存在包含該紅色邊緣的哈密頓循環。 （如果沒有中間的頂點，則每個哈密爾頓循環都包含兩個綠色邊緣，然後任何綠色邊緣可以被兩個紅色邊緣替換。）從HC減少到HC'將立方圖$ G $映射到$ G'$任何紅色的ege。
3）最後，我們將HC'減少到問題的問題。給定一個實例 $（G，e）$，我們創建$ G $的兩個副本，在每個副本中細分$ e $並連接兩個頂點，將兩個副本細分為新邊緣$ f $。此邊緣$ f $是新圖形中的橋梁。如果$ G $具有通過$ e $的哈密頓循環，則新圖形具有由兩個相同大小的循環組成的2因子。 相反，如果新圖形具有這樣的2因子，則它不能使用$ f $。因此，它分成兩個副本的兩個哈密頓循環。由於在這些副本中，頂點細分$ e $具有度數2，我們得到$ G $的哈密頓循環，其中包含$ e $。