YorkU Biology Lab scientists have received n samples of the coronavirus and using their limited lab capability want to find out $($as much as possible$)$ how many different variants of the virus these samples may come from. They have a specialized lab equipment for this purpose that in each round it can run a test on any given pair of virus samples. At the completion of the test, one of $3$ possible lights on the device goes off: blue means the two virus samples being tested are definitely the same variant; red means they are definitely different variants; and green means the test was inconclusive on that sample pair. $($Multiple runs of testing on the same sample pair will always give the same result.$)$ Using this device, the lab scientists have run tests on all pairs among the n available samples and have modeled the test results by a graph G$=($V$,$E$)$

whose n vertices represent the n virus samples, and edges represent the conclusive test results $($excluding those that were inconclusive$).$ Each edge of G

is labeled blue or red according to the test result on the pair of nodes incident to that edge.

Given this edge coloured graph G

$,$ they want to determine whether the n samples must come from at least $3$ different variants, or they may possibly come from at most $2$ different variants. In other words, they need to determine whether the vertices can be partitioned into two possible groups $($of virus variants$)$ in such a way that each blue edge is incident to two vertices that are in the same group, and each red edge is incident to two vertices that are not in the same group.

The Lab has hired you as their consultant to solve this problem algorithmically. The worst$-$case most efficient time complexity of an algorithm to solve this problem is

Question $2$Answer

a$.$

$\backslash$theta $($VE$)$

$.$

b$.$

$\backslash$theta $($V$3)$

$.$

c$.$

This problem cannot be solved $($deterministically$)$ in polynomial time, unless P$=$NP

$.$

d$.$

$\backslash$theta $($V$2)$

$.$

e$.$

$\backslash$theta $($V$+$E$)$

$.$

f$.$

$\backslash$theta $($ElogV$)$

$.$