This page contains the reliably extracted subset, not the complete original paper.
Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.
0 / 21 published solutions
Question 183 MCQ · 2.0 marks
Based on the above data, answer the given subquestions.
Consider the following graph. A triangle-free subset of seven vertices is highlighted. Find the size
of the largest triangle-free subset of vertices in this graph.
6406532878651.
7
6406532878652.
8
6406532878653.
9
6406532878654.
10
A published solution is not available for this question yet.
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.
6406532878655.
It is in P.
6406532878656.
It is in NP.
6406532878657.
It is NP-hard.
6406532878658.
It is NP-complete.
A published solution is not available for this question yet.
Finding a Hamiltonian cycle in a graph is as hard as determining the answer to
the Marbles Elimination question; i.e, there is a reduction from the problem of Marbles Elimination
to the problem of finding a Hamiltonian cycle.
6406532878660.
Determining the answer to the Marbles Elimination question is as hard as
finding a Hamiltonian cycle in a graph; i.e, there is a reduction from the Hamiltonian cycle problem
to the problem of Marbles Elimination.
6406532878661.
Marbles Elimination is in P by a reduction to the Max Flow problem.
A published solution is not available for this question yet.
Based on the above data, answer the given subquestions.
Recall that the size of an optimal vertex cover is at most twice the size of a maximum matching of
a graph G. Are there examples of graphs where the size of the optimal vertex cover is **exactly**
**equal** to twice the size of its maximum matching? For example, this is not true for a path on three
vertices: the size of both the maximum matching and minimum vertex cover is 1.
6406532878683.
Yes
6406532878684.
No
A published solution is not available for this question yet.
Based on the above data, answer the given subquestions.
Does the greedy algorithm always produce the right answer?
6406532878704.
Yes
6406532878705.
No
**RL**
**Section Id :** 64065361119
**Section Number :** 13
**Section type :** Online
**Mandatory or Optional :** Mandatory
**Number of Questions :** 16
**Number of Questions to be attempted :** 16
**Section Marks :** 40
**Display Number Panel :** Yes
**Section Negative Marks :** 0
**Group All Questions :** No
**Enable Mark as Answered Mark for Review and**
No
**Clear Response :**
**Section Maximum Duration :** 0
**Section Minimum Duration :** 0
**Section Time In :** Minutes
**Maximum Instruction Time :** 0
A published solution is not available for this question yet.
