1 Noninterfering paths
Consider the following problem: given a directed graph G = (V, E) and two nodes s and t, we
say two paths are from s to t noninterfering if they do not share nodes other than s and t. Our
problem is to find the largest possible set of noninterfering paths. (In Lecture 21, we saw how to
find the largest set of paths that do not share any edges.)
1. Give an example of a graph G with vertices s and t in which there are at least two edge-disjoint
paths from s to t, but where every two paths from s to t share a node.
2. You want to give an algorithm that will find the largest set of noninterfering paths. You will
do so by giving reduction to the edge-disjoint paths problem from class. On input G, s, t, our
algorithm will
• build a new directed graph G0 = (V
0
, E0
), along with vertices s
0 and t
0
.
• run the algorithm from class to find a largest set of edge-disjoint paths p
0
1
, …, p0
k
from s
0
to t
0
in G0
.
• transform the paths p
0
1
, …, p0
k
into a set of paths in the original graph G and output
those.
Specify your algorithm by answering each of the questions below. Your descriptions should
be clear enough that any other student could turn them into working code.
(a) Describe V
0
, the set of nodes in G0
.
(b) Describe E0
, the set of edges in G0
.
(c) Which nodes in G0 will be s
0 and t
0
?
(d) Describe how you to transform a path p
0
in the new graph G0
into a path p in the original
graph.
3. What is the running time of your algorithm (including the time to find edge-disjoint paths in
G0
)?
4. Do not hand in, but write Prove your reduction is correct. You will need to prove two
statements: (a) Every set of edge-disjoint paths in G0 will be transformed into a set of
noninterfering paths in G, and (b) Every set of noninterfering paths in G corresponds to a
set of edge-disjoint paths in G0
.
1
2 Undecidability, Reductions, and NP
1. The DeadCode problem is the following: On input (a) the code of a Python function (for
simplicity, in a .py text file) and (b) an integer k, decide whether line k of the Python function
can ever be executed. You can assume that the Python code takes no inputs, and does not
read from external sources (disk, user input, network, etc).
My friend Alana thinks that this problem is undecidable. In fact, she thinks it is related to
the Halting problem discussed in class. Which of the following arguments would suffice to
prove that DeadCode is undecidable? Select the best fit:
# Alana shows how, supposing an algorithm A for DeadCode did exist, one can design
an algorithm B for Maximum-Flow that uses A as a subroutine.
# Alana shows how, supposing an algorithm A for DeadCode did exist, one can design
an algorithm B for Halting that uses A as a subroutine.
# Alana shows how, supposing an algorithm A for Maximum-Flow did exist, one can
design an algorithm B for DeadCode that uses A as a subroutine.
# Alana shows how, supposing an algorithm A for Halting did exist, one can design an
algorithm B for DeadCode that uses A as a subroutine.
[Exercise not to be handed in: Is Alana right? Write down a reduction that would prove her
claim.]
2. Given a graph directed G = (V, E) with edge capacities c, and two pairs of nodes (s1, t1) and
(s2, t2), a two-color flow is a pair of flows f1, f2, such that (a) f1 is a valid s1-t1 flow, and f2
is a valid s2-t2 flow, and (b) For each edge e, the sum of the flows along the edges is at most
c(e) (that is, f1(e) + f2(e) ≤ c(e).
Consider the following computational problem:
Max-Two-Color-Flow: Given a graph G, list of capacities c, and two pairs of nodes
(s1, t1) and (s2, t2), and a number k, determine if there exists a integral two-color flow (f1, f2)
where each flow has value at least k. (Here “integral” means that the flow values for both f1
and f2 are integers.)
Show that Max-Two-Color-Flow is in NP. [What would the certificate be, and what would
the verificiation algorithm have to check?]