# 算法代写 | CS 330, Fall 2020, Homework 12

这个作业是完成图算法和NP算法相关的编程

CS 330, Fall 2020, Homework 12

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?]