Question

classification_p_np
dominating_set
vertex_cover

עבור גרף לא מכוון G=(V,E)G = (V, E) נגדיר קבוצה שולטת כתת קבוצה של צמתים DVD \subseteq V כך שלכל צומת vVDv \in V \setminus D יש שכן ב- DD, כלומר קיים uDu \in D כך ש-(u,v)E(u, v) \in E. נזכיר כי כיסוי בצמתים של GG הוא קבוצהSVS \subseteq V כך שלכל קשת {u,v}E\{u,v\} \in E מתקיים {u,v}S\{u,v\} \cap S \neq \emptyset.

הערה: בשאלה זו ניתן להניח ש-GG קשיר.

  1. הוכיחו / הפריכו: אם SVS \subseteq V היא כיסוי בצמתים של GG אז היא קבוצה שולטת ב-GG.
  2. הוכיחו / הפריכו: אם DVD \subseteq V היא קבוצה שולטת ב-GG אז היא כיסוי בצמתים של GG.

בהנחה ש-PNPP \neq NP קבעו לכל אחת מהשפות הבאות אם היא ב-PP או שהיא NPNP-שלמה.

  • }\}יש ב-GG קבוצה שולטת בגודל V10|V| - 10L1={G:L_1 = \{G :
  • }\}יש ב GG קבוצה שולטת בגודל kk DS={(G,k):DS = \{(G, k) :
  • }\}יש ב GG קבוצה שולטת בגודל kk DSk={G:DS_k = \{G :
1

Answers

1. הטענה נכונה: נסתכל על צומת uS u \notin S, מכיוון שהגרף קשיר אז ל-uu יש שכן vv, מכיוון ש-SS כיסוי אז הקשת uvuv מכוסה, כלומר vSv \in S.

2. הטענה לא נכונה, למשל

אז {1,4}\{1, 4\} היא קבוצה שולטת אבל היא אינה כיסוי בצמתים.

3. נראה ש-L1PL_1 \in P זאת מכיוון שאפשר לנחש 10 צמתים שאינם בקבוצה השולטת ולבדוק ששאר הצמתים הם אכן קבוצה שולטת. ניתן לעשות זאת בזמן פולינומי.

4. נראה ש-L2NPCL_2 \in \text{NPC} על ידי רדוקציה מ-SC:

f(U,{S1,,Sm},k)=(G=(V,E),k)f(U, \{S_1,\ldots,S_m\}, k) = (G = (V, E), k)

כאשר

V=U{S1,,Sm}V = U \cup \{S_1,\ldots,S_m\}

ו-

E={(Si,Sj)}ij{(e,Si):eSi}E = \{(S_i, S_j)\}_{i \neq j} \cup \{(e, S_i) : e \in S_i\}

נניח בלי הגבלת הכלליות שלכל uUu \in U קיימת SiS_i כך ש-uSiu \in S_i וכן שכל קבוצה שולטת ב-GG היא תת קבוצה של {S1,,Sm}\{S_1, \ldots, S_m\}. נראה ש-C{S1,,Sm}C \subseteq \{S_1,\ldots,S_m\} בגודל kk היא כיסוי בקבוצות של UU אמ"מ CC היא קבוצה שולטת ב-GG .

אם uUu \in U אז מכיוון ש-CC כיסוי קיימת SiCS_i \in C כך ש-uSiu \in S_i כלומר (e,Si)E(e, S_i) \in E.

מצד שני אם uUu \in U אז מכיוון ש-CC קבוצה שולטת קיימת קשת (Si,u)E(S_i, u) \in E כך ש-SiCS_i \in C כלומר uSiu \in S_i.

0
Feedback