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