We can illustrate this idea of reducibility by introducing another problem on social networks
that we'll call the S independent set problem and the problem goes like this.
Given the graph H and a number S, is there a set of nodes of size S, the set is a size S not the nodes,
in H such that node to node in the set are connected in the original graph H.
In some sense, they're independent of each other.
You can think of this as the find the strangers problem.
So they need to be in the social network together but none of them know each other.
So for example, if we look in this graph H for an independent set size of three,
We noticed that there is at least this triple, this set of nodes where none of the pairs know each other.
We can't make it any bigger than this at least including those three nodes
because every other nodes that we didn't include is connected to at least one of these guys.
I think this is probably the biggest independent set in this graph.
All right, so now what we're going to try to do is reduce this problem to K-clique
or more concretely show how a polynomial time solution
to K-clique solves the S-independent set problem.
So here's four approaches that we might be able to use to solve this problem.
One is first note that the S-independent set problem can be solved by guessing a set of nodes,
and then making sure that none of the pairs of nodes in that set are connected.
All you have to do is check SÂ˛ edges or big Î of SÂ˛ edges so this runs in polynomial time.
Here's another possibility. Let's actually take the graph H and run the S-clique algorithm on it.
That is to say the K-clique algorithm that we use when looking for a clique of size S,
and whatever it returns, return the opposite of the answer.
The idea being that if a graph has a very big clique in it, there's lot of nodes
that are densely connected, then it's unlikely to have a large independent set.
All right, here's another approach.
Let's take the graph H and build a new graph G that is the complement of H.
That is to say every place there's an edge in H.
There's no edge in G. Every place there's no edge in H. There is an edge in G.
Then we run the S-clique algorithm that the K-clique algorithm looking for a clique of size S
on this new graph G and whatever answer it gives just return the opposite.
So if it says that there's an S-clique in G return false
and if it says there's no S-clique in G then return true.
And this last option is the reverse of that, so you build the complement graph.
You look for a size S-clique in that graph and if there is one say yes and if there isn't one say no.
So think about these a little bit.
Maybe even sketch an example problem for yourself to see which of these makes sense.
हम सामाजिक नेटवर्क पर एक और समस्या शुरू करने से इस विचार reducibility का वर्णन कर सकते हैं
कि हम स्वतंत्र S फोन करता हूँ समस्या सेट करें और समस्या इस तरह चला जाता है।
ग्राफ H और एक नंबर दिया S, वहाँ आकार S के नोड्स का एक सेट, सेट S नहीं नोड्स का एक आकार है,
कि इस तरह के मूल में सेट कर रहे हैं में नोड के लिए नोड से जुड़े में एच एच. ग्राफ
कुछ मायने में, वे एक दूसरे से स्वतंत्र हैं।
आप के इस अजनबी समस्या ढूँढना के रूप में सोच सकते हैं।
तो वे सामाजिक नेटवर्क में एक साथ किया जा करने के लिए की जरूरत है लेकिन उनमें से कोई भी एक दूसरे को जानते।
तो उदाहरण के लिए, H के लिए तीन में से एक स्वतंत्र सेट आकार ग्राफ़ करें अगर हम इस में देखो,
हमने पाया है कि वहाँ कम से कम इस ट्रिपल है, यह नोड्स के जोड़े में से कोई भी कहाँ पता एक दूसरे सेट है।
हम इसे कम से कम उन तीन नोड्स सहित इस की तुलना किसी भी बड़ा नहीं कर सकता
क्योंकि हर अन्य नोड्स कि हम शामिल नहीं था करने के लिए जुड़ा हुआ है, इन में से कम से कम एक दोस्तों।
मुझे लगता है कि यह शायद सबसे बड़ा स्वतंत्र इस ग्राफ में सेट है।
सब ठीक है, तो अब क्या हम करने की कोशिश जा रहे हैं K-गुट के लिए इस समस्या को कम है
या अधिक concretely दिखाने के कैसे एक बहुपद समय समाधान
K-गुट के लिए S-स्वतंत्र सेट समस्या हल करती है।
तो यहाँ है चार दृष्टिकोण है कि हम इस समस्या को हल करने के लिए उपयोग करने में सक्षम हो सकता है।
सबसे पहले ध्यान दें कि S-स्वतंत्र सेट समस्या नोड्स का एक सेट अनुमान लगाने के द्वारा हल किया जा सकता है,
और तब सुनिश्चित करें कि उस सेट में नोड्स के जोड़े में से कोई भी जुड़े हुए हैं।
सब तुम्हें क्या करना है है चेक SÂ˛ किनारों या बड़ा मैं के SÂ˛ किनारों तो इस में बहुपद बार चलाया जाता है।
यहाँ एक और संभावना है। हम वास्तव में ग्राफ H ले और S-गुट एल्गोरिथ्म पर चला।
यह कहना है K-गुट एल्गोरिथ्म, कि हम का उपयोग करें जब S के आकार का एक गुट के लिए देख
और जो कुछ भी है तो यह, जवाब के विपरीत लौटें।
किया जा रहा है कि अगर एक ग्राफ में एक बहुत बड़ा गुट है, वहाँ बहुत कुछ नोड्स के विचार
तो यह एक बड़ी स्वतंत्र निर्धारित किया है की संभावना नहीं है कि घनी, कनेक्टेड हैं।
सब ठीक है, यहाँ एक और तरीका है।
चलो ग्राफ H ले और एक नए ग्राफ जी कि एच. के पूरक हैं है का निर्माण
यह कहना है हर जगह वहाँ एच. में एक किनारे है
जी में कोई धार है हर जगह वहाँ है कोई एज में एच. जी में एक किनारे है
तो हम कि K-गुट एल्गोरिथ्म S के आकार का एक गुट के लिए देख S-गुट कलन विधि चलाएँ
इस नए ग्राफ जी और जो भी इसे देता है सिर्फ जवाब पर विपरीत लौटें।
अगर यह कहता है कि जी में एक S-गुट तो झूठी वापसी
और अगर यह कहते हैं, जी में कोई S-गुट है तो सच वापसी।
और यह पिछले विकल्प कि, के विपरीत है, तो आप पूरक ग्राफ़ निर्माण।
आप कि ग्राफ में एक आकार S-गुट के लिए देखो और अगर वहाँ एक है हाँ और नहीं है नहीं अगर एक कहते हैं कहते हैं।
तो इन के बारे में एक छोटा सा लगता है।
शायद भी अपने आप को देखना है जो ये समझ में आता है के लिए एक उदाहरण समस्या स्केच।
ソーシャルネットワークを例に取り 還元可能性の概念を勉強しましょう
これを独立s点集合問題と呼びます
グラフHと数字のsそしてsサイズのノードがあります
Hではどのノードも接続しておらず
ある意味お互いが独立した存在です
これを見知らぬ者の間の問題として 捉えることができます
彼らはソーシャルネットワークでつながっていても お互いのことは誰も知りません
例えばこのグラフHで言えば 独立点集合のサイズは3です
少なくともこの3つは お互いのことを知らないノードになります
すでにノードが3つなので これ以上は大きくなり得ません
なぜなら他のノードは3つのうちのどれかと つながっているからです
このグラフでは最大の独立点集合になります
次にこの問題をkクリーク問題に還元します
つまりkクリーク問題の解法を用いて
多項式時間で独立s点集合問題を解くかを示します
利用できそうなアプローチが4つあります
1つ目は独立s点集合問題の最初のノードから 一連のノードを推測します
この集合のペアノードはどれもつながっていません
ただsの2乗個のエッジさえ確認できればよいので 多項式時間で実行できます
2つ目の方法はsクリークアルゴリズムを グラフHで実行します
kクリークアルゴリズムは サイズsのクリークを求める際に使用します
それが何を返しても逆の答えを返してください
もしグラフに大きなクリークがあれば ノードも多数あります
ノードは密接につながっているため 1つの大きな独立点集合とはなり得ません
3つ目のアプローチですが
グラフHを補完するために新しいグラフGを作ります
Hでエッジがある場所にはGにはなく
Gでエッジがある場所にはHにはありません
sクリークアルゴリズムを実行します kクリークアルゴリズムはサイズsのクリークを求めます
答えは何になろうとも反対になります
つまりG上でsクリークが存在すれば 答えは偽になります
G上でsクリークが存在しなければ 答えは真になります
最後のアプローチ法は今の逆です 補完グラフを立てて
sクリークを求め1があればイエス なければノーです
これらを解いてみてください
例題の概略だけでも答えが導けるかもしれません