Advanced Algorithms End Term: 1 September 2024, Set QDB1 (May 2024 term)

In this problem you are given as input a graph $T = (V, E)$ that is a tree (that is, $T$ is undirected, connected, and acyclic). A perfect matching of $T$ is a subset $F \subset E$ of edges such that every vertex $v \in V$ is the endpoint of exactly one edge of $F$.

Equivalently, $F$ matches each vertex of $T$ with exactly one other vertex of $T$. For example, a path graph has a perfect matching if and only if it has an even number of vertices.

Consider the following two algorithms that attempt to decide whether or not a given tree has a perfect matching. The degree of a vertex in a graph is the number of edges incident to it.

Algorithm A:

Algorithm B:

Is either algorithm correct?

Hint: Recall that every tree with at least two vertices has at least one degree one vertex.

Which of the following statements is true?
Statement 1: For every graph G and every maximum flow on G, there always exists an edge such that increasing the capacity on that edge will increase the maximum flow that’s possible in the graph.
Statement 2: Suppose the maximum (s,t)-flow of some graph has value f. Now we increase the capacity of every edge by 1. Then the maximum (s,t)-flow in this modified graph will have value at most f + 1.

Recall the max-flow problem: for a directed graph $G(V, E)$ with non-negative capacities $c_e$ for every $e \in E$ and two special vertices $s$ (source, with no incoming edges) and $t$ (sink, with no outgoing edges), a flow in $G$ is an assignment $f : E \rightarrow \mathbb{R}_{\geq 0}$ such that $f_e \leq c_e$ for every edge and for every vertex $v \in V, \sum_{(u,v) \in E} f((u,v)) = \sum_{(u,v) \in E} f((v,u))$. The task is to find a maximum flow $f$ i.e., a flow $f$ such that $\sum_{(s,u) \in E} f((s,u))$ is maximized.

Given an instance $(G; s, t, c)$, we attempt here to design a LP whose optimal value is equal to the maximum flow in the graph $G$. There is a variable $x_{uv}$ for all $(u, v) \in E$. Note that for any pair of vertices that is not an edge, we do not introduce any variable corresponding to it.

$\begin{aligned} &\max \sum_u x_{ut} \\ &\forall e = (u,v) \in E, x_{uv} \leqslant c_e \\ &\forall v \notin \{s,t\}, \sum_u x_{uv} = \sum_w x_{vw} \\ &\forall e = (u,v) \in E, x_{uv} \geqslant 0 \end{aligned}$

Is the LP above a valid formulation for computing the maximum flow in $G$?

A subset S of vertices in an undirected graph G is half-independent if each vertex in S is adjacent to at most one other vertex in S. Is it true that finding the size of the largest half-independent set of vertices in a given undirected graph is NP-hard?

Can the disk with dimensions [2,1,2] be placed above [3,2,3]?

Can the disk with dimensions [2,2,2] be placed above [3,2,3]?

Suppose the input consists of the following triplets: [[3, 5, 7], [3, 2, 2], [3, 1, 1], [5, 5, 9]]. What’s the answer?

Our approach will be to building a DP table of the same length as the array of disks. Let $d_i$ denote the $i^{th}$ disk in the input array.

The value of $\text{DP}[i]$ will be the height of the tallest tower that can be created with $d_i$ the bottom. We initialize the value of $\text{DP}[i]$ the height of $d_i$.

Consider the following approach. We process the DP array in increasing order of indices (i.e, $i = 1$ to $i = N$). We look at all disks $d_j$ where $j < i$ and $d_j$ can be placed on top of $d_i$. If $d_j$ can be placed on top of $d_i$, then $\text{DP}[i]$ is updated to be the maximum of $\text{DP}[i]$ and $\text{DP}[j] + H$, where $H$ is the height of the disk $d_i$. What can you say about this approach?

With the same notation as in the previous question, consider the following alternate approach. We process the DP array in increasing order of indices (i.e, $i = 1$ to $i = N$). We look at all disks $d_j$ such that $d_j$ can be placed on top of $d_i$. If $d_j$ can be placed on top of $d_i$, then $\text{DP}[i]$ is updated to be the maximum of $\text{DP}[i]$ and $\text{DP}[j] + H$, where $H$ is the height of the disk $d_i$.

Note that the DP array is initialized as before, that is, $\text{DP}[i]$ is initialized to the height of $d_i$.

What can you say about this approach?

With the same notation as in the previous questions, consider the following alternate approach. We first organize the disks in non-decreasing order of heights, that is, $d_1$ is a disk that has the smallest height, while $d_N$ is a disk that has the largest height.

