SGT Sheet

Question 1

Determine if true or false:

1. $10^{15}n\in O(n)$: $\top$
2. $n^2\in O(n)$: $\perp$
3. $n^2\in O(n\log n)$: $\perp$
4. $n^2\in O(n{\log }^{2}n)$: $\perp$
5. $n\log n\in O(n^2)$: $\top$
6. $2^{2n+1}\in O(4^n)$: $\top$
7. $n^{\log \log n}\in O(n^{10})$: $\perp$

Question 2

1. COLOURING problem Input of graph $G=(V,E)$ and set of colours $C=\{c_1,\dots ,c_k\}$ and returns $\top$ if every vertex $v\in V$ can be assigned a colour from $C$ such that no two adjacent vertices share the same colour.
   • We have $k$ colours, for $n$ vertices. ($k^n$)
   • We have to check all edges, which takes $O(n^2)$.
2. VERTEX-COVER problem Given a graph $G=(V,E)$ and integer $k>2$, it returns $\top$ if there exists a subset $C\subseteq V$ of size $k$ such that every edge in $E$ is adjacent to some vertex $v\in V$. There are $n$ vertices, we have to select $k$ vertices, $\left(\begin{array}{c}n\\ k\end{array}\right)$ To check everything, would require $O(n^2)$.
3. GRAPH-ISO problem We get two graphs $G=(V_G,E_G)$ and $H=(V_H,E_H)$ and returns $\top$ if $H$ is Isomorphic to $G$. The simplest way to check isomorphism is to use brute force to generate and check mappings.
4. SUBGRAPH-ISO problem

Question 3

1. $F=(P\vee \neg Q\vee \neg S)\wedge (Q\vee \neg R)\wedge (R\vee S)$ $F$ is only satisfiable $⟺$ there is a clique of size $k=\text{number of clauses}=3$.

graph {
	layout=circo
 
	subgraph cluster0 {
		P, nQ, nS
	}
	
	subgraph cluster1 {
		Q, nR
	}
 
	subgraph cluster2 {
		R, S
	}
 
	P--Q,nR,R,S
	nQ--nR,R,S
	nS--Q,nR,R
 
	Q--R,S
	nR--S
}

There are two cliques: $P,Q,R$, $\neg R,\neg Q,S$ and $\neg S,Q,R$.

2. $F=(\neg P\vee Q\vee R)\wedge (P\vee \neg Q)\wedge (\neg Q\vee R)$ $F$ is only satifiable $⟺$ there is a clique of size $k=3$

graph {
	layout=circo
 
	subgraph cluster0 {
		nP, Q, R
	}
	
	subgraph cluster1 {
		P, nQ
	}
 
	subgraph cluster2 {
		nQ1, R1
	}
 
	nP--nQ,nQ1,R1
	Q--P,R1
	R--P,R1
 
	P--nQ1,R1
	nQ--nQ1,R1
}

Question 4

Given $F=(\neg P\vee R)\wedge (Q\vee R)\wedge (P\vee \neg Q)$, construct a graph $G_F$ such that $F$ is satisfiable $⟺$ $G_F$ contains a Hamiltonian cycle.

digraph {
	rankdir=LR
	node [label="" shape=circle]
	clause1, clause2, clause3 [shape=rectangle]
	clause1 [label="-P or R"]
	clause2 [label="Q or R"]
	clause3 [label="P or -Q"]
 
	# P
	subgraph clusterGadget0 {
		label="P"
		true0 [color=green]
		false0 [color=red]
		init0 [color=aqua]
 
		init0 -> true0, false0
		true0, false0 -> exit0
 
		# clause 1
		false0->mid0_0
		mid0_0->false0
		mid0_0->clause1
		mid0_0->mid0_1
		mid0_1->mid0_0
		clause1->mid0_1
		mid0_1->mid0_2
 
		# clause 3
		true0->mid0_3
		mid0_3->true0
		mid0_3->clause3
		mid0_3->mid0_2
		mid0_2->mid0_3
		clause3->mid0_2
		mid0_2->mid0_1
	}
 
	# Q
	subgraph clusterGadget1 {
		label="Q"
		true1 [color=green]
		false1 [color=red]
 
		init1 -> true1, false1
		true1, false1 -> exit1
 
		# clause 2
		true1->mid1_0
		mid1_0->true1
		mid1_0->clause2
		clause2->mid1_1
		mid1_0->mid1_1
		mid1_1->mid1_0
		mid1_1->mid1_2
 
		# clause 3
		false1->mid1_3
		mid1_3->false1
		mid1_3->clause3
		clause3->mid1_2
		mid1_2->mid1_3
		mid1_3->mid1_2
		mid1_2->mid1_1
	}
 
	# R
	subgraph clusterGadget2 {
		label="R"
		true2 [color=green]
		false2 [color=red]
 
		init2 -> true2, false2
		true2, false2 -> exit2
 
		# clause 1 (true)
		true2->mid2_0
		mid2_0->true2
		mid2_0->clause1
		clause1->mid2_1
		mid2_0->mid2_1
		mid2_1->mid2_0
		mid2_1->mid2_2
 
		# clause 2 (true)
		mid2_2->mid2_1
		mid2_2->clause2
		clause2->mid2_2
		mid2_2->mid2_3
		mid2_3->mid2_2
		mid2_3->false2
		false2->mid2_3
	}
 
	# link all gadgets
	exit0->init1
	exit1->init2
	exit2->init0
}

Question 5

Show SUBGRAPH-ISO is NP-hard by constructing the polynomial reductions.

SUBGRAPH-ISO takes in two graphs $G,H$ and returns true if $H$ is an isomorphic to a sub-graph of $G$.

1. CLIQUE ${\le }_p$ SUBGRAPH-ISO //
2. HAMILTONIAN ${\le }_p$ SUBGRAPH-ISO