Advanced Algorithms · End Term · 3 Sept 2023 · May 2023 term · Set QPE1-S2

Question 22: Consider the following orientation problem. We are given…

Question 22

+5 marksOne correct option

Consider the following orientation problem.

We are given an undirected graph $G = (V, E)$ and integer values $p(v)$ for every vertex $v \in V$ . We would like to know if we can orient the edges of $G$ such that the directed graph we obtain has at most $p(v)$ arcs incoming to $v$ (the 'in-degree requirements').

In other words, for each edge $\{u, v\}$ , we have to decide whether to orient it as $(u, v)$ or as $(v, u)$ , and we would like at most $p(v)$ arcs to be oriented towards $v$ .

This problem is:

A
NP-hard because there is a polynomial-time reduction to SAT
B
NP-hard because there is a polynomial-time reduction to MaxFlow
C
in P because there is a polynomial-time reduction to MaxFlow
D
in P because there is a polynomial-time reduction to SAT

Show answer

Correct answer

C
in P because there is a polynomial-time reduction to MaxFlow

See the whole paper Take it as a mock test

Question 22 of 34 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) End Term paper sat on 3 Sept 2023, in the May 2023 term (IIT M DEGREE ET1 EXAM QPE1 S2 03 Sep). It carries 5 marks.

This question was also asked in

Advanced Algorithms End Term — 3 Sept 2023, Set QPE1-S1 · question 23

Question 22: Consider the following orientation problem. We are given…

Question 22

This question was also asked in

More questions from this paper