---
title: CSCI6212_HW8
tags: CSCI6212, Algorithm
---

<style>
.text-center{
text-align: center; //文字置中
}
.text-left{
text-align: left; //文字靠左
}
.text-right{
text-align: right; //文字靠右
}
</style>

<h1 class="text-center">CSCI 6212 - Homework 8</h1>
<h3 class="text-center">Chien-Huan Kao (G37556856)</h3>
<br>

1. (30 points) Given an undirected graph $G$, a subgraph $H \subseteq G$ is called an independent set of $G$ if for every pair of vertices $u, v \in V (H), (u, v) \notin E(G)$.

a) Design a backtracking algorithm to find an independent set of size $k$ (i.e., with $k$ vertices), if there is any, where $k$ is an arbitrary given integer, $1 \leq k \leq n$.

**Sol.**
Initial an empty set $S$.
For each vertex $v$ in $G$:
$\text{ } \text{ } \text{ } \text{ }$ if $S$ size is $k$, then return S.
$\text{ } \text{ } \text{ } \text{ }$ if $v$ is adjancent to any vertex in $S$,
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ }$ skip to the next vertex
$\text{ } \text{ } \text{ } \text{ }$ else add $v$ to the set $S$ and recursively call the algorithm with the new set $S$ and the remaining vertices in $G$.
return None

b) Design a branch-and-bound algorithm to find a maximum independent set of $G$ (i.e., an independent set with the maximum number of vertices).

**Sol.**
1. Initial an empty set $S$.
2. Let $UB(v)$ denote the upper bound on the size of the independent set that can be obtained by including a vertex $v$ in the set $S$. To calculate $UB(v)$, first add $v$ to $S$. Then, for every vertex $u$ adjacent to $v$, remove $u$ and all of its adjacent vertices from consideration. Repeat this process until no more vertices can be removed.
3. Choose a vertex $v$ with the highest upper bound $UB(v)$ and add it to $S$.
4. If $S$ contains all vertices in $G$, terminate the algorithm and return $S$.
5. Else for each vertex $u$ that is not in $S$ and is not adjacent to any vertex in $S$, create a new branch of the search tree by adding $u$ to $S$. Calculate the upper bound $UB(u)$ for the new set $S$ and add the branch to a priority queue sorted by decreasing upper bound. If the priority queue is empty, terminate the algorithm and return $S$.
6. Select the next branch from the priority queue, and repeat from step 3.

c) Now, assume that each node $v$ is assigned a positive weight $w(v)$. Design a branch-and-bound algorithm to find an independent set $S \subseteq G$ such that the sum of weights of vertices in $S$ is maximized. (We call such a subgraph a ***maximum-weighted independent set***.)
For example, consider a vertex-weighted graph $G$ and a subgraph $H \subseteq G$ shown in Figure 1. We then note that $H$ is a maximum-weighted independent set of $G$.

**Sol.**
1. Initialize a variable max_weight to 0 and a set $S$ to the empty set.
2. Create an initial node in the search tree with the current set $S$ and its weight sum $w(S)$.
3. If the current node represents a valid independent set, update max_weight to be the maximum of max_weight and $w(S)$.
4. If the current node represents a potential solution with a weight sum less than max_weight, prune this branch of the search tree.
5. Otherwise, for each vertex $v$ not in $S$, create a child node with $S \cup {v}$ as the set and $w(S) + w(v)$ as the weight sum. Add this child node to the search tree.
6. If there are no more nodes to explore, return max_weight and $S$.

2. (20 points) Consider the traveling salesperson instance shown in Figure 2. Apply the branch-and bound algorithm using the cost function discussed in the lecture slides 17-18 (7. Backtracking and Branch-and-Bound.pptx) to find a minimal tour. Show the full state space tree generated by the algorithm.

**Sol.**

The minimal tour is $1 \rightarrow 3 \rightarrow 4 \rightarrow 1$ which is 12.

3. (20 points)
a) Draw the comparison tree for sorting four elements.

**Sol.**

b) Is there a comparison-based sorting algorithm for sorting six elements in an arbitrary order using at most 9 comparisons in the worst case? Justify your answer.

