Optimization Problems on Acyclic Orientations of Graphs, Shellability of Simplicial Complexes, and Acyclic Partitions

Abstract

In this chapter, we discuss optimization problems on orientations of a given graph, where the values of the objective functions are determined by the out-degrees of the resulted directed graph and the constraints contain acyclicity of the orientations. We survey applications of such optimization problems in polytope theory, shellability of simplicial complexes, and acyclic partitions. We also discuss such optimization problems without acyclicity constraint.

3.1 An Optimization Problem on Acyclic Orientation of Graphs in the Theory of Polytopes

For an undirected graph $G = (V(G), E(G))$ and its orientation O, we denote by $G^O$ the resulted directed graph. In this chapter, we consider optimization problems such that the values of the objective functions are determined by the out-degrees of $G^O$, where we vary the orientations O of G under some given restrictions. A typical example is the following problem.

$$\begin{aligned} (P1): \qquad \min&\sum _{v\in G} 2^{\text {out-deg}(v;\, G^O)} \\ {\text {s}.~\text {t.} }&O \,\text {is acyclic,} \end{aligned}$$

where the minimum is taken by varying the orientations O of G under the restriction that O is acyclic, i.e., there are no directed cycles on $G^O$. Here, $\text {out-deg}(v;\, G^O)$ is the out-degree of v in $G^O$. This optimization problem appears in the theory of polytopes. In [6], Blind and Mani showed the following theorem.

Theorem 1

(Blind and Mani [6]) The combinatorial structure of a simple polytope P is determined by its graph G(P).

Here, the graph G(P) of a polytope P is a graph consisting of the vertices and edges of P. In other words, two simple polytopes have isomorphic face lattices if and only if their graphs are isomorphic.

Later, Kalai [14] gave a simple short proof for Theorem 1. In his proof, the key is the notion of “good orientation.” An orientation O of G(P) is a good orientation if the restriction of $G(P)^O$ to every face of P (including P itself) has exactly one source. (Remark: In this chapter, we orient all the edges in a reverse way to the original paper. Originally, it is defined that an orientation is good if all the restriction of $G(P)^O$ to every face of P has exactly one sink. Here, a source is a node in a directed graph such that all the edges incident to the node are oriented from the node, and a sink is a node such that all the edges incident to it are oriented into the node.) Using this definition, it is shown that a set of vertices A of G(P) forms a face of P if and only if the induced subgraph G(P)[A] is k-regular and A is an ending set with respect to some good orientation O (i.e., all the edges connecting a vertex a of A and a vertex $a'$ outside of A are oriented from $a'$ to a.). By this fact, the remaining thing to be shown is to determine which orientations are good without knowing which set A of vertices forms a face of P. The following theorem is the answer to this.

Theorem 2

(Kalai [14]) For a simple polytope P, an orientation O of G(P) is a good orientation if and only if it is a minimizer of the problem (P1) with $G=G(P)$.

Since Theorem 2 assures that whether an orientation is good or not is determined only by G(P) (no information of the faces of P is needed), this gives the proof of Theorem 1. A comprehensive introduction of this story can be found in Ziegler [21, Lect. 3.4].

In this chapter, we introduce optimization problems similar to (P1) in the following sections in relation to the combinatorial structures of simplicial complexes and cubical complexes.

3.2 Shellability of Simplicial Complexes and Orientations of Facet-Ridge Incidence Graphs

A (finite) simplicial complex $\varGamma$ is a nonempty set of simplices in some Euclidean space $\mathbb {R}^N$ such that (i) every face of $\sigma \in \varGamma$ is a member of $\varGamma$, and (ii) $\sigma \cap \tau$ is a face of both $\sigma$ and $\tau$ for any $\sigma , \tau \in \varGamma$. (Remark: we treat the empty set as a $(-1)$-dimensional simplex, and in this definition, the empty set is always a member of a simplicial complex. Also we remark that we assume all the simplicial complexes are finite in this chapter.) The members of a simplicial complex $\varGamma$ are faces of $\varGamma$. We adopt the conventional terminology to mention 0-dimensional faces as vertices, 1-dimensional faces as edges, and the maximal faces with respect to inclusion as facets. The dimension of a simplicial complex $\varGamma$ is the maximum dimension of its faces. A simplicial complex is pure if all the facets are of the same dimension.

The combinatorial structures of simplicial complexes have been important subjects of study from several contexts, as a high-dimensional generalization of graphs, in the theory of polytopes (e.g., Ziegler [21, Lect. 8]), as a tool of topological methods in combinatorics (Björner [2]), or a way to address applications like computing network reliability (Colbourn [7]). One reason simplicial complexes appear in many contexts in combinatorics is because they are equivalent to a set family closed under taking subsets (i.e., “abstract simplicial complex”) which can be found quite commonly in many combinatorial structures. Among several combinatorial properties of simplicial complexes, shellability is one of the most famous and important properties, and it appears in many places.

Definition 1

A simplicial complex $\varGamma$ is shellable if the facets $\sigma _1, \sigma _2, \ldots , \sigma _t$ of $\varGamma$ can be ordered such that $(\bigcup _{j=1}^{i-1} \overline{\sigma }_j) \cap \overline{\sigma _i}$ is a $(\dim \sigma _i-1)$-dimensional pure subcomplex for each $2\le i\le t$, where $\overline{\sigma }$ denotes the simplicial complex consisting of all the faces of $\sigma$. An ordering of facets satisfying this condition is called a shelling.

Fig. 3.1

Shellable and nonshellable simplicial complexes

See Fig. 3.1 for examples of shellable and nonshellable simplicial complexes. During the previous century, shellability of simplicial complexes are only defined for pure simplicial complexes (e.g., [2, 21]). To define shellability for nonpure simplicial complexes is suggested by Björner and Wachs [4, 5] and now this generalized version has become the standard definition. Our definition above follows this version.

To distinguish shellable simplicial complexes and nonshellable ones is a difficult problem. All zero-dimensional simplicial complexes are shellable, and one-dimensional simplicial complexes are shellable if and only if its 1-dimensional edges are connected (i.e., a connected graph with some isolated vertices). However, for two- and higher dimensional simplicial complexes, no efficient way is known in general to recognize whether a given simplicial complex is shellable or not. The recognition problem is in the class NP, but it is neither known whether it is in P or not, nor whether it is NP-complete or not (Kaibel and Pfetsch [16, Sec. 34]). There is an efficient way to recognize shellability for the two-dimensional case if restricted to the class of pseudomanifolds (Danaraj and Klee [8]), but it is not known whether there exist efficient algorithms to recognize shellability for three-dimensional pseudomanifolds, even for the triangulations of spheres.

In this section, we give a characterization of shellability by an optimization problem on orientations of graphs. First, we restrict ourselves to the pure case for simplicity. Later, we give a generalized formulation including nonpure complexes. Our result in this section first appeared in Hachimori and Moriyama [13], and also appeared in Hachimori [11] with a generalized treatment. We here follow the proof given in Hachimori [11] and present in a somewhat more easily comprehensible way.

3.2.1 The Case of Pure Simplicial Complexes

Though our result of this section is valid for general simplicial complexes including both pure and nonpure simplicial complexes, we first present the result restricted to pure simplicial complexes in this subsection, since the pure case is essential in this result. The generalization to include the nonpure case, which will be presented in the next subsection, is just a technical revision and easy to follow after understanding the pure case.