We process the DP array in increasing order of indices (i.e, $i = 1$ to $i = N$). We look at all disks $d_j$ where $j < i$ such that $d_j$ can be placed on top of $d_i$.

If $d_j$ can be placed on top of $d_i$, then $\text{DP}[i]$ is updated to be the maximum of $\text{DP}[i]$ and $\text{DP}[j] + H$, where $H$ is the height of the disk $d_i$.

What can you say about this approach?

What is the complexity of this algorithm?

We are given a set of N dice, each with S sides, and a target integer T , which represents a target sum to obtain when rolling all of the dice and summing their values. Your goal is to determine the total number of dice-roll permutations that sum up to exactly that target value.
All three input values will always be positive integers. Each of the dice has an equal probability of landing on any number from 1 to S.
Identical total dice rolls obtained from different individual dice rolls (for example, [2, 3] vs. [3, 2]) count as different dice-roll permutations.
If there’s no possible dice-roll combination that sums up to the target given the input dice, the answer is zero.
Based on the above data, answer the given subquestions.

If we have 1 die with 6 sides, how many ways can we achieve a target sum of 4?

We are given a set of N dice, each with S sides, and a target integer T , which represents a target sum to obtain when rolling all of the dice and summing their values. Your goal is to determine the total number of dice-roll permutations that sum up to exactly that target value.
All three input values will always be positive integers. Each of the dice has an equal probability of landing on any number from 1 to S.
Identical total dice rolls obtained from different individual dice rolls (for example, [2, 3] vs. [3, 2]) count as different dice-roll permutations.
If there’s no possible dice-roll combination that sums up to the target given the input dice, the answer is zero.
Based on the above data, answer the given subquestions.

If we have 3 dice with 17 sides each, how many ways can we achieve a target sum of 7?

We are given a set of N dice, each with S sides, and a target integer T , which represents a target sum to obtain when rolling all of the dice and summing their values. Your goal is to determine the total number of dice-roll permutations that sum up to exactly that target value.
All three input values will always be positive integers. Each of the dice has an equal probability of landing on any number from 1 to S.
Identical total dice rolls obtained from different individual dice rolls (for example, [2, 3] vs. [3, 2]) count as different dice-roll permutations.
If there’s no possible dice-roll combination that sums up to the target given the input dice, the answer is zero.
Based on the above data, answer the given subquestions.

Suppose the input consists of 3 dice, each with 4 sides, and the target sum is 9. What’s the answer?

We are given a set of N dice, each with S sides, and a target integer T , which represents a target sum to obtain when rolling all of the dice and summing their values. Your goal is to determine the total number of dice-roll permutations that sum up to exactly that target value.
All three input values will always be positive integers. Each of the dice has an equal probability of landing on any number from 1 to S.
Identical total dice rolls obtained from different individual dice rolls (for example, [2, 3] vs. [3, 2]) count as different dice-roll permutations.
If there’s no possible dice-roll combination that sums up to the target given the input dice, the answer is zero.
Based on the above data, answer the given subquestions.

In which of the following scenarios will the answer be zero?

We are given a set of N dice, each with S sides, and a target integer T , which represents a target sum to obtain when rolling all of the dice and summing their values. Your goal is to determine the total number of dice-roll permutations that sum up to exactly that target value.
All three input values will always be positive integers. Each of the dice has an equal probability of landing on any number from 1 to S.
Identical total dice rolls obtained from different individual dice rolls (for example, [2, 3] vs. [3, 2]) count as different dice-roll permutations.
If there’s no possible dice-roll combination that sums up to the target given the input dice, the answer is zero.
Based on the above data, answer the given subquestions.

If we have one die with six sides, what are the achievable targets?

We are given a set of N dice, each with S sides, and a target integer T , which represents a target sum to obtain when rolling all of the dice and summing their values. Your goal is to determine the total number of dice-roll permutations that sum up to exactly that target value.
All three input values will always be positive integers. Each of the dice has an equal probability of landing on any number from 1 to S.
Identical total dice rolls obtained from different individual dice rolls (for example, [2, 3] vs. [3, 2]) count as different dice-roll permutations.
If there’s no possible dice-roll combination that sums up to the target given the input dice, the answer is zero.
Based on the above data, answer the given subquestions.

Let DP[N,T ] denote the number of ways to achieve a target sum of T > 0 using N > 0 dice. Which of the following recursive formulas is correct if all the dice have S sides?

