| Input: | Finite abstract simplicial complex D given by a list of facets |
|---|---|
| Output: | "Yes" if D 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 D is given by a list of all simplices. |
| Related problems: | 19, 35 |
|---|