Exercises
- Rosen 7.2, exercises 6, 11, 36, 38.
- Rosen 7.4, exercises 4, 8, 18, 29.a, 37, 49.
- Rosen 7.4, supplementary exercise 13. Hint for part c: see Section 7.4.5.
-
For a graph, \( G=(V,E) \), a spanning bipartite subgraph
\( G' \) of \( G \) is defined by a partition \( (V_1,V_2) \) of \( V \),
and the edges \( E' \subseteq E \) that have an endpoint in both parts.
Consider the following randomized algorithm for finding a
spanning bipartite subgraph of an arbitrary graph:
Independently, for each vertex \( v\in V \), decide uniformly at random
if vertex \( v \) is in \( V_1 \) or \( V_2 \).
- Give a lower bound on the expected number of edges \( m' \) in \( E' \) as a function of \( m = |E| \).
- How can you use your result to conclude that any graph has a spanning bipartite subgraph with \( m' \geq m/2 \)?
- Design a deterministic, polynomial-time algorithm for this problem, finding a spanning bipartite subgraph \( G' \) of any graph \( G \), where \( m' \geq m/2 \).