Week 17

Click to Open TOC

• Week 17
• Question
• Answer
  • Q1
    • 【解題思路】
    • 找Assignment
  • Q2
  • Q3
  • Q4

Question

Click to Open Question

Check

• Q1
• Q2
• Q3
• Q4

Answer

Q1

• LXS

題目

Let 2-CNF-SAT be the set of satisfiable Boolean formula in CNF with exactly 2 literals per clause. Show that 2-CNF-SAT ∈ P. Make your algorithm as efficient as possible. (Hint: Observe that x ∨ y is equivalent to ¬x → y. Reduce 2-CNF-SAT to an efficiently solvable problem on a directed graph.)

【解題思路】

將一個Boolean formula，其中有n個Boolean variable、m個calause，轉成一個directed graph，每個Boolean variable，

$x_1,...,x_n$對應圖中點

$x_1,\mathrm{\neg }{x}_1,...,x_n,\mathrm{\neg }{x}_n$ 共2n個點，每個calause

$x\vee y$相當於

$\mathrm{\neg }x\to y\wedge \mathrm{\neg }y\to x$，對於圖中我們也連接

$\mathrm{\neg }x\to y$與

$\mathrm{\neg }y\to x$共個點共2m個邊。

首先找strongly connected components，需要

$O(n)$時間，然後確保每個

$x_k$與

$\mathrm{\neg }{x}_k$不在同一個SCC(不能存在

$x_k\to ...\to \mathrm{\neg }{x}_k$，

$\mathrm{\neg }{x}_k\to ...\to x_k$)，需要

$O(n)$，如果在同一個S CC則該Boolean formula是Unsatisfiable的。

我們可以在多項式時間內決定2-CNF-SAT問題，因此2-CNF-SAT ∈ P.

找Assignment

假如我們把每個SCC視為一個點(同一個SCC塗同樣顏色)稱作

$G$，將每個點之間的邊的方向相反，稱作

$G^T$，在

$G^T$中，依照從原本

$G$的Sink開始按照拓撲排序填色，相連的兩個SCC中填入相反的顏色，否則填入相同顏色，將同Sink顏色的點設為true即可以找到assignment。

Q2

• xian

【題目】

The subgraph-isomorphism problem takes two undirected graphs G1 and G2, and it asks whether G1 is isomorphic to a subgraph of G2. Show that the subgraph-isomorphism problem is NP-complete.

【證明】

證明

$SIP\in NP\to \mathrm{驗}\mathrm{證}\in P$

• 假設我們有G1和G2的子圖G，從上禮拜作業已證明 GRAPH-ISOMORPHISM
  $\in NP$，證明同構需要驗證以下四項：
  1. Equal number of vertices.
  2. Equal number of edges
  3. Same degree sequence
  4. Same number of circuit of particular length
• 而這些都可以在
  $P$ 時間內驗證
• 因此
  $SIP\in NP$

證明

$SIP\in \text{NP-hard}\Rightarrow \text{CLIQUE}{\le }_{p}SIP$

• $\mathrm{對}\mathrm{於}\text{CLIQUE}\mathrm{問}\mathrm{題}\mathrm{給}\mathrm{定}\mathrm{一}\mathrm{張}\mathrm{圖}{G}_2，\mathrm{另}\mathrm{外}\mathrm{生}\mathrm{成}\mathrm{一}\mathrm{圖}{G}_1，\mathrm{令}{G}_1=K_i，|G_1|=i\mathrm{的}\mathrm{完}\mathrm{全}\mathrm{圖}，i\le |G_2|$，問
  $G_2$是否存在一個大小為
  $k$ 的完全子圖(cliqu)
  $G$
• $\mathrm{如}\mathrm{果}{G}_2\mathrm{存}\mathrm{在}\mathrm{大}\mathrm{小}\mathrm{為}i\mathrm{的}\text{CLIQUE}，\mathrm{則}{G}_1\mathrm{為}{G}_2\mathrm{的}\mathrm{子}\mathrm{圖}$
• 因此將
  $G_1、G_2$ 丟入
  $SIP$ 中，確認
  $G_1$ 是否和
  $G_2\mathrm{的}\mathrm{子}\mathrm{圖}$同構
