「（1：k）樹匹配」 - 多項式時間可解？

Question

幾個月前，有關於一個nice question「1：N匹配問題」而且似乎沒有多時間的算法。

我想補充的限制以找到1的最大匹配：N用多項式算法的匹配問題。我想說的是：「對於頂點A1，如果頂點尚未從另一個頂點取出，則選擇{B1，B2，B5}或{B2，B3}」，即我不允許所有可能的組合。如果我們每個選擇和替代的邊緣樹木引進幫手頂點^ h

這可以表達=>我們得到類似於普通的二分匹配問題。 A或B的每個頂點在匹配中只能有一條邊。 H中的頂點的邊或者全部在匹配中，或者它們中沒有一個出現在匹配中。想象以下三方圖表：

現在定義h_ij = 「樹根包含H_ij」 容易地表達匹配：

• 然後，在例如M = {H12，H22 }將是一個「最大」匹配，儘管不是所有來自B的頂點都涉及
• 集合{h12，h23}不是匹配的，因爲B3將被選擇兩次。

請問這個問題則是在多項式時間內可解？如果是，是否有加權（w（h_ij））變體的多時間解決方案？如果不是，你是否可以爲像我這樣的「簡單人」爭辯或者證明它，或者提出其他約束來解決1：n匹配問題？

E.g.該圖可以轉化爲一般圖，然後用一般圖的加權匹配來解決？或者可以在這裏幫助branchings甚至matching forests？

PS：不是功課;-)

Answer 1

有最大和最大之間的差。我認爲你的意思是最大限度地爲下面的寫作。

你似乎沒有很清楚地定義你的問題，但如果我已經正確理解你的意圖，看起來你的問題是NP完全（和'等同於Set Packing）。

我們可以假設所允許的一組尺寸是相同的（k）的所有A_I找到一個[1：k]的匹配，如任何其他集合大小可以忽略不計。爲了找到最大值K，我們只是運行算法[1：K]對於k = 1,2,3 ...等

所以你的問題是（我想...）：

令M設置家庭F_i = {S_1i, .., S_n(i)i}（| F_i | = F_i = N（I）的大小，不一定是一樣| F_j |），每組大小爲k的，你必須要找到從每個家庭一組（比如說S_I），使得

• S_i和S_j對任何i neq j都是不相交的。
• S_i的數量是最大的。

我們可以證明，它是一個NP完全對於k = 3在兩個步驟：

1. 的NP完全問題Set Packing可以減少它。這表明它是NP-Hard。
2. 你的問題是在NP中，可以減少到設置包裝。這和1）意味着你的問題是NP-Complete。它還可以幫助您利用任何現有的用於Set-Packing的近似/隨機算法。

包裝方式的問題是：

鑑於N套S_1，S_2，...，S_N，發現中這些兩兩不相交集的最大數量。

這個問題仍然是NP-Complete，即使| S_1 | = | S_2 | = ... = | S_n | = 3，被稱爲三組裝箱問題。

我們將用這個來表明你的問題是NP-Hard，通過從3-Set包裝到你的問題提供一個簡單的減少。

鑑於S_1，S_2，...，S_N剛形成家庭

F_i = {} S_I。

現在，如果你的問題有一個多項式時間的解決方案，那麼我們得到了一組集{S_1，S_2，...，S_R}這樣

• S_I和S_j是不相交的
• 的數S_i是最大值。

這個簡單的減少給我們一個解決方案，三套裝問題，因此你的問題是NP-Hard。

一看就知道這個問題是NP，我們降低它設置包裝說明如下：

鑑於F_i = {S_1i，S_2i，...，S_ni}

我們考慮套T_ji = S_ji U {i}（即我們將一個家族的id添加到該集合本身中）並通過Set-Packing算法運行它們。我會留給你看看爲什麼Set-Packing解決方案爲你的問題提供瞭解決方案。

---

對於最大解決方案，所有你需要的是一個貪心算法。只要繼續挑選，直到你不能再挑選。這將是多項式時間。