Ordered vertex removal and subgraph problems

摘要

Several new graph theoretic problems, which arise naturally from existing coloring algorithms, are defined. The complementary High Degree Vertex Removal Problem and Low Degree Vertex Removal Problem are both shown to be NP-complete. The Low Degree Subgraph Problem is defined and shown to be NP-complete, whereas, the “complementary” problem for high degree subgraphs was previously shown to be P-complete. Since the obvious sequential algorithms for computing the low degree subgraph and high degree subgraph are based on high degree vertex removal and low degree vertex removal, respectively, we find this is an interesting result. The “greedy” versions of the vertex removal and subgraph are shown to be P-complete. In addition, a natural lexicographic version of the Low Degree Subgraph Problem is shown to be NP-complete.