1 Introduction↩︎

Unconstrained binary polynomial optimization (or in short BPO) aims at finding the maximum value of a polynomial expression depending on \(n\) binary variables. We use \(\mathbb{B}=\{0,1\}\) to denote the binary values, \(V=[n]=\{1,2,\dots,n\}\) to denote the index set of the variables, and use \(x_v\in \mathbb{B}\) for \(v\in V\) for the binary variables in our problem. We denote by \(\mathbf{x}=(x_v\mid v\in V)\) a vector of these binary variables, by \(\mathbb{B}^V\) the set of binary vectors, by \(\mathbb{R}\) the set of real numbers, by \(\mathbb{Q}\) the set of rational numbers, by \(\mathbb{Z}\) the set of integers, and by \(\mathbb{Z}_+\) the set of nonnegative integers.

To a given hypergraph \(\mathcal{H}\subseteq 2^V\) (that is a collection of subsets of \(V\)) and rational vector \(\mathbf{c}=(c_H\mid H\in \mathcal{H})\in \mathbb{Q}^{\mathcal{H}}\) we associate a multilinear polynomial function \[\label{e-multlinpoly} f_{\mathcal{H},\mathbf{c}}(\mathbf{x}) ~=~ \sum_{H\in \mathcal{H}} c_H \prod_{v\in H} x_v.\tag{1}\] With this notation, we can formulate the BPO problem as \[\label{e-BPO} \max_{\mathbf{x}\in\mathbb{B}^V} f_{\mathcal{H},\mathbf{c}}(\mathbf{x}).\tag{2}\] Note that for a binary value \(x\in \mathbb{B}\) we have \(x^k=x\) for all integers \(k\geq 1\), and thus any polynomial expression in these variables is equivalent to a multilinear one. Note also that \(\mathcal{H}\) is not assumed to be a Sperner hypergraph, and in particular, it may contain a hyperedge of size \(0\) corresponding to a constant term, and hyperedges of size \(1\) corresponding to the linear terms of \(f_{\mathcal{H},\mathbf{c}}\), etc.

A mapping \(g:\mathbb{B}^V\mapsto \mathbb{R}\) is called a pseudo-Boolean function. It is well-known that every pseudo-Boolean function has a unique multilinear polynomial representation with some hypergraph \(\mathcal{H}\subseteq 2^V\) and coefficients \(\mathbf{c}\in \mathbb{R}^\mathcal{H}\), see [1], [2]. Problem BPO is a special case of pseudo Boolean optimization³, and it contains unconstrained quadratic binary optimization (QUBO) as a special case. Thus, BPO is an NP-hard optimization class, since QUBO is known to include several well-known NP-complete combinatorial optimization problems, see e.g. [3], [4] for a more comprehensive list of related problems, equivalences, and applications.

The structure of the hypergraph \(\mathcal{H}\) plays an important role in the hardness/easiness of BPO. The so called basic-algorithm introduced by [1], [5] for pseudo-Boolean optimization was shown to be polynomial for BPO problems when \(\mathcal{H}\) has bounded tree-width [6]. The standard linearization technique was shown to lead to an integral polytope, and hence to polynomial time solvability of BPO when \(\mathcal{H}\) is Berge-acycic [7]. Unlike for graphs, acyclicity is not a uniquely definable notion for hypergraphs, see e.g., [8]–[12]. For the notion of the so-called \(\beta\)-acyclicity, it was shown in [13] that BPO is polynomially solvable if in addition \(\mathcal{H}\) does not contain a special substructure, called a kite. More recently [14], [15] showed that BPO is solvable in strongly polynomial time whenever \(\mathcal{H}\) is \(\beta\)-acyclic (without any additional assumptions). The approach of [14], [15] is based on the iterative elimination of the nest points, the existence of which is guaranteed by \(\beta\)-acyclicity. This idea was generalized in [16] by considering nest sets. Recently [17] introduced a new dynamic programming based approach that was shown to work efficiently for hypergraphs with limited reach. Utilizing an enhanced linearization model [18] proved that BPO problems with bounded rank \(\alpha\)-acyclic hypergraphs are also solvable in polynomial time. (We are going to introduce all necessary notions and definitions later, in our technical sections.)

1.1 Our Contributions↩︎

The basic-algorithm, as introduced in [1], [5], is a rather generic variable elimination scheme, described in mathematical terms. The important missing algorithmic details e.g., for bounded tree-width hypergraphs were added and analyzed by [6]. In fact, several of the above cited positive results can be viewed as variants of this basic-algorithm, filing in the missing algorithmic details and complexity analysis for particular hypergraph structures.

