Homework #5
- 10.8
- 10.9
- 10.12
- 10.24
- 10.26 augmented by the following:
The notion of completeness of a member in a set in conjuction with a
reduction appears in many context. For instance, a problem is said to be general graph isomorphism hard (GI-hard) if the problem of isomorphism
of two undirected graphs can be (poly-time) reduced to it.
- What would be a consequence of the discovery of a poly-time
algorithm solving a GI-hard problem?
- Show that the directed graph isomorphism problem is GI-hard.
- Show that the bipartite graph isomorphism problem is
GI-complete. (A bipartite graph has vertices partitioned into
two subsets, so that every edge has one endvertex in each subset.)
- Show that the chordal graph isomorphism problem is GI-complete. (A
chordal graph has no cycle of length larger than 3 without a
chord ``shortcutting'' it.)