Graph Covers and Independent Sets
A typical graph problem is that of matching different items, such as dates between men and women given preferences or teachers and courses with different preferences. These are all examples of maximum independent edge problems. Similar resource allocation problems are related to all the cover and independent set problems.
FindClique — find complete subgraphs
CompleteGraphQ — test whether a graph is a complete graph
FindVertexCover — find vertex sets that are incident to every edge
VertexCoverQ — test whether a vertex set is a vertex cover
FindEdgeCover — find edge sets that are incident to every vertex
EdgeCoverQ — test whether an edge set is an edge cover
FindIndependentVertexSet — find vertex sets that are never incident to the same edge
IndependentVertexSetQ — test whether a vertex set is an independent vertex set
FindIndependentEdgeSet — find edge sets ("matchings") that are never incident to the same vertex
IndependentEdgeSetQ — test whether an edge set is an independent edge set
