Go backward to 35 Shellability
Go up to 7 Beyond Polytopes

36 Partitionability

Input: Finite abstract simplicial complex Δ given by a list of facets
Output: "Yes" if Δ is partionable, "No" otherwise
Status (general): Open
Status (fixed dim.): Open
As in Problem 19, partitionability is meant in the sense of Stanley [60] (see also [66]). Noble [50] proved that the problem is in NP.

PARTITIONABILITY can be solved in polynomial time for one-dimensional complexes, i.e., for graphs: a graph is partitionable if and only if at most one of its connected components is a tree. For two-dimensional complexes the complexity status is open. In particular, it is unclear if the problem can be solved in polynomial time if Δ is given by a list of all simplices.

backup Why are some symbols not displayed correctly?