For a pure d-dimensional simplicial complex $\varGamma$, we say that a face $\tau$ is a ridge of $\varGamma$ if it is covered by a facet, i.e., if $\tau \subseteq \sigma$ with $\dim \tau = \dim \sigma - 1$ for some facet $\sigma$. Let $\mathcal{F}(\varGamma )$ be the set of facets, and $\mathcal{R}(\varGamma )$ the set of ridges of $\varGamma$. Since $\varGamma$ is pure, $\mathcal{F}(\varGamma )$ is exactly the set of d-dimensional faces and $\mathcal{R}(\varGamma )$ is the set of $(d-1)$-dimensional faces of $\varGamma$. (Remark that we need to change the definition of ridges for nonpure complexes in the next subsection.) We let the graph $G(\varGamma )$ be the facet-ridge incidence graph, i.e., the bipartite graph with the partite sets $\mathcal{F}(\varGamma )$ and $\mathcal{R}(\varGamma )$, and two nodes $\sigma \in \mathcal{F}(\varGamma )$ and $\tau \in \mathcal{R}(\varGamma )$ are adjacent if and only if $\sigma \supseteq \tau$ in $\varGamma$.

We consider orientations of the graph $G(\varGamma )$. We denote the oriented arc from $\alpha$ to $\beta$ in $G(\varGamma )$ by $\alpha \rightarrow \beta$, and denote the directed path from $\alpha$ to $\beta$ by $\alpha \rightsquigarrow \beta$. We say an orientation O is admissible if $\text {in-deg}(\tau )\ge 1$ for every $\tau \in \mathcal{R}(\varGamma )$. We have the following characterization of shellability of pure simplicial complexes.

Theorem 3

For a pure d-dimensional simplicial complex $\varGamma$, let us consider the following minimization problem:

$$\begin{aligned} (P2): \qquad \min&\sum _{\sigma \in \mathcal{F}(\varGamma )} 2^{{\mathrm{out}\text {-}\mathrm{deg}}(\sigma ;\, G^O\!\!(\varGamma ))} \\ {\text {s}.~\text {t}. }&O \,\text { is acyclic and admissible.} \end{aligned}$$

Then the optimum value $V^*$ of (P2) satisfies $V^*\ge f(\varGamma )$, where $f(\varGamma )$ is the number of all the faces of $\varGamma$. Further, the equality holds if and only if $\varGamma$ is shellable.

The proof of Theorem 3 follows the following lemmas.

First, we define the set $S^O(\sigma )$ as follows.

$$\begin{aligned} S^O(\sigma )= & {} \{ \eta \in \varGamma : \sigma \rightarrow \tau \,\text {in}\, G^O(\varGamma ) \,\text {for every ridge}\, \tau \, \text {with}\, \eta \subseteq \tau \subseteq \sigma \} \cup \{\sigma \} . \nonumber \\ \end{aligned}$$

(3.1)

Note that the complement of $S^O(\sigma )$ in $\overline{\sigma }$, denoted as $S^{cO}(\sigma )$, is given as follows.

$$\begin{aligned} S^{cO}(\sigma )= & {} \overline{\sigma }-S^O(\sigma ) \nonumber \\= & {} \{ \eta \in \varGamma : \sigma \leftarrow \tau \, \text {in}\, G^O(\varGamma )\, \text {for some ridge}\, \tau \, \text {with}\, \eta \subseteq \tau \subseteq \sigma \} \nonumber \\= & {} \bigcup \{\, \overline{\tau } : \tau \in \mathcal{R}(\varGamma ), \, \sigma \leftarrow \tau \, \text {in}\, G^O(\varGamma )\}. \end{aligned}$$

(3.2)

Lemma 1

Let $\varGamma$ be a pure simplicial complex, and let $\eta \in \varGamma$ and $\sigma \in \mathcal{F}(\varGamma )$. Then, for any orientation O, $\eta \in S^O(\sigma )$ if and only if $\sigma$ is a source node in $G^O_{\supseteq \eta }(\varGamma )$, where $G^O_{\supseteq \eta }(\varGamma )$ is the subgraph induced by the nodes corresponding to the facets and the ridges of $\varGamma$ containing $\eta$.

Proof

The proof is obvious from the definition of $S^O(\sigma )$.    $\square$

The inequality of the theorem follows the following lemma.

Lemma 2

Let $\varGamma$ be a pure simplicial complex and O an orientation of $G(\varGamma )$ that is acyclic and admissible. Then, we have $\sum _{\sigma \in \mathcal{F}(\varGamma )} 2^{{\mathrm{out}\text {-}\mathrm{deg}}(\sigma ;\, G^O\!\!(\varGamma ))} \ge f(\varGamma ).$

Proof

We have the graph $G^O_{\supseteq \eta }(\varGamma )$ acyclic since $G^O(\varGamma )$ is acyclic, and this implies that $G^O_{\supseteq \eta }(\varGamma )$ has at least one source node. This source node should be a facet, not a ridge, by the condition that O is admissible. By Lemma 1, this implies that the family $\{S^O(\sigma ): \sigma \in \mathcal{F}(\varGamma )\}$ covers $\varGamma$ (i.e., for any $\eta \in \varGamma$ there exists a $\sigma \in \mathcal{F}(\varGamma )$ such that $\eta \in S^O(\sigma )$ ). On the other hand, we have $|S^O(\sigma )|=2^{\text {out-deg}(\sigma ;\, G^O(\varGamma ))}$. (This follows from the fact that $S^O(\sigma )$ forms a boolean lattice with respect to inclusion relation. In fact, the smallest face in $S^O(\sigma )$ is given by $\sigma \cap \{\tau \in \mathcal{R}(\varGamma ) : \sigma \rightarrow \tau \, \text {in}\, G^O(\varGamma )\} =: \varPsi ^O(\sigma )$ and $S^O(\sigma )$ equals the interval $[\varPsi ^O(\sigma ), \sigma ]$ in the face poset of $\varGamma$. This interval is a boolean lattice since every proper interval in the face poset of a simplicial complex is boolean.) Hence the inequality is verified.    $\square$

By the proof of Lemma 2, we have the following natural consequence for the equality case.

Lemma 3

Let $\varGamma$ be a pure simplicial complex and O an orientation of $G(\varGamma )$ that is acyclic and admissible. The equality $\sum _{\sigma \in \mathcal{F}(\varGamma )} 2^{{\mathrm{out}\text {-}\mathrm{deg}}(\sigma ;\, G^O\!\!(\varGamma ))} = f(\varGamma )$ holds if and only if $\{S^O(\sigma ): \sigma \in \mathcal{F}(\varGamma )\}$ forms a partition of $\varGamma$.

Proof

By the proof of Lemma 2, $\{S^O(\sigma ): \sigma \in \mathcal{F}(\varGamma )\}$ covers $\varGamma$. Since $\sum _{\sigma \in \mathcal{F}(\varGamma )} 2^{{\text {out-deg}}(\sigma ;\, G^O\!\!(\varGamma ))}$ counts the number of the faces of $\varGamma$ with multiplicity in this covering, the equality means that each face of $\varGamma$ is contained in exactly one $S^O(\sigma )$.    $\square$

Here we define a graph $\widetilde{G}^O(\varGamma )$ whose nodes are the facets of $\varGamma$ and arcs $\sigma \rightarrow \sigma '$ are defined if there is a face $\eta \subseteq \sigma '$ with $\eta \in S^O(\sigma )$. We have the following lemma.

Lemma 4

When $\{S^O(\sigma ): \sigma \in \mathcal{F}(\varGamma )\}$ is a partition of a pure simplicial complex $\varGamma$, $\widetilde{G}^O(\varGamma )$ is acyclic if and only if $G^O(\varGamma )$ is acyclic.

Proof