In this paper we focus on a generalized version of the basic-algorithm for problem BPO, and provide a complete analysis and description of this approach.

For a subset \(S\subseteq V\) and binary vector \(\mathbf{x}\in\mathbb{B}^V\), we define \(\mathbf{x}^S = (x_j\mid j\in S)\) the subvector of \(\mathbf{x}\) corresponding to index set \(S\). For a partition \(V=X\cup Y\) we also write \(\mathbf{x}=(\mathbf{x}^X,\mathbf{x}^Y)\).

Assume \(\mathcal{H}\subseteq 2^V\) and \(\mathbf{c}\in \mathbb{Q}^n\), as in 2 . For a nontrivial partition \(V=X\cup Y\) with \(X\neq\emptyset\), \(Y\neq\emptyset\), we define the projection of \(f_{\mathcal{H},\mathbf{c}}\) on \(Y\) as \[\label{e-eliminateX} f_{\mathcal{H},\mathbf{c}}^{Y}(\mathbf{x}^Y) ~=~ \max_{\mathbf{x}^X\in \mathbb{B}^X} f_{\mathcal{H},\mathbf{c}}(\mathbf{x}^X,\mathbf{x}^Y) \text{ for all } \mathbf{x}^Y\in\mathbb{B}^Y.\tag{3}\] The results of [2] show that if \(g:\mathbb{B}^V\mapsto \mathbb{Q}\) is a rational mapping, then it’s unique multilinear polynomial has rational coefficients. Thus, it follows that the unique multilinear polynomial form of \(f_{\mathcal{H},\mathbf{c}}^{Y}\) also has rational coefficients for every \(Y\subseteq V\).

In our first main result we provide an explicit closed form for the unique multilinear polynomial of \(f_{\mathcal{H},\mathbf{c}}^{Y}\) to which we arrive by utilizing a higher dimensional representation of the problem, the so called signature space of a hypergraph (considered e.g., in [19], [20].) We prove that in this unique multilinear polynomial the monomials that (may) have nonzero coefficients are in a one-to-one relation with the signatures of \(\mathcal{T}=\{H\setminus X\mid H\in\mathcal{H},~ H\cap X\neq\emptyset\}\). This family of monomials depends only on the hypergraph \(\mathcal{H}\) (and the chosen subset \(X\)), but do not depend on the coefficients \(\mathbf{c}\) of our input. We also show that this set of monomials and the corresponding coefficients in the unique multlinear polynomial of \(f_{\mathcal{H},\mathbf{c}}^{Y}\) can be computed in polynomial time in \(|V|\), \(|\mathcal{H}|\), \(2^{|X|}\) and the size \(K\) of the signature space of \(\mathcal{T}\) (which on its own turn is known to be computable polynomially in terms of \(K\), \(|V|\), and \(|\mathcal{H}|\), see [19].)

Our next main result is the characterization of a special class of hypergraphs for which the unique multilinear polynomial of the projection \(f_{\mathcal{H},\mathbf{c}}^{Y}\) is efficiently computable in terms of the input size, and for which the variable elimination steps can be executed recursively and efficiently, leading to polynomial time solution of BPO. In particular, we show that all of the above cited tractable cases (e.g., for bounded tree-width, \(\beta\)-acyclic hypergraphs, hypergraphs with limited reach, bounded rank \(\alpha\)-acyclic hypergraphs) belong to this class together with some additional classes. Thus, our approach properly generalizes the cited tractable classes.

2 Signatures of hypergraphs↩︎

Given a hypergraph \(\mathcal{H}\subseteq 2^V\) and \(\mathbf{x}\in\mathbb{B}^V\), we introduce \[\label{e-y40x41} y_H(\mathbf{x})=\prod_{v\in H} x_v ~~~\text{ and }~~~ \mathbf{y}(\mathbf{x})=(y_H(\mathbf{x})\mid H\in\mathcal{H})\in \mathbb{B}^\mathcal{H}.\tag{4}\] We call \(\mathbf{y}(\mathbf{x})\) a signature of \(\mathcal{H}\), and denote by \[\label{e-YY} \mathbb{Y}=\{\mathbf{y}(\mathbf{x})\mid \mathbf{x}\in \mathbb{B}^V\} \subseteq \mathbb{B}^\mathcal{H}\tag{5}\] the set of signatures of \(\mathcal{H}\). If the hypergraph is not obvious from the context, we write \(\mathbf{y}^\mathcal{H}(\mathbf{x})\) and \(\mathbb{Y}_\mathcal{H}\), respectively.

Signatures were considered in a more general setting in [19] and the following result, applicable to our case, was shown there:

2.1 Lifting multilinear polynomials↩︎

