Quiz Space

Advanced Algorithms · End Term · 1 Sept 2024 · May 2024 term · Set QDB1

Question 7: A subset S of vertices in an undirected graph G is half-i…

Question 7

+3 marksOne correct option

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?

  1. A

    Yes, this can be shown by a reduction from the standard maximum independent set problem.

  2. B

    Yes, and this can be shown by reducing the half-independent set problem to the standard maximum independent set problem.

  3. C

    No, the problem of finding a largest half-independent set of vertices is in P since it can be reduced to the problem of finding a maximum matching.

Show answer

Correct answer

  • A

    Yes, this can be shown by a reduction from the standard maximum independent set problem.

See the whole paperTake it as a mock test

Question 7 of 53 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) End Term paper sat on 1 Sept 2024, in the May 2024 term (IIT M DEGREE AN EXAM QDB3 01 Sep 2024). It carries 3 marks.

More questions from this paper

  1. Q1Figure question
  2. Q2Figure question
  3. Q3In this problem you are given as input a graph T = (V, E) that is a tree (that is, T is undirected, connected, and acyc…
  4. Q4Which of the following statements is true?\ Statement 1: For every graph G and every maximum flow on G, there always ex…
  5. Q5Recall the max-flow problem: for a directed graph G(V, E) with non-negative capacities c_e for every e \in E and two sp…
  6. Q6Figure question
  7. Q8Can the disk with dimensions [2,1,2] be placed above [3,2,3]?
  8. Q9Can the disk with dimensions [2,2,2] be placed above [3,2,3]?
  9. Q10Suppose the input consists of the following triplets: [[3, 5, 7], [3, 2, 2], [3, 1, 1], [5, 5, 9]]. What’s the answer?
  10. Q11Our 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…
  11. Q12With the same notation as in the previous question, consider the following alternate approach. We process the DP array …
  12. Q13With the same notation as in the previous questions, consider the following alternate approach. We first organize the d…
  13. Q14What is the complexity of this algorithm?
  14. Q15If we have 1 die with 6 sides, how many ways can we achieve a target sum of 4?
  15. Q16If we have 3 dice with 17 sides each, how many ways can we achieve a target sum of 7?
  16. Q17Suppose the input consists of 3 dice, each with 4 sides, and the target sum is 9. What’s the answer?
  17. Q18In which of the following scenarios will the answer be zero?
  18. Q19If we have one die with six sides, what are the achievable targets?
  19. Q20Let DP[N,T ] denote the number of ways to achieve a target sum of T > 0 using N > 0 dice. Which of the following recurs…
  20. Q21What is the value of DP[0, 0]?
  21. Q22What is the value of DP[0, T ] for any T > 0?
  22. Q23What is the value of DP[N , 0] for any N > 0?
  23. Q24What is the value of DP[N , T ] if T \< N ?
  24. Q25What is the complexity of this algorithm ?
  25. Q26Based on the above data, answer the given subquestions.
  26. Q27Based on the above data, answer the given subquestions.
  27. Q28Based on the above data, answer the given subquestions.
  28. Q29In this given subquestion, we will examine the relationship of treewidth with other graph parameters. Let G be an undir…
  29. Q30In this given subquestion, we will examine the relationship of treewidth with other graph parameters. Let G be an undir…
  30. Q31In this given subquestion, we will examine the relationship of treewidth with other graph parameters.
  31. Q32If the ILP is feasible, its optimal solution must be greater than or equal to 54.3
  32. Q33If the ILP is feasible, its optimal solution must be less than or equal to 54.3.
  33. Q34It is possible that the ILP’s optimal solution (if it exists) will be 50 ×10²³³¹.
  34. Q35It is possible that the ILP’s optimal solution (if it exists) will also be 54.3.
  35. Q36The ILP is guaranteed to be feasible.
  36. Q37What is the size of each Ai?
  37. Q38Based on the above data, answer the given subquestions.
  38. Q39Based on the above data, answer the given subquestions.
  39. Q40For n = 4, calculate the number of sequences of length 3 consisting only of numbers 0, 1, and 2 such that each number o…
  40. Q41For n = 6, calculate the number of sequences of length 5 consisting only of numbers 0, 1, and 2 such that each number o…
  41. Q42How many numbers in the interval [1; r] are divisible by pi ? The answer to this question is:
  42. Q43The final answer is:
  43. Q44A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  44. Q45A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  45. Q46A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  46. Q47A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  47. Q48A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  48. Q49A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  49. Q50A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  50. Q51A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  51. Q52A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…
  52. Q53A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph whe…