Let us assume $\widetilde{G}^O(\varGamma )$ has a directed cycle. Assume $\sigma \rightarrow \sigma '$ is an arc in $\widetilde{G}^O(\varGamma )$. From the definition of $\widetilde{G}^O(\varGamma )$, there exists a face $\eta$ with $\eta \subseteq \sigma '$ and $\eta \in S^O(\sigma )$. Here, $\eta \subseteq \sigma '$ implies that both $\sigma$ and $\sigma '$ are nodes of $G^O_{\supseteq \eta }(\varGamma )$. From Lemma 1 and the assumption that $\{S^O(\sigma ): \sigma \in \mathcal{F}(\varGamma )\}$ is a partition, $\eta \in S^O(\sigma )$ implies that $\sigma$ is a unique source in $G^O_{\supseteq \eta }(\varGamma )$. This assures the existence of a directed path from $\sigma$ to $\sigma '$ in $G^O_{\supseteq \eta }(\varGamma )$, and thus in $G^O(\varGamma )$. Hence, the existence of a directed cycle in $\widetilde{G}^O(\varGamma )$ implies the existence of a directed cycle in $G^O(\varGamma )$.

On the other hand, let us assume $G^O(\varGamma )$ has a directed cycle. The cycle is of the form $\sigma _1\rightarrow \tau _1\rightarrow \sigma _2\rightarrow \tau _2 \rightarrow \cdots \rightarrow \sigma _s\rightarrow \tau _s\rightarrow \sigma _{s+1}=\sigma _{1}$, where $\sigma _i\in \mathcal{F}(\varGamma )$ for all $1\le i\le s$ and $\tau _j\in \mathcal{R}(\varGamma )$ for all $1\le j\le s$. Then we have $\tau _i\subseteq \sigma _i$ and $\tau _i\in S^O(\sigma _{i+1})$ for all $1\le i\le s$, and this implies there is a directed cycle in $\widetilde{G}^O(\varGamma )$.    $\square$

The following last lemma shows that having an acyclic admissible orientation O of $G(\varGamma )$ such that the family $\{S^O(\sigma ): \sigma \in \mathcal{F}(\varGamma )\}$ is a partition of $\varGamma$ and $\widetilde{G}^O(\varGamma )$ is acyclic is equivalent to the shellability of $\varGamma$.

Lemma 5

For a pure simplicial complex $\varGamma$, there exists an acyclic admissible orientation O of $G(\varGamma )$ such that $\{S^O(\sigma ): \sigma \in \mathcal{F}(\varGamma )\}$ is a partition of $\varGamma$ with $\widetilde{G}^O(\varGamma )$ acyclic if and only if $\varGamma$ is shellable.

Proof

To show the “only if” part, let us assume $\{S^O(\sigma ): \sigma \in \mathcal{F}(\varGamma )\}$ is a partition of $\varGamma$ and $\widetilde{G}^O(\varGamma )$ is acyclic. Let $\sigma _1, \sigma _2,\ldots ,\sigma _t$ be a linear extension (or a “topological sort”) of $\widetilde{G}^O(\varGamma )$, i.e., a total ordering such that the existence of a directed arc $\sigma _i\rightarrow \sigma _j$ in $\widetilde{G}^O(\varGamma )$ implies $i<j$. From the fact that $\{S^O(\sigma ): \sigma \in \mathcal{F}(\varGamma )\}$ is a partition together with the Eqs. (3.1) and (3.2), we have that $(\bigcup _{j=1}^{i-1} \overline{\sigma _j})\cap \overline{\sigma _i}= S^{cO}(\sigma _i)= \bigcup \{\, \overline{\tau } : \tau \in \mathcal{R}(\varGamma ),\, \sigma _i\leftarrow \tau \,\text {in}\, G^O(\varGamma )\}$ for every $1\le i\le t-1$. Hence, $\sigma _1, \sigma _2,\ldots ,\sigma _t$ is a shelling and $\varGamma$ is shellable since $(\bigcup _{j=1}^{i-1} \overline{\sigma _j})\cap \overline{\sigma _i}$ is $(\dim \sigma _i -1)$-dimensional and pure. (Note that, the set $\{\tau \in \mathcal{R}(\varGamma ) : \sigma _i\leftarrow \tau \, \text {in}\, G^O(\varGamma )\}$ is not empty for $i>1$ since $G(\varGamma )=G(\varGamma )_{\supseteq \emptyset }$ has only one source node and it should be $\sigma _1$.) For the “if” part, let $\varGamma$ be a pure shellable simplicial complex and $\sigma _1, \sigma _2, \ldots , \sigma _t$ be its shelling. It is well known that this shelling induces a partition of $\varGamma$ by $\bigcup _{i=1}^t[Res(\sigma _i),\sigma _i]$ with $Res(\sigma _i)$ the minimum face of $\sigma _i$ not contained in the facets $\sigma _1, \sigma _2,\ldots ,\sigma _{i-1}$, see for example [4, Sec. 2] or [21, Lect. 8]. (Here, $[a,b] = \{z\in \varGamma : a\subseteq z\subseteq b]$. Remark that $\varPsi ^O(\sigma )$ mentioned in the proof of Lemma 2 coincides with this $Res(\sigma )$.) This $Res(\sigma _i)$ is called the “restriction” of $\sigma _i$, and given by $Res(\sigma _i) = \bigcap \{\tau \in \mathcal{R}(\varGamma ) \cap \overline{\sigma _i}: \text {there is no}\, j<i\, \text {with}\, \tau \subseteq \sigma _j\}$. We construct an orientation O such that, for each ridge $\tau$ incident to $\sigma _i$, $\tau \rightarrow \sigma _i$ if $\tau \subseteq \sigma _j$ for some $j<i$, and $\tau \leftarrow \sigma _i$ otherwise. Under this orientation, we have $Res(\sigma _i) = \bigcap \{\tau \in \mathcal{R}(\varGamma ) : \tau \leftarrow \sigma _i\}$, and thus $[Res(\sigma _i),\sigma _i] = \{\eta \in \varGamma : \tau \rightarrow \sigma _i \, \text {for all}\, \tau \in \mathcal{R}(\varGamma )\, \text {with}\, \eta \subseteq \tau \subseteq \sigma _i\}= S^{O}(\sigma _i)$. Hence $\{S^O(\sigma _i): 1\le i\le t\}$ forms a partition of $\varGamma$. Here, O is obviously acyclic, and thus we have $\widetilde{G}^O(\varGamma )$ acyclic by Lemma 4, hence Lemma 5 is verified.    $\square$

Proof

(Proof of Theorem 3) The inequality $V^*\ge f(\varGamma )$ follows from Lemma 2. Further, Lemma 3 shows that the equality holds if and only if $\{S^O(\sigma ): \sigma \in \mathcal{F}(\varGamma )\}$ is a partition of $\varGamma$, and for this partition we have $\widetilde{G}(\varGamma )$ acyclic by Lemma 4. Finally, Lemma 5 shows this is equivalent to the shellability of $\varGamma$.    $\square$

3.2.2 The Case of Nonpure Simplicial Complexes

In the case of pure simplicial complexes, we defined the faces covered by a facet as ridges and considered the adjacency between facets and ridges. For the case of general simplicial complexes including nonpure complexes, we need to discriminate these faces covered by a facet into ridges and pseudoridges. Let $\varGamma$ be a simplicial complex not necessarily pure. Let $\tau$ be a face covered by some facet. We say $\tau$ is a ridge if all its superfaces (i.e., faces strictly containing $\tau$) are facets, and a pseudoridge otherwise. We denote the set of facets, ridges, and pseudoridges of $\varGamma$, by $\mathcal{F}(\varGamma )$, $\mathcal{R}(\varGamma )$, and $\mathcal{R}'(\varGamma )$, respectively.

Fig. 3.2

