\documentstyle[fullpage]{article}
\begin{document}

\title{Reading Group Notes: Finding Max-Weight High-Girth Subgraphs}
\author{Levon Lloyd}
\date{February 14, 2003}
\maketitle

Problem: Given a weighted, undirected graph $G=(V, E)$, find the maximum weighted
 subgraph with no cycles of length $\leq t$.

If $t=N$, then this is the maximum spanning tree problem which has a polynomial t
ime solution.

If $t=2$, then you can take the whole graph so the problem is trivial.

For directed graphs and $t=N$, this is known as the {\em maximum weight acyclic
subgraph } or {\em feedback vertex set} problem.
It was proven NP-complete from vertex cover in Karp's original paper in 1972. 
Make two copies of the graph $G$ and $G'$.
Add directed arcs
i' to i'' for every node i in the original graph, and also
for every original edge (i,j) you have 2 directed arcs
i'' to j' and j'' to i'.


We prove our problem NP-complete in a similar way,
by reducing Vertex Cover in triangle free graphs to it.
Vertex cover in triangle free graphs was proven NP-Complete in
``NP-complete problems on a 3-connected cubic planar graph and their
applications'' by Ryuhei Uehara.
For a given instance of Vertex Cover $G=(V,E)$,
double the graph $G'=(V \cup V', E \cup E')$ and make all of the edges
of high weight, and add low weight edges
$E''={(v_i, v'_i)}, G''=(V \cup V', E \cup E' \cup E'')$ between the vertices
of the old graph with there corresponding vertices in the new graph.
Now for each edge in $E$ and $E'$ add a node in the middle and replace it
with two edges.
Now each edge in the original graph corresponds to a 6-cycle and each 4-cycle
in the original graph is now an 8-cycle.
So a minimum vertex cover in the original graph will correspond
to a maximum weight subgraph of our constructed graph with
no cycles of size 6 or less by taking out the edges of $E''$ that are
between the vertices of the vertex cover. 

We can see that a greedy approximation algorithm can be bad by looking
at a complete graph of $N$ nodes where each edge has weight 1.
In this graph, the greedy algorithm can end up choosing a star graph which
has total weight $N-1$ and another edge cannot be added without introducing
a cycle of size 3, but a complete bipartite graph has weight
$\frac{n^2}{4}$ so greedy $\leq \frac{n}{4} OPT$ and has no cycle of length 3.

For the case of $t=3$, the following heuristic gives a factor of two
approximation.
Find (an approximate) maximum cut of the graph.
The edges in this cut form a bipartite graph, so the graph formed by them
have no cycles of length 3 (or any odd length).
Further, a randomized or greedy vertex partition will select a cut that
cuts at least half the edges in the graph, giving us the factor
2 approximation.

Open question -- can we do anything interesting with larger girths?

\end{document}