Matching and Vertex Packing: How Hard Are They?
Abstract
Two of the most well-known problems in graph theory are: Find a maximum matching (or perfect matching, if one exists); and Find a maximum independent set of vertices. The first problem-usually called the matching problem-is known to have a polynomial algorithm; the second-often called the vertex packing problem-is known to be NP-complete. However, many graph theorists-especially those who do not deal much with complexity of algorithms- know little more about the complexity issues associated with these two problems than these two basic facts. What is not so widely known within the graph theory community is that these two problems have motivated a great deal of recent activity in the area of algorithms and their complexity. Of course it is not known whether or not P = NP, but most workers in the area currently believe that equality is unlikely to hold. Motivated by this belief, a number of people have studied variations of both matching and vertex packing with the general theme being two-fold. On the one hand, one can add various side conditions to the matching problem and study the complexity-both sequential and parallel-of the resulting problems. On the other hand, one can investigate certain large and interesting classes of graphs trying to prove that for these classes the vertex packing problem has a polynomial solution.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1991
- Accession Number
- ADA245928
Entities
People
- Michael D. Plummer
Organizations
- Vanderbilt University