A generic greedy algorithm, partially-ordered graphs and NP-completeness

Puricella, A.; Stewart, I.A.

Abstract

Let π 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 π, with respect to one of these linear orders, contains a specified vertex is NP-complete.

Citation

Puricella, A., & Stewart, I. (2001). A generic greedy algorithm, partially-ordered graphs and NP-completeness. In A. Brandstaedt, & V. Le (Eds.), Graph-theoretic concepts in computer science : 27th International Workshop, WG 2001, 14-16 June 2001, Boltenhagen, Germany ; proceedings (306-316). https://doi.org/10.1007/3-540-45477-2_28

• Conference Name: 27th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2001)
• Conference Location: Rostock, Germany
• Start Date: Jun 14, 2001
• End Date: Jun 16, 2001
• Publication Date: Oct 2, 2001
• Deposit Date: Jul 2, 2009
• Publicly Available Date: Aug 25, 2009
• Pages: 306-316
• Series Title: Lecture notes in computer science
• Series Number: 2204
• Series ISSN: 0302-9743,1611-3349
• Book Title: Graph-theoretic concepts in computer science : 27th International Workshop, WG 2001, 14-16 June 2001, Boltenhagen, Germany ; proceedings.
• ISBN: 9783540427070
• DOI: https://doi.org/10.1007/3-540-45477-2_28
• Keywords: Greedy algorithms, NP-completeness, Hereditary properties.
• Public URL: https://durham-repository.worktribe.com/output/1695306