We are given a set of N dice, each with S sides, and a target integer T , which represents a target sum to obtain when rolling all of the dice and summing their values. Your goal is to determine the total number of dice-roll permutations that sum up to exactly that target value.
All three input values will always be positive integers. Each of the dice has an equal probability of landing on any number from 1 to S.
Identical total dice rolls obtained from different individual dice rolls (for example, [2, 3] vs. [3, 2]) count as different dice-roll permutations.
If there’s no possible dice-roll combination that sums up to the target given the input dice, the answer is zero.
Based on the above data, answer the given subquestions.

What is the value of DP[0, 0]?

We are given a set of N dice, each with S sides, and a target integer T , which represents a target sum to obtain when rolling all of the dice and summing their values. Your goal is to determine the total number of dice-roll permutations that sum up to exactly that target value.
All three input values will always be positive integers. Each of the dice has an equal probability of landing on any number from 1 to S.
Identical total dice rolls obtained from different individual dice rolls (for example, [2, 3] vs. [3, 2]) count as different dice-roll permutations.
If there’s no possible dice-roll combination that sums up to the target given the input dice, the answer is zero.
Based on the above data, answer the given subquestions.

What is the value of DP[0, T ] for any T > 0?

We are given a set of N dice, each with S sides, and a target integer T , which represents a target sum to obtain when rolling all of the dice and summing their values. Your goal is to determine the total number of dice-roll permutations that sum up to exactly that target value.
All three input values will always be positive integers. Each of the dice has an equal probability of landing on any number from 1 to S.
Identical total dice rolls obtained from different individual dice rolls (for example, [2, 3] vs. [3, 2]) count as different dice-roll permutations.
If there’s no possible dice-roll combination that sums up to the target given the input dice, the answer is zero.
Based on the above data, answer the given subquestions.

What is the value of DP[N , 0] for any N > 0?

We are given a set of N dice, each with S sides, and a target integer T , which represents a target sum to obtain when rolling all of the dice and summing their values. Your goal is to determine the total number of dice-roll permutations that sum up to exactly that target value.
All three input values will always be positive integers. Each of the dice has an equal probability of landing on any number from 1 to S.
Identical total dice rolls obtained from different individual dice rolls (for example, [2, 3] vs. [3, 2]) count as different dice-roll permutations.
If there’s no possible dice-roll combination that sums up to the target given the input dice, the answer is zero.
Based on the above data, answer the given subquestions.

What is the value of DP[N , T ] if T < N ?

We are given a set of N dice, each with S sides, and a target integer T , which represents a target sum to obtain when rolling all of the dice and summing their values. Your goal is to determine the total number of dice-roll permutations that sum up to exactly that target value.
All three input values will always be positive integers. Each of the dice has an equal probability of landing on any number from 1 to S.
Identical total dice rolls obtained from different individual dice rolls (for example, [2, 3] vs. [3, 2]) count as different dice-roll permutations.
If there’s no possible dice-roll combination that sums up to the target given the input dice, the answer is zero.
Based on the above data, answer the given subquestions.

What is the complexity of this algorithm ?

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

In this given subquestion, we will examine the relationship of treewidth with other graph parameters.

Let G be an undirected connected graph and T be a depth-first search (DFS) tree of G rooted at a vertex r. An edge of G is called a back edge if the endpoints of the edge are on the same root to leaf path in T . That is, an edge is from a vertex to one of its ancestors in the DFS tree. An edge that is not a back edge is called a cross edge. Indeed, such an edge points from a vertex to a previously visited vertex that is neither an ancestor nor a descendant. Which of the following statements are true?

In this given subquestion, we will examine the relationship of treewidth with other graph parameters.

Let G be an undirected connected graph and T be a depth-first search (DFS) tree of G rooted at a vertex r. Depth of T is the length of a longest path from root to a leaf. Let q be the depth of T . Which of the following statements are true?

In this given subquestion, we will examine the relationship of treewidth with other graph parameters.

Suppose we are given an ILP which seeks to minimize an objective functions subject to constraints. We solve the LP relaxation and find an optimal solution with the objective evaluating to 54.3. What can you say about the original ILP?
Based on the above data, answer the given subquestions.

If the ILP is feasible, its optimal solution must be greater than or equal to 54.3

Suppose we are given an ILP which seeks to minimize an objective functions subject to constraints. We solve the LP relaxation and find an optimal solution with the objective evaluating to 54.3. What can you say about the original ILP?
Based on the above data, answer the given subquestions.

If the ILP is feasible, its optimal solution must be less than or equal to 54.3.

