|Input:||Finite abstract simplicial complex D given by a list of facets|
|Output:||"Yes" if D is partionable, "No" otherwise|
|Status (fixed dim.):||Open|
As in Problem 19, partitionability is meant in the sense
of Stanley  (see also ).
Noble  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 D is given by a list of all simplices.
|Related problems:||19, 35|