From tivadar@ccs.neu.edu Tue Apr 13 10:35:04 2004
Date: Thu, 26 Feb 2004 18:15:30 -0500 (EST)
From: Eric I. Robinson <tivadar@ccs.neu.edu>
To: Joseph Willey <jjw@ccs.neu.edu>
Cc: csg399@ccs.neu.edu
Subject: Re: CSG399: HW 2 Problems 4 & 5

Yeah, my solution to 5 was as follows:

Given a graph for which you wish to solve the VC problem, make a new graph
in the following manner:  For each edge in the old graph, duplicate that
edge in the new graph.  Now each pair of connected vertices for a cycle.
In a solution for the FVS, we know that each cycle must be eliminated, the
only way of doing this is removing one vertex in every pair of adjacent
vertices.  Clearly this forms a VC.  In addition, we know we will never
have to remove extra vertices in the FVS problem, because once one in each
pair of adjacent vertices have been removed, there cannot possibly be any
edges left in the graph.  Hence a solution approximation to FVS implies a
solution to VC where V' = V, and E' = 2E.

Eric

On Wed, 25 Feb 2004, Joseph Willey wrote:

> Hello,
>
> Attached are my thoughts on/solutions to the last two problems for
> HW #2. I apologize in advance for the length of the writeup.
> Questions, comments, corrections, and criticisms are welcome.
>
> BTW, after having written up my solution for #5, I talked to a classmate
> who has a better solution (that duplicates edges and adds no vertices).
> So there are likely better approaches to one or both of the problems
> than those which I've attached.
>
>
>
> Regards,
> Joe Willey