Suppose we are given an ILP which seeks to minimize an objective functions subject to constraints. We solve the LP relaxation and find an optimal solution with the objective evaluating to 54.3. What can you say about the original ILP?
Based on the above data, answer the given subquestions.

It is possible that the ILP’s optimal solution (if it exists) will be 50 ×10²³³¹.

Suppose we are given an ILP which seeks to minimize an objective functions subject to constraints. We solve the LP relaxation and find an optimal solution with the objective evaluating to 54.3. What can you say about the original ILP?
Based on the above data, answer the given subquestions.

It is possible that the ILP’s optimal solution (if it exists) will also be 54.3.

Suppose we are given an ILP which seeks to minimize an objective functions subject to constraints. We solve the LP relaxation and find an optimal solution with the objective evaluating to 54.3. What can you say about the original ILP?
Based on the above data, answer the given subquestions.

The ILP is guaranteed to be feasible.

Based on the above data, answer the given subquestions.

What is the size of each Ai?

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

For n = 4, calculate the number of sequences of length 3 consisting only of numbers 0, 1, and 2 such that each number occurs at least once.

Based on the above data, answer the given subquestions.

For n = 6, calculate the number of sequences of length 5 consisting only of numbers 0, 1, and 2 such that each number occurs at least once.

Based on the above data, answer the given subquestions.

How many numbers in the interval [1; r] are divisible by pi ? The answer to this question is:

Based on the above data, answer the given subquestions.

The final answer is:

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex.

The CLUSTER VERTEX DELETION problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph. We need to find if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph.

Determine, for each statement given , if it is true or false.

Based on the above data, answer the given subquestions.

A graph G is a cluster graph if and only if it does not have an induced path on 3 vertices.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex.

The CLUSTER VERTEX DELETION problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph. We need to find if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph.

Determine, for each statement given , if it is true or false.

Based on the above data, answer the given subquestions.

In the DISJOINT CLUSTER VERTEX DELETION problem, if the subgraph induced on S is not a cluster graph, we can immediately return YES.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex.

The CLUSTER VERTEX DELETION problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph. We need to find if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph.

Determine, for each statement given , if it is true or false.

Based on the above data, answer the given subquestions.

In the DISJOINT CLUSTER VERTEX DELETION problem, if the subgraph induced on the vertices of S is not a cluster graph, we can immediately return NO.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex.

The CLUSTER VERTEX DELETION problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph. We need to find if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph.

Determine, for each statement given , if it is true or false.

Based on the above data, answer the given subquestions.

If the subgraph induced on the vertices of S is a cluster graph and a vertex in V(G)\S is adjacent to at least two vertices in S which are in different cliques, then we can delete it and leave the parameter unchanged.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex.

The CLUSTER VERTEX DELETION problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph. We need to find if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph.

Determine, for each statement given , if it is true or false.

Based on the above data, answer the given subquestions.

If the subgraph induced on the vertices of S is a cluster graph and a vertex in V(G)\S is adjacent to at least two vertices in S which are in different cliques, then we can delete it and decrease the parameter by 1.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex.

The CLUSTER VERTEX DELETION problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph. We need to find if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph.

Determine, for each statement given , if it is true or false.

Based on the above data, answer the given subquestions.

If the subgraph induced on the vertices of S is a cluster graph and a vertex in V(G)\S is adjacent to some but not all vertices in a clique of G[S], then we can delete it and leave the parameter unchanged.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex.

The CLUSTER VERTEX DELETION problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph. We need to find if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph.

Determine, for each statement given , if it is true or false.

Based on the above data, answer the given subquestions.

If the subgraph induced on the vertices of S is a cluster graph and a vertex in V(G)\S is adjacent to some but not all vertices in a clique of G[S], then we can delete it and decrease the parameter by 1.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex.

The CLUSTER VERTEX DELETION problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph. We need to find if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph.

Determine, for each statement given , if it is true or false.

Based on the above data, answer the given subquestions.

After modifying the input instance, we can solve DISJOINT CLUSTER VERTEX DELETION by solving a matching problem on a bipartite graph.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex.

The CLUSTER VERTEX DELETION problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph. We need to find if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph.

Determine, for each statement given , if it is true or false.

Based on the above data, answer the given subquestions.

DISJOINT CLUSTER VERTEX DELETION is NP-Hard.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex.

The CLUSTER VERTEX DELETION problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph. We need to find if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph.

Determine, for each statement given , if it is true or false.

Based on the above data, answer the given subquestions.