一千萬個為什麽

搜索

在立方圖中找到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 $。

轉載註明原文: 在立方圖中找到2個頂點不相交$(| V |/2)$ - 周期的復雜性?