# Homework 7

## CS 482 - Spring 2007

### Due: Wednesday, April 4

**Upcoming Prelim: **Our second prelim takes place on Tuesday, April 10,
at 7:30pm in Hollister B14. If you have a scheduling conflict, please let
our Course Administrator (Kelly Patwell) know as soon as possible.

**Reminder: **Please include your Cornell NetID on your each part of your
homework. We have been taking off points for those who neglect to include
their NetID.

### Part A

[Finding Cycles] For each of the following problems either show the problem
is NP-complete or describe the best (least-time) polynomial time algorithm that
you can find. For problems that are NP-complete, you are welcome to make
use of any of the NP-complete problems discussed in class or in the text.
For an algorithm, you should state the algorithm's runtime. It is not
necessary to prove that your algorithm works. Describe your algorithm at a very
high level, with just enough detail for someone familiar with this course to
understand how the algorithm works (i.e., we don't want to see code). You are
welcome to make use of any of the algorithms discussed in class or in the text.

- Input: a directed graph G and an integer k.

Question: Does G have a cycle of length __<__ k?

- Input: a directed graph G and an integer k.

Question: Does G have a cycle of length __>__ k?

- Input: a directed graph G with n=2k vertices.

Question: Does G have a cycle of length exactly k?

### Part B

[Genome Assembly] Do Problem 32 in Chapter 8 of the text.

### Part C

[Avoiding Pamphleteers] Now that the weather is warm, more people are
outside, including more people trying to hand pamphlets to passers-by.
Your friend Otto has developed an aversion to pamphleteers (i.e., people trying
to give him pamphlets). His goal is to pass few pamphleteers as he moves
around campus, but at the same time, he doesn't want to do too much extra
walking. Poor Otto has never had the benefit of CS482 and has asked for your
help.

Here's one way to model this problem: Given an undirected graph G where each
edge e is labeled with two integers (1) y_{e}, the distance along that
edge in yards, and (2) p_{e}, the number of pamphleteers along that
edge, and given a source node s, a destination node t, and bounds Y and P, is
there an s-to-t path in G that takes less than or equal to Y yards and passes
less than or equal to P pamphleteers?

Prove that APP (the Avoiding Pamphleteers Problem) is NP-complete.