---
# System prepended metadata

title: CSCI6212_HW8
tags: [' Algorithm', CSCI6212]

---

---
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$.
   ![](https://i.imgur.com/GC0mqVz.jpg)
   
   **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.
   ![](https://i.imgur.com/L4O8hiD.jpg)
   
   **Sol.**
   ![](https://i.imgur.com/fQL874c.jpg)
   
   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.**
   ![](https://i.imgur.com/VCJV7Ci.jpg)

   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.
   ![](https://i.imgur.com/wiV5yCw.jpg)

    **Sol.**
    $G'_1:$
    
    ![](https://i.imgur.com/KQwNoiX.jpg)
    
    $G'_2:$
    
    ![](https://i.imgur.com/TRZDKMN.jpg)
    
   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).
   ![](https://i.imgur.com/1A72CdX.jpg)
   
   **Sol.**
   Black color pen is the graph.
   ![](https://i.imgur.com/QYXydgD.jpg)
   
   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.**
   ![](https://i.imgur.com/tm2OKU8.jpg)

   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.
   ![](https://i.imgur.com/UkEDWWd.jpg)
   
   **Sol.**
   ![](https://i.imgur.com/9d5i3tX.jpg)
   
   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.
   ![](https://i.imgur.com/MeEFvR5.jpg)
   
   **Sol.**
   ![](https://i.imgur.com/EARqamA.png)
