Input: | Finite abstract simplicial complex D given by a list
of facets |
---|---|

Output: | The f-vector of D |

Status (general): | #P-hard |
---|---|

Status (fixed dim.): | Polynomial time |

If D is given by all of its simplices the problem is
trivial. Clearly, for fixed k, the first k entries of the
f-vector can be computed in polynomial time, since the number of
k-simplices in D is polynomial in n. Hence the problem
is polynomial time solvable for fixed dimension dim(D).
It is unknown whether the decision problem "Given the list of
facets of To the best of our knowledge, up to now, no proof of
# The following problem is in P(see Garey
and Johnson [23] for a definition).
To prove # K. This problem is #P-hard: It is well
known that counting the vertex covers of size at most K is
#P-complete (see [23, p. 169]). Since a set V'
Í V is a vertex cover if and only if V \ V' is
a stable set, the claim follows. Let S be the number of
stable sets of size ^{=}(k)k. Clearly, it suffices to compute S to compute ^{=}(n),
S^{=}(n-1), ..., S^{=}(K)S. It follows
that the problem to compute ^{³ }(K)S is #^{=}(K)P-hard (in fact,
#P-complete).
Let n values
of i, it follows that computing f is #_{i}(D)P-hard.
We now construct a simplicial complex dual complex), which is given by its facets. Define
D by the facets ^{*}V \ e for each edge e Î E. Note that D is pure. We have that a set ^{*}S
Í V is a face of D if and only if V \ S is not a face of D. Hence, ^{*}f. It follows that
one can efficiently compute _{i}(D) +
f_{n-i-1}(D^{*}) = (_{i+1}^{n})f from
_{i}(D)f, which completes the proof.
_{n-i-1}(D^{*}) |

Related problems: | 15, 32 |
---|