Quiz Space

Advanced Algorithms · Quiz 2 · 4 Aug 2024 · May 2024 term

Question 2: The TRIANGLE-FREEDOM problem is the following: the input …

Question 2

+3 marksOne or more correct options

Based on the above data, answer the given subquestions.

The TRIANGLE-FREEDOM problem is the following: the input is a simple undirected graph G and a positive integer k. An instance (G, k) is a YES-instance if and only if G has a subset S of at least k vertices that are triangle-free.
What can you say about TRIANGLE-FREEDOM? Check all that apply.

Select all that apply.

  1. A

    It is in P.

  2. B

    It is in NP.

  3. C

    It is NP-hard.

  4. D

    It is NP-complete.

Show answer

Correct answers

  • B

    It is in NP.

  • C

    It is NP-hard.

  • D

    It is NP-complete.

See the whole paperTake it as a mock test

Question 2 of 21 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) Quiz 2 paper sat on 4 Aug 2024, in the May 2024 term (IIT M DEGREE AN EXAM QDB2 4 Aug 2024). It carries 3 marks.

More questions from this paper

  1. Q1Consider the following graph. A triangle-free subset of seven vertices is highlighted. Find the size of the largest tri…
  2. Q3Figure question
  3. Q4Recall 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…
  4. Q5Figure question
  5. Q6The worst-case running time and expected running time are equal to within constant factors for any randomized algorithm.
  6. Q7An adversary can provide randomized quicksort with an input array of length n that forces the algorithm to run in \omeg…
  7. Q8Figure question
  8. Q9Recall that in the vertex cover problem, we are trying to find a smallest subset S of vertices in a graph G such that G…
  9. Q10Recall that in the vertex cover problem, we are trying to find a smallest subset S of vertices in a graph G such that G…
  10. Q11Recall that in the vertex cover problem, we are trying to find a smallest subset S of vertices in a graph G such that G…
  11. Q12Recall that in the vertex cover problem, we are trying to find a smallest subset S of vertices in a graph G such that G…
  12. Q13Based on the above data, answer the given subquestions.
  13. Q14Based on the above data, answer the given subquestions.
  14. Q15Based on the above data, answer the given subquestions.
  15. Q16The construction described here is a valid reduction from 3-SAT to 3-Coloring.
  16. Q17The construction described here is a valid reduction from 3-Coloring to 3-SAT.
  17. Q18Argue that to solve SCS, it is sufficient to find:
  18. Q19Observe that for a given \pi, the length of the corresponding superstring s(\pi), which is obtained by writing the inpu…
  19. Q20We define an overlap graph OG(\mathcal{S}) associated with \mathcal{S} as follows: OG(\mathcal{S}) is a complete direct…
  20. Q21Does the greedy algorithm always produce the right answer?