Publication details for Professor Iain StewartPuricella, A. & Stewart, I.A. (2001). A generic greedy algorithm, partially-ordered graphs and NP-completeness. 27th International Workshop on Graph-Theoretic Concepts in Computer Science, WG'01, Rostock, Germany, Springer-Verlag.
- Publication type: Conference Proceeding
- ISSN/ISBN: 9783540427070 (print), 9783540454779 (online)
- DOI: 10.1007/3-540-45477-2_28
- Keywords: Greedy algorithms, NP-completeness, Hereditary properties.
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
Let $\pi$ be any fixed polynomial-time testable, non-trivial, hereditary property of graphs. Suppose that the vertices of a graph G are not necessarily linearly ordered but partially ordered, where we think of this partial order as a collection of (possibly exponentially many) linear orders in the natural way. We prove that the problem of deciding whether a lexicographically first maximal subgraph of G satisfying $\pi$, with respect to one of these linear orders, contains a specified vertex is NP-complete.