backup forward

Go backward to 32 Euler Characteristic
Go up to 7 Beyond Polytopes
Go forward to 34 Homology
XHTML 1.0

33 f-Vector of Simplicial Complexes

Input: Finite abstract simplicial complex Δ given by a list of facets
Output: The f-vector of Δ
Status (general): #P-hard
Status (fixed dim.): Polynomial time
If Δ 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 Δ is polynomial in n. Hence the problem is polynomial time solvable for fixed dimension dim(Δ).

It is unknown whether the decision problem "Given the list of facets of Δ and some φ∈ N ; is φ the total number of faces of Δ?" is contained in NP. This problem is only known to be in NP for partitionable (see Problem 19) simplicial complexes (see Kleinschmidt and Onn [39]).

To the best of our knowledge, up to now, no proof of #P-completeness of the general problem has appeared in the literature. Therefore we include the one of [53] here.

The following problem is in NP: Given a set S ⊆ [n] of size i, decide whether S ∈ Δ? The number of times the answer to a "guess" S is "yes" is exactly fi(Δ). Hence the corresponding counting problem is in #P (see Garey and Johnson [23] for a definition).

To prove #P-hardness, consider an instance of the STABLE SET problem, i.e., a simple graph G = (V, E) and an integer K. A stable set in G is a subset S of V such that S contains no edge of G, i.e., if {u, v} ∈ E then u ∉ S or v ∉ S. The corresponding counting problem is to compute the number S(K) of stable sets of size at least 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=(k) be the number of stable sets of size k. Clearly, it suffices to compute S=(n), S=(n-1), …, S=(K) to compute S(K). It follows that the problem to compute S=(K) is #P-hard (in fact, #P-complete).

Let n be the number of vertices and m be the number of edges of G. Let V be the vertex set of a simplicial complex Δ that is defined by the minimal non-faces e ∈ E. Clearly, S ⊆ V is a stable set in G if and only if S ∈ Δ. Hence, to solve the STABLE SET problem, we just have to ask if dim(Δ)+1 ≥ K. Since we can compute dim(Δ) by computing fi(Δ) for at most n values of i, it follows that computing fi(Δ) is #P-hard.

We now construct a simplicial complex Δ* (the dual complex), which is given by its facets. Define Δ* by the facets V  \ e for each edge e ∈ E. Note that Δ* is pure. We have that a set S ⊆ V is a face of Δ if and only if V  \ S is not a face of Δ*. Hence, fi(Δ) + fn-i-1*) = (i+1n). It follows that one can efficiently compute fi(Δ) from fn-i-1*), which completes the proof.


backup forward Why are some symbols not displayed correctly?