Go backward to 35 ShellabilityGo 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 |

Related problems: | 19, 35 |
---|

Why are some symbols not displayed correctly? |