在立方圖中找到2個頂點不相交$（| V |/2）$ - 周期的復雜性？
我在 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 $，用一個三角形替換一個任意頂點（左手邊），另一個頂點（右邊）：
!enter image description here
將此新圖表稱為$ 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 $。
在特定實驗室工作的機會很多，但您需要與經營個別實驗室或研究小組的教授開始對話，以了解您學校的可用資料。您是否可以獲得某個職位的資金將因實驗室/
RG而異。在數學或理論計算機科學研究實驗室獲得資助職位通常更加困難，因為沒有經驗，你沒有太多可以證明獲得報酬的理由（而在實驗室裏，你至少可以幫助你獲得報酬）實驗室固有的工作）。
我的建議：預約在實驗室或小組中看教授或實驗室主任。你可以免費工作至少一年，以證明自己的價值。如果這意味著在其他地方從事第二份工作，那就這樣吧。準備好討論為什麽你認為你會讓一個有價值的團隊成員參與討論你的長期目標。這應該不僅僅是“我可能想在理論計算機科學領域工作”。對實驗室最近發表的論文做一些預讀，並對教授的背景有所了解。
不幸的是，跳入理論研究小組可能不是測試某個特定領域水域的最佳方式（尤其是沒有良好背景的水域），因此您可能更有價值繼續學習這些學科的課程很有趣，並且自己做了很多閱讀。