Let us now fix a hypergraph \(\mathcal{H}\subseteq 2^V\), a rational vector \(\mathbf{c}\in\mathbb{Q}^\mathcal{H}\), and a nontrivial partition \(V=X\cup Y\). We associate to \(\mathcal{H}\) and \(V=X\cup Y\) the following hypergraphs: \[\label{e-PQRT} \begin{array}{rl} \mathcal{P}&=\{H\in\mathcal{H}\mid H\subseteq X\},\\ \mathcal{Q}&=\{H\in\mathcal{H}\mid H\cap X\neq\emptyset \text{ and } H\cap Y\neq\emptyset\},\\ \mathcal{R}&=\{H\in\mathcal{H}\mid H\subseteq Y\}, \text{ and }\\ \mathcal{T}&=\{H\cap Y\mid H\in \mathcal{Q}\}. \end{array}\tag{6}\] We also consider the signatures \(\mathbb{Y}_\mathcal{T}\) of hypergraph \(\mathcal{T}\) and partition \(f_{\mathcal{H},\mathbf{c}}(\mathbf{x})=\alpha(\mathbf{x})+\beta(\mathbf{x})+\gamma(\mathbf{c})\) where \[\begin{array}{rl} \alpha(\mathbf{x}) &= \displaystyle\sum_{H\in \mathcal{P}} c_H \prod_{v\in H} x_v,\\*[5mm] \beta(\mathbf{x}) &= \displaystyle\sum_{H\in \mathcal{Q}} c_H \prod_{v\in H} x_v, \text{ and }\\*[5mm] \gamma(\mathbf{x}) &= \displaystyle\sum_{H\in \mathcal{R}} c_H \prod_{v\in H} x_v.\\ \end{array}\] Note that \(\alpha\) depends only on variables \(x_v\), \(v\in X\), while \(\gamma\) depends only on variables \(x_v\), \(v\in Y\). We can transform \(\beta\) as follows: \[\begin{array}{rl} \beta(\mathbf{x}) &= \displaystyle\sum_{H\in \mathcal{Q}} c_H \prod_{v\in H} x_v,\\*[8mm] &= \displaystyle\sum_{H\in \mathcal{Q}} c_H \left(\prod_{v\in H\cap X} x_v\right)\left(\prod_{v\in H\cap Y} x_v\right)\\*[8mm] &= \displaystyle\sum_{H\in \mathcal{Q}} c_H \left(\prod_{v\in H\cap X} x_v\right) y_{H\cap Y}(\mathbf{x}). \end{array}\] Note that on the right hand side we have sets \(H\cap Y\) for \(H\in \mathcal{Q}\) that is sets from \(\mathcal{T}\). Thus, for a particular vector \(\mathbf{y}=(y_T\mid T\in \mathcal{T})\in \mathbb{Y}_\mathcal{T}\) we can introduce \[\beta_\mathbf{y}(\mathbf{x}) ~=~ \displaystyle\sum_{H\in \mathcal{Q}} c_H \left(\prod_{v\in H\cap X} x_v\right) y_{H\cap Y}.\] Now, both \(\alpha\) and \(\beta_\mathbf{y}\) depends only on variables from \(X\), for each \(\mathbf{y}\in \mathbb{Y}_\mathcal{T}\). Let is finally define \[\label{e-mu} \mu(\mathbf{y}) ~=~ \max_{\mathbf{x}\in \mathbb{B}^X} \left(\alpha(\mathbf{x})+\beta_\mathbf{y}(\mathbf{x})\right) ~~~\text{ for all } \mathbf{y}\in \mathbb{Y}_\mathcal{T}.\tag{7}\] With these notations we can rewrite the reduced function \(f^Y_{\mathcal{H},\mathbf{c}}\) defined in 3 .

Let us remark here that the above expression may not seem to provide a “small” multilinear form for the projection \(f^Y_{\mathcal{H},\mathbf{c}}\), since to obtain that we would need to carry out the multiplications on the right, for every \(\mathbf{z}\in \mathbb{Y}_\mathcal{T}\), and for a \(\mathbf{z}\) vector with many zeros that multiplication may yield potentially exponentially many different monomials in terms of the \(x_v\), \(v\in V\) binary variables. In the next claim we show that in fact this is not happening, and the size is limited in terms of the size of \(\mathbb{Y}_\mathcal{T}\).

Note that our proof above shows that the right hand side of ?? is the unique multilinear polynomial of the \(\mathbb{B}^{\mathbb{Y}_\mathcal{T}}\mapsto \mathbb{Q}\) mapping defined by the left hand side. (Recall, that all such mappings have a unique multilinear polynomial representation by [1], [2].)

