CS 5114 --- Sample Project Proposal

This proposal was developed roughly as follows.

• I browsed some of the online journals listed as Sources for CS 5114 Projects. Most of the papers mention a problem that could be attacked algorithmically. These problems come from a variety of research areas, so there is something to interest just about anyone.

• Fairly quickly, I found A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem, a paper on a topic that interested me and that had the potential of open problems to work on. As the abstract states:

  Any further improvement on this bound, matching the best constant factor known for the vertex cover problem, is deemed challenging.

  Since this paper was just published in 1999, I can hope that its information on the Feedback Vertex Set problem is sufficiently up-to-date that its open problems should still be open.

• I retrieved the postscript version and read it. I identified some of the papers that I would need to obtain to research this problem. Searching for these with a MathSciNet Full Search, I retrieved preformatted BibTeX entries for all the papers except the techical report. The references to in the LaTeX bib file sample.bib.

• I considered various possible research directions:
  • Try for a better approximation than the factor 2 for limited classes of graphs (restricting the possible instances).
  • Would randomizing the algorithm result in any improvement?
  • Look at the average approximation ratio that the algorithm achieves, rather than the worst case. Is it much better than 2?
  • Change the statement of the problem slightly to see whether the problem becomes easier or harder. For example, suppose we ask for a set of vertices such that every maximal clique contains at least vertex in that set. Is that NP-complete? Easy?
  • Consider alternative ideas for obtaining an algorithm. For example, suppose we choose a vertex greedily based solely on how many simple cycles it is in --- choose the vertex contained in the most simple cycles. What can be said about this algorithm?
  • Implement several algorithms and experiment with them. Which gives the best approximation ratio experimentally on some class of graphs, such as the class of random graphs?

• After deciding what directions I wished to pursue, I started writing the proposal using a skeleton LaTeX file. I also used a Makefile for the project. Some LaTeX distributions might not have the SIAM bibliography style, and you will need it. The initial skeleton looks like this in postscript and like this in PDF.

• The project proposal in LaTeX results in this postscript file and in this PDF file.

• Throughout your CS 5114 project, you can build on this initial LaTeX proposal to reach the next product in the project.