The simplicial complex $\varGamma$ has facets abcd, bce, cef, fg, and gh. The faces bc and f are pseudoridges. In the figure of $G(\varGamma )$, the black nodes are facets and white nodes are ridges. The pseudoridges are indicated by the node with dashed circle but they are not contained in $G(\varGamma )$

We define the facet-ridge incidence graph $G(\varGamma )$ as the bipartite graph with partite sets $\mathcal{F}(\varGamma )$ and $\mathcal{R}(\varGamma )$, where the two nodes $\sigma \in \mathcal{F}(\varGamma )$ and $\tau \in \mathcal{R}(\varGamma )$ are joined by an edge if $\sigma \supseteq \tau$. Note that we do not include pseudoridges in $G(\varGamma )$. (See Fig. 3.2 for example. Here, note that the adjacency between a facet $\sigma$ and a ridge $\tau$ occurs in $G(\varGamma )$ only when $\dim \sigma =\dim \tau +1$.)

Under this setting, we have the same statement as the pure case.

Theorem 4

For a d-dimensional (not necessarily pure) simplicial complex $\varGamma$, let us consider the following minimization problem:

$$\begin{aligned} (P3): \qquad \min&\sum _{\sigma \in \mathcal{F}(\varGamma )} 2^{{\mathrm{out}\text {-}\mathrm{deg}}(\sigma ;\, G^O\!\!(\varGamma ))} \\ {\text {s. t.} }&O\, \text {is acyclic and admissible.} \end{aligned}$$

Then, the optimum value $V^*$ of (P3) satisfies $V^*\ge f(\varGamma )$, where $f(\varGamma )$ is the number of all the faces of $\varGamma$. Further, the equality holds if and only if $\varGamma$ is shellable.

Note that Theorem 4 contains Theorem 3 as a special case.

For the proof of Theorem 4, we introduce a graph $G'(\varGamma )$ and $G'^O(\varGamma )$ as follows. The graph $G'(\varGamma )$ is the graph obtained from $G(\varGamma )$ by adding pseudoridges as nodes and edges between pseudoridges and facets such that an edge is introduced between $\tau \in \mathcal{R}'(\varGamma )$ and $\sigma \in \mathcal{F}(\varGamma )$ if $\tau \subseteq \sigma$. (Here, $\sigma$ and $\tau$ with $\dim \sigma >\dim \tau +1$ can be joined by an edge.) For an orientation O of $G(\varGamma )$, we extend the orientation to that of $G'(\varGamma )$ to obtain $G'^O(\varGamma )$. In this extended orientation, for $\tau \in \mathcal{R}'(\varGamma )$ and $\sigma \in \mathcal{F}(\varGamma )$ with $\tau \subseteq \sigma$, we orient $\tau \rightarrow \sigma$ if $\dim \sigma =\dim \tau +1$ and $\tau \leftarrow \sigma$ if $\dim \sigma >\dim \tau +1$. (See Fig. 3.3 for example.) Further, for a face $\eta \in \varGamma$, we let $G'^O_{\supseteq \eta }(\varGamma )$ be the subgraph of $G'^O(\varGamma )$ induced by the facets, ridges, and pseudoridges containing $\eta$.

Fig. 3.3

The graphs $G(\varGamma )$ and $G'(\varGamma )$, and their orientations

The proof of Theorem 4 is given completely in parallel to that of Theorem 3 by replacing $G^O_{\supseteq \eta }(\varGamma )$ by $G'^O_{\supseteq \eta }(\varGamma )$. In the definitions of $S^O(\sigma )$ and $S^{cO}(\sigma )$, we also replace $G^O(\varGamma )$ by $G'^{O}(\varGamma )$ as follows. (Formally, $S^O(\sigma )$ is the same as the original definition (1). The replacement is essential for the description of $S^{cO}(\sigma )$.)