• 如果同構則回答true，不同構則回答false

$\because \mathrm{生}\mathrm{成}{G}_1\mathrm{最}\mathrm{多}\mathrm{只}\mathrm{需}O(|G_1{|}^2)，\mathrm{因}\mathrm{此}\mathrm{轉}\mathrm{換}\mathrm{時}\mathrm{間}\mathrm{為}\mathrm{指}\mathrm{數}\mathrm{時}\mathrm{間}$

$\therefore \text{CLIQUE}$在指數時間下可解，則

$SIP$也可
且我們已知

$\text{CLIQUE}\in \text{NP-hard}\wedge SIP\in NP⟹SIP\in \text{NP-hard}$

又因為

$SIP\in \text{NP-hard}\wedge NP$

$\therefore \mathbf{S}\mathbf{I}\mathbf{P}\in {\mathbf{\text{NP-complete}}}_{\mathbf{\#}}$

Q3

• chung

【題目】

Given an integer m x n matrix A, and an integer m-vector b, the 0-1 integer-programming problem asks whether there exists an integer n-vector x with elements in the set {0, 1} such that Ax ≤ b. Prove that 0-1 integer programming problem is NP-complete. (Hint: Reduce from 3-CNF-SAT.)

【證明】

• Problem ∈ NP : Find a certificate to verify that it is the correct answer to this question.

  • A certificate would be the n-vector x, and we can verify in polynomial time that Ax ≤ b, so 0-1 integer linear programming (01LP) is in NP.

• Problem ∈ NP-hard : 3-CNF-SAT

  ${\le }_{𝑝}$ 0-1 integer- programming problem
  • 3-CNF-SAT
    
    $Ex:({𝑥}_1\vee {𝑥}_2\vee {𝑥}_3)\wedge ({𝑥}_1\vee \neg {𝑥}_3\vee \neg {𝑥}_4)$
    If
    ${𝑥}_{𝑗}$ in clause i with negation →
    ${𝐴}_{(}𝑖,𝑗)=1$
    If
    ${𝑥}_{𝑗}$ in clause i without negation →
    ${𝐴}_{(}𝑖,𝑗)=-1$
    Other,
    ${𝐴}_{(}𝑖,𝑗)=0$
    
    ${𝑏}_{𝑖}$ = – 1 + num of negation in clause i
    
    $$\begin{gathered} ({𝑥}_1\vee {𝑥}_2\vee {𝑥}_3):{𝑥}_1+{𝑥}_2+{𝑥}_3\ge 1\Rightarrow -{𝑥}_1-{𝑥}_2-{𝑥}_3\le -1 \\ ({𝑥}_1\vee \neg {𝑥}_3\vee \neg {𝑥}_4):{𝑥}_1+(1-{𝑥}_3)+(1-{𝑥}_4)\ge 1\Rightarrow -{𝑥}_1+{𝑥}_3+{𝑥}_4\le 1 \\ Ax\le b:\left[\begin{array}{cccc}-1& -1& -1& 0\\ -1& 0& 1& 1\end{array}\right]𝜒\le \left[\begin{array}{c}-1\\ 1\end{array}\right] \end{gathered}$$
    轉換時間在 polynomial time 內，其又為 NP Problem，故得證 0-1 integer- programming problem is NP-complete.

Q4

• yee

【題目】

Based on hw14-7,we know that longest-simple-cycle problem is an NP-problem.
Prove that the problem is NP-complete

【解題思路】
由14-7我們知道LSC為NP問題，

$\text{certificate}$依序為

$v_1,v_2,v_3,...,v_k$，且已知Hami-cycle 為NP-complete問題，因此可由Hami-cycle reduce to LSC 來證明LSC也是NP-complete問題。

【證明】

$Hami-cycle<{=}_{p}LSC$

若一Graph存在一個Hami-cycle也代表該Graph存在一k = |V|的LSC，若一Graph存在一序列

$v_1,v_2,v_3,...,v_n(n=|V|)$的LSC，也代表該Graph也存在一Hami-cycle，因此可知Hami-cycle\ \ iff.\ LSC

$\therefore \mathbf{L}\mathbf{S}\mathbf{C}\in {\mathbf{\text{NP-complete}}}_{\mathbf{\#}}$