**Sol.**
The possible orders for six elements are $6!=720$.
However, we can only get at most $2^9=512$ for 9 comparisons in the worst case.
512 is less than 720, so there is no a comparison-based sorting algorithm for sorting six elements in an arbitrary order using at most 9 comparisons in the worst case.

4. (30 points) Using the transformation algorithms discussed in class, do the following.
a) Let $w = (x_1 + x_3 + \bar{x_4} + x_5 + x_6 + \bar{x_8} + x_9 + x_{10})(x_2 + \bar{x_5})(\bar{x_7})(x_3 +x_8 +x_9 +x_{10})$ be an input to the Satisfiability problem. Construct an input $w'$ to the 3-Satisfiability problem such that $w$ is true *if and only if* $w'$ is true.

**Sol.**
$C_1=(x_1 + x_3 + \bar{x_4} + x_5 + x_6 + \bar{x_8} + x_9 + x_{10})$. Then $D_1=$
$(x_1+x_3+a_1)(\bar{a_1}+\bar{x_4}+a_2)(\bar{a_2}+x_5+a_3)(\bar{a_3}+x_6+a_4)(\bar{a_4}+\bar{x_8}+a_5)(\bar{a_5}+x_9+x_{10})$
$C_2=(x_2+\bar{x_5})$. Then, $D_2=(x_2+\bar{x_5}+a_6)(x_2+\bar{x_5}+\bar{a_6})$.
$C_3=(\bar{x_7})$. Then, $D_3=(\bar{x_7}+a_7+a_8)(\bar{x_7}+a_7+\bar{a_8})(\bar{x_7}+\bar{a_7}+a_8)(\bar{x_7}+\bar{a_7}+\bar{a_8})$
$C_4=(x_3 +x_8 +x_9 +x_{10})$ Then, $D_4=(x_3+x_8+a_9)(\bar{a_9}+x_9+_{10})$

$w'$ defined as $w'=$
$(x_1+x_3+a_1)(\bar{a_1}+\bar{x_4}+a_2)(\bar{a_2}+x_5+a_3)(\bar{a_3}+x_6+a_4)(\bar{a_4}+\bar{x_8}+a_5)(\bar{a_5}+x_9+x_{10})$
$(x_2+\bar{x_5}+a_6)(x_2+\bar{x_5}+\bar{a_6})(\bar{x_7}+a_7+a_8)(\bar{x_7}+a_7+\bar{a_8})(\bar{x_7}+\bar{a_7}+a_8)(\bar{x_7}+\bar{a_7}+\bar{a_8})$
$(x_3+x_8+a_9)(\bar{a_9}+x_9+_{10})$

b) Consider graphs $G_1$ and $G_2$ shown in Figure 3. (i) Construct graph $G'_1$ such that $G_1$ is 3-colorable *if and only if* $G'_1$ is 4-colorable, and (ii) construct a graph $G'_2$ such that $G_2$ is 3-colorable *if and only if* $G'_2$ is 4-colorable.

**Sol.**
$G'_1:$


$G'_2:$


c) Consider graph $G$ shown in Figure 4. Construct graph $G'$ such that $G$ is 3-edge colorable *if and only if* $G'$ is 3-colorable (i.e., 3-vertex-coloarable).

**Sol.**
Black color pen is the graph.

d) Let $w = (x_1 + x_2 + \bar{x_3})(\bar{x_2} + x_3 + \bar{x_4})(x_2 + x_4 + \bar{x_5})(x_3 + \bar{x_4} + x_5)$ be an input to the 3-SAT where the number $n$ of variables is 5 and the number $m$ of clauses is 4. Construct a graph $G$ such that $w$ is true *if and only if* $G$ has a node cover of size $n + 2m$.

**Sol.**

e) Consider graph $G$ shown in Figure 5. Construct graph $G'$ such that $G$ has a Hamiltonian cycle *if and only if* $G'$ has a Hamiltonian path.

**Sol.**

f) Consider graph $G$ shown in Figure 6. Construct graph $G'$ such that $G$ has a clique of size 4 *if and only if* $G'$ has an independent set of size 4.

**Sol.**