# Predicting Online Item-Choice Behavior: A Shape-Restricted Regression Approach
## 5 Algorithms for Transitive Reduction
### Constructive Algorithms  
Let \((\Gamma,E^{*}_{\textsc{UM}})\) be a transitive reduction of a directed graph \((\Gamma,E_{\textsc{UM}})\) representing the poset \((\Gamma,\preceq_{\textsc{UM}})\). Then, the transitive reduction can be characterized by the following theorem:  
Figure 2: Directed graph representations of the poset \((\Gamma,\preceq_{\textsc{US}})\) with \((n,m)=(3,2)\). **Theorem 3**. : _Suppose \((\mathbf{u},\mathbf{v})\in\Gamma\times\Gamma\). Then, \((\mathbf{u},\mathbf{v})\in E^{*}_{\textsc{Um}}\) holds if and only if any one of the following conditions is fulfilled:_  
\[ \begin{array}{l}(\textsc{UM1})\ \mathbf{v}=\textsc{Up}(\mathbf{u},n)\ \text{, or}\\ (\textsc{UM2})\ \text{there exists }s\in[1,n]\ \text{such that }\mathbf{v}=\textsc{Move}(\mathbf{u},s,s+1)\ \text{.}\end{array} \]  
Proof. : See Appendix A.1. Theorem 3 provides a constructive algorithm that directly computes the transitive reduction \((\Gamma,E^{*}_{\textsc{Um}})\) without generating an exhaustive directed graph \((\Gamma,E)\). Our algorithm is based on the breadth-first search [58]. Specifically, we start with a node list \(L=\{(0,0,\ldots,0)\}\subseteq\Gamma\). At each iteration of the algorithm, we choose \(\mathbf{u}\in L\), enumerate \(\mathbf{v}\in\Gamma\) such that \((\mathbf{u},\mathbf{v})\in E^{*}_{\textsc{Um}}\), and add these nodes to \(L\). Table 2 shows this enumeration process for \(\mathbf{u}=(0,2,1)\) with \((n,m)=(3,2)\). The operations Up and Move generate \(\mathbf{v}\in\{(1,2,1),(0,2,2),(1,1,1),(1,2,0)\}\), which amounts to searching edges \((\mathbf{u},\mathbf{v})\) in Figure 0(a). We next check whether each \(\mathbf{v}\) satisfies conditions (UM1) or (UM2) in Theorem 3. As shown in Table 2, we choose \(\mathbf{v}\in\{(0,2,2),(1,1,1)\}\) and add them to list \(L\); this amounts to enumerating edges \((\mathbf{u},\mathbf{v})\) in Figure 0(b). Appendix B.1 presents a pseudocode for our constructive algorithm (Algorithm A1). Recalling the time complexity analysis of the breadth-first search [58], one readily sees that the time complexity of Algorithm A1 is \(\mathcal{O}(n(m+1)^{n})\), which is much smaller than \(\mathcal{O}((m+1)^{2.3729n})\), as achieved by the general-purpose algorithm [57], especially when \(n\) is very large. Next, we focus on the transitive reduction \((\Gamma,E^{*}_{\textsc{US}})\) of a directed graph \((\Gamma,E_{\textsc{US}})\) representing the poset \((\Gamma,\preceq_{\textsc{US}})\). The transitive reduction can then be characterized by the following theorem:  
**Theorem 4**. : _Suppose \((\mathbf{u},\mathbf{v})\in\Gamma\times\Gamma\). Then, \((\mathbf{u},\mathbf{v})\in E^{*}_{\textsc{US}}\) holds if and only if any one of the following conditions is fulfilled:_  
\[ \begin{array}{l}(\textsc{US1})\ \text{there exists }s\in[1,n]\ \text{such that }\mathbf{v}=\textsc{Up}(\mathbf{u},s)\ \text{and}\ u_{j}\
ot\in\{u_{s},u_{s}+1\}\ \text{for all}\ j\in[s+1,n]\ \text{, or}\\ (\textsc{US2})\ \text{there exists }(s,t)\in[1,n]\ \text{such that }\mathbf{v}=\textsc{Swap}(\mathbf{u},s,t)\ \text{and}\ u_{j}\
ot\in[u_{s},u_{t}]\ \text{for all}\ j\in[s+1,t-1]\ \text{.}\end{array} \]  
Proof. : See Appendix A.2. Theorem 4 also gives a constructive algorithm for computing the transitive reduction \((\Gamma,E^{*}_{\textsc{US}})\). Let us again consider \(\mathbf{u}=(0,2,1)\) as an example with \((n,m)=(3,2)\). As shown in Table 3, operations Up and Swap generate \(\mathbf{v}\in\{(1,2,1),(0,2,2),(2,0,1),(1,2,0)\}\), and we choose \(\mathbf{v}\in\{(0,2,2),(2,0,1),(1,2,0)\}\) (see also Figure 1(a),(b)). Appendix B.2 presents the pseudocode for our constructive algorithm (Algorithm A2). Its time complexity is estimated to be \(\mathcal{O}(n^{2}(m+1)^{n})\), which is larger than that of Algorithm A1 but much smaller than that of the general-purpose algorithm [57], especially when \(n\) is very large.