一千萬個為什麽

搜索

兩個最大平面圖的最大公共子圖

考慮以下問題 -

給定最大平面圖$ G_1 $和$ G_2 $,找到具有最大邊數的圖形$ G $,使得$ G_1 $和$ G_2 $中的子圖(不一定是誘導的)與$ G $同構。

這可以在多項式時間內完成嗎?如果是,那怎麽樣?

眾所周知,如果$ G_1 $和$ G_2 $是一般圖表,那麽問題就是NP完全(因為$ G_1 $可能是一個集團)。眾所周知,如果$ G_1 $和$ G_2 $是樹,或有界度的部分k樹,那麽問題可以在多項式時間內解決。那麽最大平面情況呢?有誰知道這個?兩個最大平面圖上的圖同構是多項式的。也許這會有所幫助嗎?

最佳答案

它是NP完全的,通過Wigderson的修正版本用來證明最大平面圖的哈密爾頓性是NP完全的。

仔細檢查Wigderson 1982年最大平面圖中哈密頓循環硬度的NP-完整性證明( http://www.math,http://www.math .ias.edu/avi/node/820 )顯示由他減少產生的實例具有存在邊緣$ e $的屬性,使得存在通過$ e $的哈密頓循環或者沒有完全存在任何哈密頓循環。例如,可以選擇$ e $作為Wigderson的$ M $ -gadgets之一的邊緣之一。

讓$ G $成為以這種方式構造的硬實例,並嵌入$ G $,以便邊緣$ e $屬於嵌入的外三角形。連接這個嵌入圖形的許多副本,使它們的$ e $ -edges形成一個循環,並通過再添加兩個頂點使結果最大化為平面,每個頂點在此循環的每一側,連接到副本的所有暴露頂點。 $ G $。讓副本數為$ c $,並將結果圖調用$ H $。設$ n $是$ G $中的頂點數。

我們對最大公共子圖的硬實例將是$(H,B)$對,其中$ B $是一個雙金字塔,其頂點數與$ H $相同。因此,最佳公共子圖必須配對所有頂點。如果我們使$ c $足夠大,子圖必然會將雙錐體的頂點與$ H $中的兩個添加頂點配對,因為它們的度數($ c $和$ 2c $)將足夠高於其他每個頂點。 $ H $,因此將這些度數添加到解決方案大小將彌補其他地方因此配對而造成的任何中斷。

如果$ G $是哈密頓量,那麽通過將$ G $的副本中的哈密頓循環(減$ e $)與雙錐體的赤道相匹配而形成的公共子圖將具有$ c(n + 2)$邊緣,$ c (n-1)赤道為$,頂點為$ 3c $。如果$ G $不是哈密頓量,那麽(對於$ c $的足夠大的選擇,最佳解決方案正確配對頂點)任何常見的子圖將具有更少的邊緣:仍然在頂點處$ 3c $但是少於$ c(n- 1)$其他地方。因此,測試$ H $和$ B $的公共子圖是否具有至少$ c(n + 2)$邊緣是NP完全的。

轉載註明原文: 兩個最大平面圖的最大公共子圖