ICS 280, Fall 2000: Exponential Algorithms
Homework Assignment 2

Consider the problem of finding a partition of the vertices of a graph into two trees. I.e., you are given as input an indirected graph. You must partition the vertices of the graph into two subsets, so that each subset is connected and contains no cycle.

For planar graphs, this is equivalent to finding a Hamiltonian cycle in the dual graph, so it is NP-complete. But for nonplanar graphs, it might have different time bounds than the Hamiltonian cycle problem.

  1. Outline a generate-and-test algorithm for this problem. I.e., describe a class of potential solutions, such that a partition into two trees (if it exists) can be found in polynomial time from one of the potential solutions. Try to make the size of the set of potential solutions as small as possible.

  3. How many potential solutions are there in your answer to part (a)? Give your answer as a formula involving n and/or m, the numbers of vertices and edges respectively in the input graph.

  5. Describe a recursive backtracking search for a solution, using the same space of partial solutions. What opportunities are there to discover that a potential solution will not work and return early from a recursive call?

  7. Does your backtracking solution have better worst-case complexity than the generate-and-test solution?

Due by email Monday, Oct. 23, 11:59PM.

Please do not send MS Word or other proprietary formats. Plain text, TeX, HTML, or PDF are all acceptable.