$$\begin{aligned} S^O(\sigma )= & {} \{ \eta \in \varGamma : \sigma \rightarrow \tau \, \text {in}\, G'^O(\varGamma )\, \text {for every (pseudo)ridge}\, \tau \,\text {with}\, \eta \subseteq \tau \subseteq \sigma \} \cup \{\sigma \} \nonumber \\= & {} \{ \eta \in \varGamma : \sigma \rightarrow \tau \, \text {in}\, G^O(\varGamma )\, \text {for every ridge}\, \tau \, \text {with }\, \eta \subseteq \tau \subseteq \sigma \} \cup \{\sigma \} ,\qquad \end{aligned}$$

(3.3)

$$\begin{aligned} S^{cO}(\sigma )= & {} \overline{\sigma }-S^O(\sigma ) \nonumber \\= & {} \{ \eta \in \varGamma : \sigma \leftarrow \tau \, \text {in}\, G'^O(\varGamma )\, \text {for some (pseudo)ridge}\, \tau \, \text {with}\, \eta \subseteq \tau \subseteq \sigma \} \nonumber \\= & {} \bigcup \{\, \overline{\tau } : \tau \in \mathcal{R}(\varGamma )\cup \mathcal{R}'(\varGamma ),\, \sigma \leftarrow \tau \, \text {in}\, G'^O(\varGamma )\}. \end{aligned}$$

(3.4)

When $\{S^O(\sigma ): \sigma \in \mathcal{F}(\varGamma )\}$ is a partition, we define $\widetilde{G}(\varGamma )$ as same as the pure case. That is, we define a graph $\widetilde{G}^O(\varGamma )$ whose nodes are facets of $\varGamma$ and arcs $\sigma \rightarrow \sigma '$ are defined if there is a face $\eta \subseteq \sigma '$ with $\eta \in S^O(\sigma )$.

By this replacement, the whole argument in Theorem 3 works for the nonpure case. Theorem 4 is verified by examining the following lemmas.

Lemma 6

Let $\varGamma$ be a simplicial complex and let $\eta \in \varGamma$ and $\sigma \in \mathcal{F}(\varGamma )$. Then, for any orientation O, $\eta \in S^O(\varGamma )$ if and only if $\sigma$ is a source node in $G'^O_{\supseteq \eta }(\varGamma )$.

Lemma 7

Let $\varGamma$ be a simplicial complex and O an orientation of $G(\varGamma )$ that is acyclic and admissible. Then we have $\sum _{\sigma \in \mathcal{F}(\varGamma )} 2^{{\mathrm{out}\text {-}\mathrm{deg}}(\sigma ;\, G^O\!\!(\varGamma ))} \ge f(\varGamma ).$

Lemma 8

Let $\varGamma$ be a simplicial complex and O an orientation of $G(\varGamma )$ that is acyclic and admissible. The equality $\sum _{\sigma \in \mathcal{F}(\varGamma )} 2^{{\mathrm{out}\text {-}\mathrm{deg}}(\sigma ;\, G^O\!\!(\varGamma ))} = f(\varGamma )$ holds if and only if $\{S^O(\sigma ): \sigma \in \mathcal{F}(\varGamma )\}$ forms a partition of $\varGamma$.

Lemma 9

When $\{S^O(\sigma ): \sigma \in \mathcal{F}(\varGamma )\}$ is a partition of a simplicial complex $\varGamma$, the following are equivalent.

• $\widetilde{G}^O(\varGamma )$ is acyclic,

• $G'^O(\sigma )$ is acyclic,

• $G^O(\sigma )$ is acyclic.

Lemma 10

For a simplicial complex $\varGamma$, there exists an acyclic and admissible orientation O of $G(\varGamma )$ such that $\{S^O(\sigma ): \sigma \in \mathcal{F}\}$ is a partition of $\varGamma$ with $\widetilde{G}(\varGamma )$ acyclic if and only if $\varGamma$ is shellable.

The proofs of Lemmas 6 to 10 are completely the same as the pure case. The proof of Theorem 4 is also the same as the pure case.

Proof

(Proof of Theorem 4) The inequality $V^*\ge f(\varGamma )$ follows from Lemma 7. Further, Lemma 8 shows that the equality holds if and only if $\{S^O(\sigma ): \sigma \in \mathcal{F}(\varGamma )\}$ is a partition of $\varGamma$, and for this partition we have $\widetilde{G}(\varGamma )$ acyclic by Lemma 9. Finally, Lemma 10 shows this is equivalent to the shellability of $\varGamma$.    $\square$

The trick of generalizing the pure case of Theorem 3 to the nonpure case of Theorem 4 can be understood from the well-known “Rearrangement lemma” of Björner and Wachs [4, Lemma 2.6]. According to the Rearrangement lemma, any shelling of a shellable simplicial complex $\varGamma$ can be rearranged such that the facets in the shelling are ordered in a descending order with respect to dimension, without changing the restriction maps. In our theorems, setting restriction maps corresponds to giving orientations to the facet-ridge incidence graph, and shellings with fixed restriction maps are derived as linear extensions of $G'^O(\varGamma )$ restricted to facets. As remarked in [4, p. 1305], (after the rearrangement) any shelling of a nonpure simplicial complex of dimension d has the structure such that first d-dimensional facets are shelled, and after that $(d-1)$-dimensional facets follow extending a shelling of the $(d-1)$-skeleton of the d-dimensional part, and then $(d-2)$-dimensional facets follow in the same way. This process continues until all the facets are shelled. The orientation of $G'^O(\varGamma )$ extending $G^O(\varGamma )$ forces this structure.

The result of Theorem 4 is first shown in [13], and also later appears in [11] with a generalized framework for cell complexes.

Remark 1

In the optimization problem (P2) or (P3), in the optimal orientation, every ridge has in-degree equal to 1. To see this, assume in an acyclic and admissible orientation O, there is a ridge node $\tau$ that has in-degree $k\ge 2$ with $\sigma _1\rightarrow \tau , \sigma _2\rightarrow \tau , \ldots \sigma _k\rightarrow \tau$. Then, we can observe there is at least one $\sigma _i$ such that reversing the orientation to $\sigma _i\leftarrow \tau$ remains the orientation acyclic (and obviously also admissible) as follows. If reversing $\sigma _1\rightarrow \tau$ to $\sigma _1\leftarrow \tau$ in O makes a cycle, then there should exist a directed path from $\sigma _1$ to some $\sigma _{i_1}$. If reversing $\sigma _{i_1}\rightarrow \tau$ to $\sigma _{i_1}\leftarrow \tau$ in O makes a cycle, then there should exist a directed path from $\sigma _{i_1}$ to some $\sigma _{i_2}$. By continuing this way, at some $l\le k$, we will find a $\sigma _{i_l}$ such that reversing $\sigma _{i_l}\rightarrow \tau$ to $\sigma _{i_l}\leftarrow \tau$ in O remain the orientation acyclic, since otherwise we have a cycle $\sigma _{i_j}\rightsquigarrow \sigma _{i_{j+1}}\rightsquigarrow \sigma _{i_{j+2}}\rightsquigarrow \cdots \rightsquigarrow \sigma _{i_l}=\sigma _{i_j}$ because k is finite. Since reversing one $\sigma _{i_l}\rightarrow \tau$ to $\sigma _{i_l}\leftarrow \tau$ makes the value of the objective function smaller, we conclude that an orientation O cannot be an optimal solution if there is a ridge node with in-degree $\ge 2$.

Remark 2

The optimization problem (P1) in the setting of Theorem 2 (setting $G=G(P)$ for a simple polytope P) is in fact a special case of the problem (P2) in Theorem 3. For a simple polytope P, let $P^*$ be the polar dual of P. $P^*$ is a simplicial polytope, and thus its boundary $\partial P^*$ is a simplicial complex. Then, the facet-ridge incidence graph $G(\partial P^*)$ is isomorphic to a subdivision of the graph G(P) introducing one node (corresponding to a ridge) on each edge. Note that each ridge node in $G(\partial P^*)$ has degree 2. Here, as is explained in the previous remark, the optimal orientation of the problem (P2) has $\text {in-deg}(\tau )= 1$ for each ridge node $\tau$. Since each ridge in $G(\partial P^*)$ has exactly two adjacent facets, the orientation optimal for (P2) can be naturally translated to an orientation for (P1), and the resulted orientation is an optimal orientation for (P1). This relation shows that the optimal orientations of (P1) give shellings of $P^*$ as their linear extensions. Such a relation between good orientations of simple polytopes and shellings of their duals has been known already, see [20] for example.

The optimization problem (P1) can be used for characterizing shellability of pseudomanifolds. A (closed) pseudomanifold is a pure simplicial complex such that each ridge is contained by exactly two facets. As is noted in Sect. 3.1, the recognition of shellability of pseudomanifolds is easy for the 2-dimensional case [8], but no efficient algorithms are known for 3-dimensional and higher cases. Since each ridge node has exactly two facet nodes in the facet-ridge incidence graph of a pseudomanifold, (P2) can be reduced to (P1) for the case of pseudomanifolds by the same reason as for $\partial P^*$. The facet-ridge incidence graph of a d-dimensional pseudomanifold is a $(d+1)$-regular graph. This suggests that the problem (P1) is likely a difficult optimization problem even if we restrict the graph G to be a k-regular graph with $k\ge 4$.

3.3 Cubical Complexes and Acyclic Partitions

A simplicial complex, discussed in Sect. 3.2 is a cell complex in which each cell is a simplex. Likewise, a cubical complex is a cell complex in which each cell is (combinatorially equivalent to) a (hyper)cube. In this section, we develop a theory for cubical complexes similar to that for simplicial complexes. (More precisely, what we are considering here is a regular CW complex in which each cell is combinatorially equivalent to a (hyper)cube. Usually, it is required that cubical complexes satisfy the intersection property, i.e., the nonempty intersection of two cells is always a cell in the complex, but we do not need this condition.) This result appeared in Hachimori [11]. We here follow the discussion in [11].

Recall the story of our theory for simplicial complexes in the previous section. In the optimization problem of (P2) or (P3), the objective function $\sum _{\sigma \in \mathcal{F}(\varGamma )} 2^{\text {out-deg}(\sigma ; G^O(\varGamma ))}$ is equal to $\sum _{\sigma \in \mathcal{F}(\varGamma )} |S^O(\sigma )|$, where $S^O(\sigma )$ is the set of faces of a facet $\sigma$ generated by the ridges $\tau$ with orientation $\sigma \rightarrow \tau$. On the other hand, the constraint of the optimization problem that the orientations must be acyclic and admissible (i.e., each ridge has in-degree at least 1) assures that the family $\{S^O(\sigma )\}$ always forms a covering of $\varGamma$. Hence, the condition that the minimum value of the optimization problem equals the number of the faces of $\varGamma$ turns out to be equivalent to that $\{S^O(\sigma ): \sigma \in \mathcal{F}(\varGamma )\}$ is a partition with an acyclic structure, i.e., such that the graph $\widetilde{G}^O(\varGamma )$ is acyclic. We say such a partition an “acyclic partition.” In this story for simplicial complexes, the existence of acyclic partitions happens to be equivalent to be shellable, and this concludes the proof of Theorem 4.

For cubical complexes, the same story can be developed except the last part. We define $G(\varGamma )$ and $G'(\varGamma )$ analogously to Sect. 3.2 with the same definition of facets, ridges, and pseudoridges. For a given orientation O of $G(\varGamma )$, we extend the orientation to $G'(\varGamma )$ by the same rule. We say an orientation O is admissible if $\text {in-deg}(\tau )\ge 1$ for every $\tau \in \mathcal{R}(\varGamma )$. In a cubical complex $\varGamma$, each facet $\sigma$ contains $\dim \sigma$ antipodal pairs of (pseudo)ridges of dimension $\dim \sigma -1$. (For example, a three-dimensional cube has three antipodal pairs of two-dimensional (pseudo)ridges.) According to the orientation O of $G(\varGamma )$ and thus of $G'(\varGamma )$, we define $(t_0^O(\varGamma ), t_1^O(\varGamma ),t_2^O(\varGamma ))$ the type of the facet $\sigma$, where

$$\begin{aligned} t_0^O(\sigma )= & {} \# \text { of antipodal pairs of (pseudo)ridges}\, \{\tau ,\tau '\}\, \text {with}\, \sigma \rightarrow \tau \, \text {and}\, \sigma \rightarrow \tau ', \\ t_2^O(\sigma )= & {} \# \text { of antipodal pairs of (pseudo)ridges}\, \{\tau ,\tau '\}\, \text {with}\, \sigma \leftarrow \tau \, \text {and}\, \sigma \leftarrow \tau ', \\ t_1^O(\sigma )= & {} \dim \sigma - t_0^O(\sigma )-t_2^O(\sigma ). \end{aligned}$$

For cubical complexes, we develop the theory on $\check{\varGamma } = \varGamma -\emptyset$ instead of $\varGamma$. For $\sigma \in \mathcal{{F}}(\varGamma )$, we define $\check{S}^O(\sigma )=S^O(\sigma )-\emptyset$ and $\check{S}^{cO}(\sigma )=\overline{\sigma }-\check{S}^O(\sigma )$. As same as in the case of simplicial complexes, define a graph $\widetilde{G}^O(\varGamma )$ whose nodes are facets of $\varGamma$ and arc $\sigma \rightarrow \sigma '$ is defined if there is a face $\eta \subseteq \sigma '$ with $\eta \in \check{S}^O(\sigma )$. If there exists an orientation O for a cubical complex $\varGamma$ such that $\{\check{S}^O(\sigma ): \sigma \in \mathcal{{F}}(\varGamma )\}$ is a partition of $\check{\varGamma }$ with $\widetilde{G}^O(\varGamma )$ acyclic, we say $\check{\varGamma }$ has an acyclic partition. Now we have the following theorem.

Theorem 5

For a cubical complex $\varGamma$, let us consider the following minimization problem:

$$\begin{aligned} (P4): \qquad \min&\sum _{\sigma \in \mathcal{{F}}(\varGamma )} 2^{t_1^O(\sigma )}3^{t_0^O(\sigma )} \\ {\text {s. t.} }&O\, \text {is acyclic and admissible.} \end{aligned}$$

Then the optimum value $V^*$ of (P4) satisfies $V^*\ge f(\check{\varGamma })$, where $\check{\varGamma } = \varGamma - \emptyset$ and $f(\check{\varGamma })$ is the number of all the faces of $\check{\varGamma }$. Further, the equality holds if and only if $\check{\varGamma }$ has an acyclic partition.

The proof of this theorem is completely the same as Theorem 4. Here, in the objective function of (P4), $2^{t_1^O(\sigma )}3^{t_0^O(\sigma )}$ equals the number of faces contained in $\check{S}^O(\sigma )$. (One reason we removed the empty set and replaced $\varGamma$ by $\check{\varGamma }$ is to represent the number of faces by this formula.) In Theorem 4 of the case of simplicial complexes, the existence of acyclic partitions is equivalent to shellability as Lemma 10. Unfortunately, however, we lack this equivalence for cubical complexes.

Remark 3

$S^O(\sigma )$ and $\check{S}^O(\sigma )$ differ only when $S^O(\sigma )=\overline{\sigma }$, in this case $\check{S}(\sigma ) = S(\sigma )-\emptyset$. The difference between an acyclic partition of $\varGamma$ and an acyclic partition of $\check{\varGamma }$ is the treatment of the empty set. For an acyclic partition of $\varGamma$, we require that the empty set should be contained in exactly one $S^O(\sigma )$. This requires that the oriented graph $G^O(\varGamma )$ has exactly one source node. On the other hand, for an acyclic partition of $\check{\varGamma }$, we remove the empty set from $\check{\varGamma }$ and from each $\check{S}^O(\sigma )$. Hence $G^O(\sigma )$ can have more than one source nodes. If O induces an acyclic partition of $\check{\varGamma }$ such that $G^O(\varGamma )$ has only one source node, then the orientation O also induces an acyclic partition of $\varGamma$.

For cubical complexes, more generally for a general class of cell complexes called “regular CW complexes” (including polytopal complexes), shellability is defined in the following recursive form.

Definition 2

(Björner and Wachs [5, Sec. 13]) In a regular CW complex $\varGamma$, an ordering $\sigma _1, \sigma _2, \ldots , \sigma _t$ of the facets of $\varGamma$ is called a shelling if either $\dim \varGamma =0$ or if $\dim \varGamma \ge 1$ and satisfies the following:

• (i) $\partial \sigma _1$ has a shelling,

• (ii) $\partial \sigma _i\cap (\bigcup _{j=1}^{i-1}\partial \sigma _i)$ is pure and $(\dim \sigma _i-1)$-dimensional, for $2\le i\le t$,

• (iii) $\partial \sigma _i$ has a shelling such that facets of $\partial \sigma _i$ in $\partial \sigma _i\cap (\bigcup _{j=1}^{i-1}\partial \sigma _i)$ come first in the shelling, for $2\le i\le t$,

where $\partial \sigma$ is the boundary complex of $\sigma$, i.e., the subcomplex of $\overline{\sigma }$ consisting of all proper faces of $\sigma$ (i.e., all the faces of $\sigma$ except $\sigma$ itself). $\varGamma$ is shellable if it has a shelling.

This kind of generalized version of shellability has been studied classically for pure complexes, see Björner and Wachs [3]. For a comprehensive exposition of shellability for pure polytopal complexes, see Ziegler [21, Lecture 8]. For regular CW complexes, see Björner [1].

The equivalence of acyclic partition and shellability like Lemma 10 is valid only in the class of simplicial complexes. Unfortunately, this equivalence does not hold for general cell complexes. For example, the simple example in Fig. 3.4 has an acyclic partition with the orientation shown in the figure, but it is not shellable. Hence, the optimization in Theorem 5 does not characterize shellability.

Fig. 3.4

A nonshellable cubical complex that has an acyclic partition

For cubical complexes, however, we can retrieve some topological information as follows. Let O be an orientation on a cubical complex $\varGamma$. We say a facet $\sigma$ is critical if $t_1^O(\sigma )=0$, and count the number of critical facets as follows:

$$ p_i^O(\varGamma ) = \#\{\sigma \in \mathcal{F}(\varGamma ) : \sigma \, \text {is critical and}\, t_2^O(\sigma )=i \}. $$

We say that a facet is a critical facet of index i if $\sigma$ is critical and $t_2^O(\sigma )=i$. Thus, $p_i^O(\varGamma )$ is the number of critical facets of index i. We have the following theorem.

Theorem 6

Let $\varGamma$ be a cubical complex, and O an orientation such that $\{\check{S}^O(\sigma ) : \sigma \in \mathcal{F}(\varGamma )\}$ is an acyclic partition. Then we have the following inequalities:

$$\begin{aligned} \beta _k(\varGamma ) - \beta _{k-1}(\varGamma ) + \cdots m + (-1)^{k-1} \beta _0(\varGamma ) \le p^O_k(\varGamma ) - p^O_{k-1}(\varGamma ) + \cdots m + (-1)^{k-1} p^O_0(\varGamma ) , \\ (0\le k \le \dim \varGamma ) \end{aligned}$$

$$\begin{aligned}&\chi (\varGamma ) = p^O_0(\varGamma ) - p^O_1(\varGamma ) + \cdots m + (-1)^{\dim \varGamma -1} p^O_{\dim \varGamma }(\varGamma ), \\& \beta _i \le p^O_i, \quad (0\le i\le \dim \varGamma ) \end{aligned}$$

where $\beta _i(\varGamma )$ is the ith Betti number of $\varGamma$ and $\chi (\varGamma )$ is the Euler characteristic of $\varGamma$.

Proof

Let $\sigma _1,\sigma _2,\ldots ,\sigma _t$ be a linear extension of $\widetilde{G}^O(\varGamma )$, and $\varGamma _i = \bigcup _{j=1}^i\overline{\sigma }_j$. As same as the discussion in the proof of Theorem 3, $\varGamma _{i-1}\cap \overline{\sigma _i} = \check{S}^{cO}(\sigma _i)$. For each i, $\varGamma _i$ is a cubical complex and we observe the following.

• If $t_1^O(\sigma _i)\ge 1$, then $\check{S}^{cO}$ is homeomorphic to a ball (of dimension $\dim \sigma _i$), and thus $\varGamma _i$ is homotopy equivalent to $\varGamma _{i-1}$. (This can be verified from the fact that $S^{cO}(\sigma _i)$ is shellable, see for example [21, Exercise 8.1 (i)].)

• If $t_1^O(\sigma _i)=0$, then $\varGamma _i$ is a union of $\varGamma _{i-1}$ and $\overline{\sigma }_i$, where $\overline{\sigma }_i$ is homeomorphic to the direct product of intervals $I^{t_0^O(\sigma _i)}\times I^{t_2^O(\sigma _i)}$ with the intersection $\varGamma _{i-1}\cap \overline{\sigma }_i$ corresponds to $I^{t_0(\sigma _i)}\times \{0,1\}^{t_2(\sigma _i)}$. Thus, $\varGamma _i$ is homotopy equivalent to the union of $\varGamma _{i-1}$ and a $t^O_2(\sigma _i)$-dimensional cell (i.e., adding a $t^O_2(\sigma _i)$-handle to $\varGamma _i$).

By these observations, we conclude that $\varGamma = \varGamma _t$ is homotopy equivalent to a CW complex with $p_i$ cells for each i. (See Fig. 3.5 for a simple illustrative example of this procedure.) The inequalities follow from this by following the standard argument in Morse theory, see for example [10, 17].    $\square$

Fig. 3.5

An acyclic partition of a cubical complex homotopy equivalent to a cell complex with one 0-cell and one 1-cell

As we see in the proof of Theorem 6, acyclic partitions can be seen as a kind of discrete analogue of Morse functions on smooth manifolds. The critical facets of index i correspond to the critical points of index i of Morse functions. There is a famous discrete analogue of Morse theory by Forman [10], but our cubical analogue seems different from this. The similarity to Morse function can be observed further as follows. This is an analogue of the “Sphere Theorem”.

Theorem 7

Let $\varGamma$ be a cubical decomposition of a closed manifold (i.e., a cubical complex homeomorphic to a closed manifold). If $\varGamma$ has an acyclic partition such that $p_0=p_{\dim \varGamma }=1$ and $p_i=0$ for $0<i<\dim \varGamma$, then $\varGamma$ is a PL-sphere.

Proof

This is just a consequence of that $\varGamma$ is shellable if $p_0=1$ and $p_i=0$ for $0<i<\dim \varGamma$, which is easy to verify. It is well known that a regular CW decomposition of a closed manifold is a PL-sphere if it is shellable, see Björner [1] for example.    $\square$

3.4 Optimization of Orientation of Graphs Without Acyclicity Constraint

As is remarked in the end of Sect. 3.2, the problem (P1) seems a difficult optimization problem in general. The difficulty of the problem (P1) lies in the constraint that the orientations must be acyclic. Without this constraint, the problem is easy to solve. To see this, let us consider the following optimization problem.

$$\begin{aligned} (P5): \qquad \min&\sum _{v\in G} 2^{\text {out-deg}(v;\, G^O)} \quad ( =: \varphi (O) ) \\ {\text {s}.~\text {t}. }&O\, \text {is any orientation.} \end{aligned}$$

Lemma 11

An orientation O is optimal for the problem (P5) if and only if there is no directed path in $G^O$ from u to v for any $u,v\in V(G)$ with ${\mathrm{out}\text {-}\mathrm{deg}}(v) \le {\mathrm{out}\text {-}\mathrm{deg}}(u)-2$.

Proof

The “only if” part is easy. If there is a directed path p in $G^O$ from u to v, let $O_p$ be the orientation reversing the orientations of edges on the path p in O. Then we have

$$\begin{aligned} \text {out-deg}(u; G^{O_p})= & {} \text {out-deg}(u; G^O)-1, \\ \text {out-deg}(v; G^{O_p})= & {} \text {out-deg}(v; G^O)+1, \\ \text {out-deg}(w; G^{O_p})= & {} \text {out-deg}(w; G^O) \qquad (^\forall w\in V(G)-\{u,x\}). \end{aligned}$$

By the condition $\text {out-deg}(v) \le \text {out-deg}(u)-2$, it is verified that $\varphi (O_p)< \varphi (O)$ since $2^a+2^b > 2^{a+1}+2^{b-1}$ if $a\le b-2$, hence O is not optimal.

For the “if” part, assume an orientation O has no directed path from u to v for any $u,v\in V(G)$ with $\text {out-deg}(v) \le \text {out-deg}(u)-2$, and $O^*$ is an optimal orientation with $\varphi (O)> \varphi (O^*)$. Let $G^{(O,O^*)}$ be the subgraph of G induced by the edges of G with different orientations in O and $O^*$, and $G^{(O,O^*)O}$ ($G^{(O,O^*)O^*}$) the graph $G^{(O,O^*)}$ oriented by O (by $O^*$). Here, we observe that we can choose $O^*$ such that $G^{(O,O^*)O^*}$ has no directed cycles: if there is a directed cycle in $G^{(O,O^*)O^*}$, we can reverse the orientations of the edges in $O^*$ along the cycle without changing the value of $\varphi (O^*)$, and we get a required $O^*$ by continuing this. Further, we choose $O^*$ such that the number of edges of $G^{(O,O^*)}$ is minimum. Since $G^{(O,O^*)O^*}$ is acyclic and thus $G^{(O,O^*)O}$ is also acyclic, we can find a path $q=x\rightsquigarrow y$ on $G^{(O,O^*)}$ such that, in $G^{(O,O^*)O}$, x is a source, y is a sink, and the path q is a directed path from x to y. Here, we have $\text {out-deg}(x; G^{O^*})\le \text {out-deg}(x; G^O)-1$ and $\text {out-deg}(y; G^{O^*})\ge \text {out-deg}(y; G^{O})+1$ since x is a source and y is a sink in $G^{(O,O^*)O}$. We have $\text {out-deg}(y; G^O) \ge \text {out-deg}(x; G^O)-1$ by the assumption on O. Hence we have

$$\text {out-deg}(x; G^{O^*})\le \text {out-deg}(x; G^{O})-1\le \text {out-deg}(y;G^O) \le \text {out-deg}(y; G^{O^*})-1. $$

Now let $O^*_q$ be the orientation reversing the edges on the path q in $O^*$. If $\text {out-deg}(x; O^*) \le \text {out-deg}(y; O^*)-2$, we have $f(O^*_q)<f(O^*)$, a contradiction to the optimality of $O^*$. If $\text {out-deg}(x; O^*) = \text {out-deg}(y; O^*)-1$, we have $f(O^*_q)=f(O^*)$ with $|E(G^{(O,O^*_q)}|< |E(G^{(O,O^*)}|$, a contradiction to the minimality of the number of edges of $G^{(O,O^*)}$. This completes the proof of Lemma 11.    $\square$

Theorem 8

The problem (P5) can be solved in a polynomial time.

Proof

To solve (P5), Lemma 11 suggests the following easy algorithm. First, start from an arbitrary orientation of G. Then, find a directed path $u\rightsquigarrow v$ in the orientation such that $\text {out-deg}(v)\le \text {out-deg}(u)-2$ and reverse the orientations of edges along the path. Continue this until there is no such a directed path found. The resulted orientation is an optimal solution of (P5). Since finding such a path in each repetition can be easily done in a polynomial time, what remains is to evaluate the number of repetitions in this algorithm. For this evaluation, consider a function

$$ F(O) = \sum _{\{u,v\}\in \left( {\begin{array}{c}V(G)\\ 2\end{array}}\right) } |\text {out-deg}(u; G^O) - \text {out-deg}(v; G^O)|. $$

When the orientations of the edges are reversed along a path $p = x \rightsquigarrow y$ with $\text {out-deg}(y)\le \text {out-deg}(x)-2$, $\text {out-deg}(x)$ decreases and $\text {out-deg}(y)$ increases by one respectively, and thus we have the following.

• If $w\in V(G)-\{x,y\}$ has $\text {out-deg}(w; G^O)\le \text {out-deg}(y; G^O)$ or $\text {out-deg}(w; G^O) \ge \text {out-deg}(x; G^O)$, then

  $$\begin{aligned} \bigg ( |\text {out-deg}(x; G^O)-\text {out-deg}(w; G^O)|+ |\text {out-deg}(y; G^O)-\text {out-deg}(w; G^O)|\bigg ) \qquad \qquad \\ - \bigg (|\text {out-deg}(x; G^{O_p})-\text {out-deg}(w; G^{O_p})|+ |\text {out-deg}(y; G^{O_p})-\text {out-deg}(w; G^{O_p})|\bigg )\!\!=\!\! & {} 0. \end{aligned}$$

• If $w\in V(G)-\{x,y\}$ has $\text {out-deg}(y; G^O)< \text {out-deg}(w; G^O) < \text {out-deg}(x; G^O)$, then

  $$\begin{aligned} \bigg ( |\text {out-deg}(x; G^O)-\text {out-deg}(w; G^O)|+ |\text {out-deg}(y; G^O)-\text {out-deg}(w; G^O)|\bigg ) \qquad \qquad \\ - \bigg (|\text {out-deg}(x; G^{O_p})-\text {out-deg}(w; G^{O_p})|+ |\text {out-deg}(y; G^{O_p})-\text {out-deg}(w; G^{O_p})|\bigg )\!\!=\!\! & {} 2. \end{aligned}$$

• We have $\,|\text {out-deg}(x; G^O)-\text {out-deg}(y; G^O)|- |\text {out-deg}(x; G^{O_p})-\text {out-deg}(y; G^{O_p})|= 2 \; (*),$ and $|\text {out-deg}(w; G^O)-\text {out-deg}(z; G^O)|$ remains unchanged for $w,z\in V(G)-\{x,y\}$.

Thus, in total, we have $F(O)-F(O_p) \ge 2$ (from $(*)$). On the other hand, for any orientation O we have $0\le F(O)< n^3$, hence the number of repetition is bounded by $n^3/2$. This completes the proof of Theorem 8.    $\square$

Lemma 11 and Theorem 8 relies only on the convexity property of the function $2^x$ in the summand that $2^a+2^b > 2^{a+1}+2^{b-1}$ for $a\le b-2$. Likewise, the same holds if the objective function is a function $\psi$ satisfying the condition that $\psi (O) - \psi (O') > 0$ if the out-degrees of the nodes are the same in O and $O'$ except u and v, $\text {out-deg}(u; G^O)\le \text {out-deg}(v; G^O)-2$, $\text {out-deg}(u; G^{O'})=\text {out-deg}(u; G^{O})+1$, and $\text {out-deg}(v; G^{O'})=\text {out-deg}(v; G^O)-1$. Also, we can apply the same algorithm for the problems (P2)-(P4) without acyclicity constraint starting from an orientation with $\text {out-deg}(\tau )=1$ for all $\tau \in \mathcal{R}(\varGamma )$ and finding a directed path $\sigma \rightsquigarrow \sigma '$ with $\sigma ,\sigma '\in \mathcal{F}(\varGamma )$ in each repetition. (Note that we have $\text {out-deg}(\tau )=1$ for all $\tau \in \mathcal{R}(\varGamma )$ in the optimal orientation as same as remarked in the end of Sect. 3.2.2.)

To conclude this chapter, we list some open problems to be studied.

For the original optimization problem (P1), such a good property as Lemma 11 does not likely hold and this makes the problem difficult. As is remarked before, (P1) seems difficult even if we restrict the graph G to be k-regular with $k\ge 4$. To look for a nontrivial class of graphs for which optimization problems like (P1)-(P4) can be solved in a polynomial time is an interesting problem. For example, is (P1) efficiently solvable for 3-regular graphs?

On the other hand, we believe the problems (P1)-(P4) are difficult to solve in general, but we do not have NP-hardness results for these problems. To show NP-hardness of these problems is an important problem.

Our results in Sect. 3.2 are based on the fact that the optimization for problems (P2) or (P3) gives an acyclic partition of a given simplicial complex. Such a partition without acyclicity is called partitionability and have been an important topic of study, see Kleinschmidt and Onn [15], Stanley [18, Ch. III.2], etc. See also Duval, Goeckner, Klivans, and Martin [9] for recent progress. Signability, introduced by Kleinschmidt and Onn [15] as a generalization of partitionability, is very closely related to our discussion in Sects. 3.2 and 3.3. Lemma 1 is essentially equivalent to the relation between partitionability and signability shown in [15] where the orientations of edges $\sigma \rightarrow \tau$ and $\sigma \leftarrow \tau$ are replaced to the assignment of signs $+$ and − to the covering relations between facets $\sigma$ and ridges $\tau$. Though partitionability is a property removing the acyclicity structure from shellability, unfortunately partitionability cannot be represented by the optimization problems just removing acyclicity constraints from (P2)-(P4) as is considered in (P5). To assure partitionability, $G^O(\varGamma )_{\supseteq \eta }$ should have exactly one source facet node for all faces $\eta \in \varGamma$. In Theorem 3, for this requirement, acyclicity assures that each $G^O(\varGamma )_{\supseteq \eta }$ has at least one source facet node, and optimization reduces it to exactly equal to one node. For partitionability, the lack of acyclicity makes it difficult to assure $G^O(\varGamma )_{\supseteq \eta }$ to have at least one source facet node. How to treat partitionability in a similar framework is a difficult problem.

Related to shellability and partitionability, Hachimori and Kashiwabara [12] introduced hereditary-shellability and hereditary-partitionability, which are properties requiring the restriction to any vertex subset has the property to be shellable and partitionable. (Other related hereditary properties are defined in the same way.) This is motivated by the notion of obstructions introduced by Wachs [19]. To treat these hereditary properties in the optimization setting is a quite open problem.

Finally, to look for other topics that can be formulated using optimizations on orientations of graphs will be an interesting problem.