Go backward to 35 Shellability
Go up to 7 Beyond Polytopes
|
Go backward to 35 Shellability Go up to 7 Beyond Polytopes |
XHTML 1.0 |
| 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. |
| Related problems: | 19, 35 |
|---|
|
|
Why are some symbols not displayed correctly? |