Furthermore, 2 implies that considering the signature space of \(\mathcal{T}\) is the right choice, in the sense that the “new” monomials that may have nonzero coefficient in \(f^Y_{\mathcal{H},\mathbf{c}}\) for some \(\mathbf{c}\in \mathbb{Q}^\mathcal{H}\) are exactly the ones on the right hand side of ?? corresponding to the signatures in \(\mathbb{Y}_\mathcal{T}\).

2.2 Algorithmic Consequences↩︎

Using the above results, we can easily build an algorithm that solves problem 2 by iteratively eliminating small (with an eye on the efficiently computable special cases) sets of variables.

To be able to do this, we need to refine our notation (to avoid potential ambiguities). For a mapping \(g:\mathbb{B}^V\mapsto \mathbb{Q}\) let us denote by \(\mathcal{H}(g)\subseteq 2^V\) the hypergraph for which we have \(g=f_{\mathcal{H}(g),\mathbf{c}}\) for some \(\mathbf{c}\in (\mathbb{Q}\setminus\{0\})^{\mathcal{H}(g)}\) (that is with no zero components). Note that by [1], [2] \(g\) has a unique multilinear polynomial representation, and thus both \(\mathcal{H}(g)\) and \(\mathbf{c}\) are uniquely defined.

Let us recall next that to a hypergraph \(\mathcal{H}\) and a partition \(V=X\cup (V\setminus X)\) we associated partial hypergraphs as in 6 . In a multistep procedure this may lead to ambiguities, so for clarity we will write

\[\label{e-PQRT-updated} \begin{array}{rl} \mathcal{P}= \mathcal{P}(\mathcal{H},X) &=~ \{H\in\mathcal{H}\mid H\subseteq X\} \\ \mathcal{Q}= \mathcal{Q}(\mathcal{H},X) &=~ \{H\in\mathcal{H}\mid H\cap X\neq \emptyset \text{ and } H\setminus X\neq \emptyset \} \\ \mathcal{R}= \mathcal{R}(\mathcal{H},X) &=~ \{H\in\mathcal{H}\mid H\cap X = \emptyset \} \\ \c T= \mathcal{T}(\mathcal{H},X) &=~ \{ H\setminus X \mid H\in \mathcal{Q}(\mathcal{H},X)\} \end{array}\tag{10}\]

For a hypergraph \(\mathcal{H}\subseteq 2^V\) we define its union closure as \[\mathcal{H}^u ~=~ \left\{\left. \bigcup_{H\in\mathcal{H}'}H ~\right|~ \mathcal{H}'\subseteq \mathcal{H}\right\}.\]

Thus, the union closure of a hypergraph and its signature space are in a one-to-one correspondence. While in the proofs of the previous section it was advantageous to consider the signature space, in the sequel we switch to the equivalent union closure.

Let us observe finally that according to 3 we have for all \(X\subseteq V\) the containment \[\label{e-th4-consequence} \mathcal{H}\big(f^{V\setminus X}_{\mathcal{H},\mathbf{c}}\big) \subseteq \mathcal{R}(\mathcal{H},X)\cup \mathcal{T}(\mathcal{H},X)^u.\tag{11}\] In fact, for some \(\mathbf{c}\in \mathbb{Q}^\mathcal{H}\) we may have equality here⁴. Thus, we feel justified to call the hypergraph \(\mathcal{R}(\mathcal{H},X)\cup \mathcal{T}(\mathcal{H},X)^u\) the \((V\setminus X)\)-projection of \(\mathcal{H}\).

We use 3 first to derive a sufficient condition for an efficient single step of the above variable elimination scheme.

While such a single step variable elimination could be helpful in reducing/simplifying BPO problems, our purpose here is to solve BPO problems by recursively applying the above elimination step.

We describe below a fully general solution algorithm for BPO problems that applies the above ideas. We will analyze its efficiency later for special hypergraph classes.

Procedure SBVE (Signatures Based Variable Elimination)

Input: an integer threshold \(\tau\in \mathbb{Z}_+\),
a hypergraph \(\mathcal{H}\subseteq 2^V\) and
a coefficient vector \(\mathbf{c}\in\mathbb{Q}^\mathcal{H}\).

Initialize: \(k=1\), \(W_1=V\), and \(g_1=f_{\mathcal{H},\mathbf{c}}\) (as in 2 )

While \(|W_k|\geq \tau\) do:

Step 1: Choose \(X_k\subseteq W_k\), \(1\leq |X_k|\leq \tau\), and set \(Y_k=W_k\setminus X_k\).

Step 2: Compute \(\mathcal{T}_k=\mathcal{T}(\mathcal{H}(g_k),X_k)\) from \(\mathcal{H}(g_k)\) (as in 10 )

Step 3: Compute \(\mathbb{Y}_{\mathcal{T}_k}\),

Step 4: Compute \(\mu(\mathbf{y})\) and a binary vector \(\mathbf{x}(\mathbf{y})\in \mathbb{B}^{X_k}\) attaining
\(~\)the maximum in 7 , for each \(\mathbf{y}\in \mathbb{Y}_{\mathcal{T}_k}\).

Step 5: Compute \(h=g_k^{Y_k}\) (as in 3).

Step 6: Update \(g_{k+1}=h\), \(W_{k+1}=Y_k\), and set \(k=k+1\).

EndWhile:

Finalize: Compute \(Z=\displaystyle\max_{\mathbf{x}\in \mathbb{B}^{W_k}} g_k(\mathbf{x})\), a binary vector \(\mathbf{x}_k\) attaining
\(~\)this maximum, and set \(\ell=k-1\).

While \(\ell \geq 1\) do:

Step 7: Compute \(\mathbf{y}_\ell = \mathbf{y}(\mathbf{x}_{\ell+1})\in \mathbb{Y}_{\mathcal{T}_\ell}\).

Step 8: Set \(\mathbf{x}_\ell = (\mathbf{x}(\mathbf{y}_\ell),\mathbf{x}_{\ell+1})\in \mathbb{B}^{X_\ell\cup Y_\ell}\) (concatenation)

Step 9: Update \(\ell=\ell-1\).

EndWhile:

Output: \(Z\) and \(\mathbf{x}^*=\mathbf{x}_1\).

Let us remark last that Step 1 in the above procedure is quite vague (on purpose), while all other steps are described precisely, and are based on the computational ideas we used in some of our proofs above. We shall provide precise description for Step 1 tailored to the structure of the special hypergraph classes we consider below. In fact, we choose in Step 1 a \((\tau,K)\)-nest for a particular value of \(K\) such that the considered special hypergraph class guarantees the existence of such a nest set.

3 Applications↩︎

In this section we utilize the explicit description of a projection in 3 allowing us to analyze the repeated application of this variable elimination (projection) process to describe specially structured families of hypergraphs for which Procedure SBVE can provide an efficient solution of the corresponding BPO problem.

3.1 Union Bounded Problems↩︎

First we consider those hypergraphs the union closure of which is “not too large”.

For a \(K\)-union bounded hypergraph \(\mathcal{H}\subseteq 2^V\) we also call a corresponding multilinear polynomial \(f_{\mathcal{H},\mathbf{c}}\) and the corresponding BPO problem 2 \(K\)-union bounded for every \(\mathbf{c}\in\mathbb{Q}^\mathcal{H}\).

Let us next argue that polynomially union bounded BPO problems can in fact be solved efficiently in one step, without a recursive variable elimination.

For a subset \(S\subseteq V\) we denote by \(\chi(S)\in \mathbb{B}^V\) the characteristic vector of \(S\). To a hypergraph \(\mathcal{H}\subseteq 2^V\) we associate the family of characteristic vectors of the subsets in its union closure:

\[\label{e-char-of-union-closure} \mathbb{U}(\mathcal{H}) ~=~ \{\chi(U)\mid U\in\mathcal{H}^u\} ~\subseteq~ \mathbb{B}^V.\tag{12}\]

3.2 Locally Union Bounded Problems↩︎

While union bounded hypergraphs are natural to consider in view of Theorem 3, they form a somewhat narrow class that has no relation to the other classes of hypergraphs for which BPO is known to be solvable efficiently. It is possible however to extend this class to a significantly larger family that still guarantees efficient solvability of problem BPO.

Assume that \(\tau\in\mathbb{Z}_+\) is a positive integer, and \(K\in \mathbb{Z}_+\) as before.

Let us note that we do not know how to test the conditions of 3 in polynomial time. Furthermore, it may happen that we have different subsets \(X_1\subseteq V\) and \(X_2\subseteq V\), both satisfying property (i) of 3, and with \(\mathcal{G}=\mathcal{T}(\mathcal{H},X_1)^u\cup\mathcal{R}(\mathcal{H},X_1)\) \[|\mathcal{T}(\mathcal{G},X_2)^u| ~\gg~ K.\] Still, under further special properties of the underlying hypergraph, local boundedness may become efficiently recognizable.

In the next subsections we show multiple classes of hypergraphs that are \(O(n^\beta)\)-union bounded or locally \((\tau,O(n^\beta))\)-bounded, for some constants \(\tau\) and \(\beta\). In fact these classes include all of the tractable special classes cited in the introduction, and some others.

3.3 Bounded width hypergraphs↩︎

Given a hypergraph \(\mathcal{H}\subseteq 2^V\) we call a subfamily \(\mathcal{C}\subseteq \mathcal{H}\) a chain if for all \(H,H'\in\mathcal{C}\) we have either \(H\subseteq H'\) or \(H'\subseteq H\) (such families are also called nested). A subfamily \(\mathcal{A}\subseteq \mathcal{H}\) is called an antichain if for all \(H,H'\in \mathcal{A}\), \(H\neq H'\) we have both \(H\setminus H'\neq \emptyset\) and \(H'\setminus H\neq \emptyset\) (such families are also called Sperner systems in the literature). The celebrated theorem of Dilworth [21] claims that the minimum number of chains in a chain cover of \(\mathcal{H}\) is equal to the maximum number of hyperedges in an antichain of \(\mathcal{H}\), i.e., \[\max \left\{|\mathcal{A}| \left| \begin{array}{c} \mathcal{A}\subseteq \mathcal{H}\\ \mathcal{A}\text{ is an antichain} \end{array} \right.\right\} ~=~ \min \left\{\ell \left| \begin{array}{c} \exists \text{ chains } \mathcal{C}_j\subseteq \mathcal{H}, ~j\in [\ell] \\ \text{ s.t. } \mathcal{H}=\mathcal{C}_1\cup \dots \cup \mathcal{C}_\ell \end{array} \right.\right\}.\] Let us denote by \(\omega(\mathcal{H})\) this common value, called the width of \(\mathcal{H}\).

3.4 Bounded tree-width hypergraphs↩︎

In this subsection we consider simple undirected graphs and use standard graph theory notions and definitions, see e.g., [22]. We say that a vertex \(v\) of a graph \(G=(V,E)\) is simplicial if its neighbors \(N(v)=\{w\in V\mid (v,w)\in E\}\) induce a complete subgraph of \(G\). For \(\chi\in \mathbb{Z}_+\) we say that for a graph \(G=(V,E)\) an ordering \(V=\{v_1,v_2,\dots ,v_n\}\) is a \(\chi\)-perfect elimination order if for every \(v_j\in V\) vertex \(v_j\) is simplicial in the subgraph induced by \(W_j=\{v_j,v_{j+1},\dots,v_n\}\) and \(|N(v_j)\cap W_j|\leq \chi\). A graph \(G\) is called a \(\chi\)-tree if it has a \(\chi\)-perfect elimination order. A graph \(G=(V,E)\) is called a partial \(\chi\)-tree if there exists a \(\chi\)-tree \(G^*=(V,F)\) such that \(E\subseteq F\). The tree-width \(tw(G)\) of a graph \(G\) is the smallest value of \(\chi\) such that \(G\) is a partial \(\chi\)-tree. While determining \(tw(G)\) is NP-hard in general (see e.g., [23]), for a constant \(\chi\) the relation \(tw(G)\leq \chi\) can be recognized and if the relation holds the corresponding \(\chi\)-tree and \(\chi\)-perfect elimination order can be constructed in polynomial time, see e.g., [24]–[26].

To a hypergraph \(\mathcal{H}\subseteq 2^V\) we associate its co-occurrence graph \(G_\mathcal{H}=(V,E)\) where \[E ~=~ \{(i,j)\mid i,j\in V,~ \exists H\in\mathcal{H}\text{ s.t. } i,j\in H \}\] and define its tree-width \(tw(\mathcal{H})\) as the tree-width of its associated co-occurrence graph \(tw(\mathcal{H})=tw(G_\mathcal{H})\).

For a more precise complexity of the above result note that we can compute the co-occurrence graph of \(\mathcal{H}\) in \(O(|V|^2|\mathcal{H}|)\) time, and test \(tw(G_\mathcal{H})\leq \chi\) in \(O(2^{O(\chi^3)}|V|)=O(|V|)\) time by the algorithm of [25]. Procedure SBVE takes \(|V|\) iterations, and in each iteration we have \(|\mathcal{T}_k^u|\leq 2^\chi\) implying by 3 that the procedure will terminate in \(O(|V|^2|\mathcal{H}|)\) time.

3.5 Hypergraphs with bounded reach↩︎

This family of hypergraphs was recently considered by [17]. For a hypergraph \(\mathcal{H}\subseteq 2^V\) we define its reach as \(\rho(\mathcal{H})=\max_{H\in\mathcal{H}}\max _{i,j\in H} |i-j|\). The authors of [17] introduced a specialized dynamic programming procedure for this special class, and showed strongly polynomial tractability of problem BPO for this case. Note that \(tw(\mathcal{H})\leq \rho(\mathcal{H})\) as observed in [17]. In fact, for \(\chi=\rho(\mathcal{H})\) the graph \(G^*=(V,F)\) with \(F=\{(i,j)\mid i,j\in V,~|i-j|\leq \chi\}\) is a \(\chi\)-tree, such that for \(G_\mathcal{H}=(V,E)\) we have \(E\subseteq F\), and \(V=\{1,2,\dots,n\}\) is a \(\chi\)-perfect elimination order. Consequently, the results of the previous subsection provide strongly polynomial time solution for problem BPO for hypergraphs with bounded reach, by eliminating variables from \(V\) one by one, in the order indicated above. Thus, for hypergraphs with limited reach we do not need to spend time to compute the actual tree-width and the corresponding perfect elimination order.

3.6 \(\beta\)-acyclic hypergraphs↩︎

Let us recall (see [10]) that a hypergraph \(\mathcal{H}\subseteq 2^V\) is \(\beta\)-acyclic, if it does not contain hyperedges \(H_i\in\mathcal{H}\) and vertices \(v_i\in V\) for \(i=1,...,k\) for some \(k\geq 3\) such that \(v_i\in H_{i-1}\cap H_i\) and \(v_i\not\in H_j\) if \(j\not\in \{i-1,i\}\) for all \(i,j=1,...,k\) (where \(1=k+1\)). Such hypergraphs were called totally balanced in [27] and have interesting properties, see e.g., [28].

A vertex \(v\in V\) is called a nest point of \(\mathcal{H}\) if \(\mathcal{P}(\mathcal{H},\{v\})\cup \mathcal{Q}(\mathcal{H},\{v\})\) is a nested family, that is if for any pair \(H,H'\in \mathcal{P}(\mathcal{H},\{v\})\cup \mathcal{Q}(\mathcal{H},\{v\})\) we have either \(H\subseteq H'\) or \(H'\subseteq H\). Note that this condition is equivalent with the nestedness of \(\mathcal{T}(\mathcal{H},\{v\})\).

It was shown in [29] (see also [8], [9], [11]) that a hypergraphs \(\mathcal{H}\subseteq 2^V\) is \(\beta\)-acyclic if and only if for every subset \(X\subseteq V\) the subhypergraph \(\mathcal{T}(\mathcal{H},X)\cup \mathcal{R}(\mathcal{H},X)\) has a nest point. Since for a nested hypergraph \(\mathcal{N}\) we have both \(\mathcal{N}^u=\mathcal{N}\) and \(|\mathcal{N}|\leq |V|\), the following claim can be shown easily.

Note that the complexity results claimed in 3 are based on the general projection setting and yield an \(O(|\mathcal{H}||V|^3)\) complexity for \(\beta\)-acyclic hypergraphs. However, in this special case we can compute the coefficients on the right hand side of 3 more efficiently, utilizing the nested structure of \(\mathcal{T}\), potentially improving total complexity to \(O(|V|^4)\) after an initial one time \(O(|V||\mathcal{H}|)\) preprocessing.

3.7 Bounded rank \(\alpha\)-acyclic hypergraphs↩︎

Let us recall (see [10]) that a hypergraph \(\mathcal{H}\subseteq 2^V\) is \(\alpha\)-acyclic if its hyperedges can be labeled \(\mathcal{H}=\{H_0,H_1,\dots,H_m\}\) such that for all \(j=1,\dots m\) there exists an index \(\ell=\ell(j)<j\) such that \[\label{e-running-intersection} H_j\cap \left(\bigcup_{i<j} H_i\right) ~\subseteq~ H_\ell.\tag{13}\] Note that we can assume w.l.o.g. that \(H_0=\emptyset\), since we can always add the emptyset to an \(\alpha\)-acyclic hypergraph without violating \(\alpha\)-acyclicity. If for an index \(j\) there exist more than one \(\ell\) that satisfies 13 , then we denote by \(\ell(j)\) the smallest such index.

The above property is called the running intersection property and it characterizes a very large family of hypergraphs. For instance, any hypergraph becomes \(\alpha\)-acyclic, if we add to it \(V\) as a hyperedge. Consequently, the BPO problem remains NP-hard, when restricted to \(\alpha\)-acyclic hypergraphs (see also [15]).

The rank of a hypergraph \(\mathcal{H}\subseteq 2^V\) is defined as \[\label{e-rank-of-cH} r(\mathcal{H}) ~=~ \max_{H\in \mathcal{H}} |H|.\tag{14}\] We say that \(\mathcal{H}\) is a bounded rank hypergraph if \(r(\mathcal{H})\leq d=O(\log poly (|V|,|E|))\).

Using an enhanced linearization method it was shown recently in [18] that BPO problems with bounded rank \(\alpha\)-acyclic hypergraphs are polynomially solvable.

We show here that such hypergraphs are also locally union bounded. To be able to show this claim, we need a few technical observations.

Assume for the rest of this subsection that \(\mathcal{H}=\{H_0=\emptyset, H_1,\dots , H_m\}\subseteq 2^V\) is an \(\alpha\)-acyclic hypergraph satisfying the running intersection property 13 and that \(r(\mathcal{H})\leq d=O(\log poly (|V|,|E|))\). We set \(J=\{0,1,\dots, m\}\) for this subsection. Furthermore, we can assume w.l.o.g. that \(V=\bigcup_{H\in\mathcal{H}} H\), since otherwise we could just redefine \(V\).

For an index \(v\in V\) let us define \[i(v) ~=~ \min_{H_j\ni v} j,\] set \(I=\{i(v)\mid v\in V\}\subseteq J\), and define \[S_i ~=~ \{v\in V\mid i(v)=i\} ~~\text{ for all }~~ i\in I.\] Note that by our assumptions, we have \(1\leq i(v)\leq m\) for all \(v\in V\).

To every hyperedge \(H\in\mathcal{H}\) let us associate \[i(H) ~=~ \max_{v\in H} i(v),\] and for every \(i\in I\) define \(J(i)=\{j\in [m]\mid i(H_j)=i\}\).

3.8 Circular interval hypergraphs↩︎

For a finite set \(V\) let us denote by \(C_V=(V,E)\) a directed graph on vertices \(V\) that is a directed (Hamiltonian) cycle going through all vertices in \(V\). Given such a cycle \(C_V=(V,E)\) and a vertex \(v\in V\) we denote by \(v^-\) and \(v^+\) the (unique) vertices for which we have \((v^-,v),~ (v,v^+) ~\in E\). We say that a subset \(I\subseteq V\) is a circular interval in \(C_V\) if the subgraph of \(C_V\) induced by \(I\) is a directed path or \(I=V\). We call a hypergraph \(\mathcal{H}\subseteq 2^V\) circular interval with respect to \(C_V\) if all hyperedges \(H\in \mathcal{H}\) are circular intervals in \(C_V\).

Note that a circular interval hypergraph may not be union bounded (e.g., if they contain many pairwise disjoint small intervals), may not have bounded tree-width (e.g., if they have long circular intervals), and may not be \(\beta\)-acyclic (e.g., if they have a chain of circularly overlapping circular interval hyperedges that cover \(V\)).

Circular interval hypergraphs were considered in the literature under different names (circular-arc hypergraphs, circular consecutive ones property, etc.) see e.g., [30], [31]. It was observed in [31] that circular interval hypergraphs can be recognized (and the corresponding directed cycle \(C_V\) can be constructed) in polynomial time, using the results of [32] together with a transformation introduced by [33].

It was also observed that some hard optimization problems become tractable under the circular consecutive ones property, see e.g., [34], [35]. In this subsection we would like to add problem BPO to this list.

Let us first make a few easy, technical observations about the structure of circular interval hypergraphs.

Given a directed (Hamiltonian) cycle \(C_V=(V,E)\) and vertex \(v\in V\) we define its projection on \(V\setminus\{v\}\) by \(C^{-v}_V=(V\setminus\{v\}, (E\setminus \{(v^-,v),(v,v^+)\}) \cup \{(v^-,v^+)\})\). Note that \(C^{-v}_V\) is again a directed (Hamiltonian) cycle on the set \(V\setminus \{v\}\), in which elements \(v^-\) and \(v^+\) are consecutive.

Note that by applying the complexity bound of 3 we obtain an \(O(|V|^5|\mathcal{H}|)\) complexity for the BPO problem with circular interval hypergraph structure.

Note also that we assume that the directed (Hamiltonian) cycle \(C_V\) is also given, proving that \(\mathcal{H}\) is circular interval. This is similar to the case of hypergraphs with bounded reach, where a particular order of \(V\) is also given and \(\rho(\mathcal{H})\) is computed with respect that order. Finding an order of \(V\) that minimizes the reach of the given hypergraph \(\mathcal{H}\subseteq 2^V\) is however an NP-hard optimization problem. As we mentioned earlier, we do not face such difficulties with the circular interval property. Given a hypergraph \(\mathcal{H}\subseteq 2^V\) we can recognize if it is circular interval and construct a corresponding directed (Hamiltonian) cycle \(C_V=(V,E)\) in polynomial time in \(|V|\) and \(|\mathcal{H}|\), see [32], [33].

References↩︎