Deterministic Approximation for the Volume of the Truncated Fractional Matching Polytope

The evaluation of volume is a classic computing task. The pioneer work of Dyer, Frieze, and Kannan [11] showed that given a membership oracle, the volume of a convex body can be approximated to arbitrary accuracy in randomised polynomial time. On the other hand, in the same model, deterministic approximation takes at least exponential time [12, 2]. This marked an early milestone that distinguished the computational power of deterministic algorithms from that of randomized algorithms.

Nonetheless, computing volumes might still be interesting for other models and/or more restricted cases, where the lower bound of [12, 2] does not apply, and interesting deterministic volume algorithms may still exist. In particular, there appears to be no run-time lower bound for deterministically approximating the volume of a polytope given by facets. In this case, as the membership oracle is trivial to implement, the randomised algorithm of Dyer, Frieze, and Kannan [11] achieves an $\epsilon$-approximation in time polynomial in the input size and $\frac{1}{\epsilon }$. The deterministic counterpart of such an algorithm is called fully polynomial-time approximation scheme (FPTAS). Unfortunately, the best deterministic algorithmic technique for polytope volumes appears to fall short of achieving FPTAS. They either require exponential time [18, 5]¹¹1The algorithms of [18, 5] are in fact exact algorithms and the dominating term in their run-time is linear in the number of vertices of the polytope. or yield exponential approximation [3, 4]. In the hope of getting an FPTAS, we may focus on even more restricted cases, such as the independence polytope or matching polytope for graphs.

Along this direction, Gamarnik and Smedira [13] considered the relaxed independence polytope. Given a graph $G=(V,E)$, it is defined as $\{𝐱\in {[0,1]}^V\mid \forall \{u,v\}\in E,x_u+x_v\le 1\}$. Clearly, if we further restrict every $x_v$ to the interval $[0,1/2]$, this polytope degenerates to a cube of side length $1/2$ and its volume is simply $2^{-\left|V\right|}$. Gamarnik and Smedira [13] showed that we can push beyond this trivial case, namely, if we truncate the relaxed independence polytope by the interval $[0,\frac{1}{2}\left(1+\frac{O(1)}{{\mathrm{\Delta }}^2}\right)]$ for graphs of maximum degree $\mathrm{\Delta }$, a quasi-polynomial-time approximation scheme exists. Their technique is based on the correlation decay approach [22, 1]. Subsequently, Bencs and Regts [8] improved the interval to $[0,\frac{1}{2}\left(1+\frac{O(1)}{\mathrm{\Delta }}\right)]$ and the run-time to polynomial-time, based on the zeros of polynomial approach [6, 20]. The bound on this interval appears to be where the limit of the current methods is.

In this paper, we explore what other polytopes may admit efficient deterministic volume approximation. In particular, we consider the natural dual of the independence polytope, namely the matching polytope, or more precisely, its standard relaxation, the fractional matching polytope. Note that although it is the dual of the relaxed independence polytope, its volume might be drastically different.

For the fractional matching polytope, the trivial truncation is with the interval $[0,\frac{1}{\mathrm{\Delta }}]$. Similar to [13, 8], we also truncate $P_G$ by an interval that is slightly longer, multiplicatively, than the trivial truncation.

Denote the interval $[0,\frac{1+\delta }{\mathrm{\Delta }}]$ by $M_{\delta }$. Then $P_{G,\delta }=M_{\delta }^{}{}_{}{}^E\cap P_G$. Additionally, for any $v\in V$, the constraint ${\sum }_{e\sim v}{x}_e\le 1$ is denoted by $C_v$. We are interested in computing the volume of $P_{G,\delta }$, i.e. the quantity

where $\mu$ is the Lebesgue measure and the indicator function ${\mathrm{𝟙}}_{C_v}:M_{\delta }^{}{}_{}{}^E\to \{0,1\}$ outputs $1$ if and only if the constraint $C_v$ is satisfied, i.e. when ${\sum }_{e\sim v}{x}_e\le 1$.

Our main result regarding $\mathrm{Vol}(P_{G,\delta })$ is the following. Interestingly, similar to [8], the relative margin for the truncation interval we get is also $\frac{C}{\mathrm{\Delta }}$.

The proof of Theorem 3 relies on the algorithmic cluster expansion approach [14, 16]. This is very closely related to the zeros of polynomial approach Bencs and Regts [8] took. The first step is to rewrite $\mathrm{Vol}(P_{G,\delta })$ as the partition function of a polymer model on the graph $G$. Roughly speaking, each polymer corresponds to a set of connected vertices where the constraints on these vertices are violated. For the algorithmic approach of the polymer model to work, we need to show that the total weights of these violations decay rapidly, or more technically, the so-called Kotecký-Preiss criterion [17] holds. Intuitively, when we truncate with the trivial interval $[0,\frac{1}{\mathrm{\Delta }}]$, none of the violation may happen. With a longer truncation interval, violations can happen, but the small relative margin we allow implies that violations can only happen with small probability. Our method involves some careful estimates of these violation probabilities. We also note that it appears difficult to apply the correlation decay method here, and a direct application of the argument of Bencs and Regts [8] would yield a smaller margin $\delta =\frac{C}{{\mathrm{\Delta }}^2}$ for some constant $C>0$.

As mentioned earlier, the volumes of the relaxed independence polytope and the fractional matching polytope do not appear to be related, and thus Theorem 3 is not directly comparable to the main result of [8]. To put both results under a unified framework, we also consider hypergraph matchings. Let $H=(V,E)$ be a hypergraph. Consider the following polytope:

where $e\ni v$ if the hyperedge $e$ contains $v$. This is a relaxation of the hypergraph matching polytope and a natural generalisation of the fractional matching polytope for graphs in Definition 1. We denote it by the fractional hypergraph matching polytope.

We consider hypergraphs of maximum degree $\mathrm{\Delta }\ge 2$ and maximum hyperedge size $k\ge 2$. In this case, the polytope $P_H$ is indeed defined by a set of linear constraints where each variable appears at most $k$ times, and each constraint has at most $\mathrm{\Delta }$ variables. When $k=2$, this degenerates to the fractional matching polytope, and when $\mathrm{\Delta }=2$, this degenerates to the relaxed independence polytope. Similar to Definition 2, we truncate it by a cube of side length $\frac{1+\delta }{\mathrm{\Delta }}$. Recall that $M_{\delta }$ denotes the interval $[0,\frac{1+\delta }{\mathrm{\Delta }}]$. Define the truncated polytope $P_{H,\delta }:=M_{\delta }^{}{}_{}{}^E\cap P_H$. Our result regarding $\mathrm{Vol}(P_{H,\delta })$ is the following.

The bound $\delta =O\left({\left({\mathrm{\Delta }}^{\frac{2k-3}{k-1}}k\right)}^{-1}\right)$ recovers Theorem 3. Namely, when $k=2$, $\delta =O\left(\frac{1}{\mathrm{\Delta }}\right)$. Moreover, when $\mathrm{\Delta }=2$, $\delta =O\left(\frac{1}{k}\right)$ and the interval length is $\frac{1+\delta }{\mathrm{\Delta }}=\frac{1}{2}+O\left(\frac{1}{k}\right)$, which recovers the result of [8].

The proof of Theorem 4 also relies on the algorithmic cluster expansion approach. It combines our technique for proving Theorem 3 and a generalisation of the technique in [8]. In particular, we introduce a different polymer model in this case, which requires a new generalisation of the classic broken circuit theory [23, 21] to hypergraphs.

An immediate open problem is if Theorem 4 holds with $\delta =O\left(\frac{1}{\mathrm{\Delta }k}\right)$, which is discussed in more detail in Section 4. A much more challenging question is if we can obtain deterministic volume approximation for these polytopes without truncation, or with truncation by the interval $[0,1-\delta ]$ for some small $\delta$. For the closely related problems of approximating the number of independent sets or matchings, deterministic algorithms [22, 20, 7] match their randomised counterparts, at least for bounded degree graphs. In particular, in bounded degree graphs, an efficient deterministic algorithm exists to approximately count the number of matchings [7]. However, these methods do not seem to carry over to volume approximation. When there is no or little truncation, volume approximation appears to be out of reach for current deterministic methods.

The rest of the paper is organised as follows. In Section 2, we consider the fractional matching polytope and show Theorem 3. In Section 3, we turn our attention to the hypergraph case and show Theorem 4. Finally, in Section 4, we discuss some potential future directions and the current obstacles.

In this section, we briefly review the polymer model and the algorithmic cluster expansion approach, and apply it to $\mathrm{Vol}(P_{G,\delta })$ to show Theorem 3. Let $𝒫$ be a finite set, whose elements we call polymers. We endow $𝒫$ with a symmetric and reflexive incompatibility relation $\sim ̸$ between any two polymers, and also a weight function $w(\cdot )$²²2The weight function can be complex-valued, but in this paper we will focus on real-valued weight functions. that assigns a weight $w(\gamma )$ to the polymer $\gamma$. Given two polymers ${\gamma }_1$ and ${\gamma }_2$, we write ${\gamma }_1\sim ̸{\gamma }_2$ if ${\gamma }_1$ and ${\gamma }_2$ are incompatible, and ${\gamma }_1\sim {\gamma }_2$ otherwise. For a set $\mathrm{\Gamma }$ of polymers, we say it is compatible if for any two ${\gamma }_1,{\gamma }_2\in \mathrm{\Gamma }$, ${\gamma }_1\sim {\gamma }_2$. Additionally, there is a size function for polymers, and we use $\left|\gamma \right|$ to denote the size of $\gamma$.

We will be interested in the cluster expansion which is an infinite series representation of $\log \mathrm{\Xi }(P)$. Given a multiset $\mathrm{\Gamma }$ of polymers from $𝒫$, we define the incompatibility graph $H(\mathrm{\Gamma })$ where we have a vertex $v_{\gamma }$ for every polymer $\gamma \in \mathrm{\Gamma }$ and an edge between every pair of vertices corresponding to an incompatible pair of polymers. A multiset $\mathrm{\Gamma }$ is called a cluster if the incompatibility graph $H(\mathrm{\Gamma })$ is connected. We also denote the set of all clusters from $𝒫$ as $𝒞$. Given $\mathrm{\Gamma }\in 𝒞$, let $H=H(\mathrm{\Gamma })$ and define the Ursell function

We refer the interested reader to the survey by Jenssen [15] for various algorithmic (and beyond) applications of the cluster expansion. The cluster expansion is a good approximation to the logarithm of the partition function under various conditions. One of the most well-known conditions is the following.

We note that the condition in Proposition 7 is not the most general, but this particular form will be convenient for our use later.

We are going to recast (1) into a polymer partition function. Let $G=(V,E)$ be a graph of maximum degree $\mathrm{\Delta }$. For $S\subseteq V$, let $𝒦(S)$ be the set of connected components in the induced subgraph $G[S]$.

Denote by $\overline{C_v}$ the constraint ${\sum }_{e\sim v}{x}_e>1$. Using the indicator function for the constraint $\overline{C_v}$, and the fact that ${\mathrm{𝟙}}_{C_v}=1-{\mathrm{𝟙}}_{\overline{C_v}}$, we can expand (1) as

We then continue by pushing the integral inside:

where, for a subset $S\subseteq V$ of vertices, $E(S)$ denotes the set of edges adjacent to it. Note that we swapped the integral with the product in (5). This is valid because the constraint regarding each $S_i$ rely on disjoint set of edges. There is also an extra factor of ${\int }_{M_{\delta }^{}{}_{}{}^{E\setminus E(S)}}1d\mu$ to account for the edges that are not adjacent to $S$. As ${\int }_{M_{\delta }^{}{}_{}{}^{E\setminus E(S)}}1d\mu ={\left(\frac{1+\delta }{\mathrm{\Delta }}\right)}^{\left|E\right|-\left|E(S)\right|}$, we have

where

The redistribution of the ${\left(\frac{1+\delta }{\mathrm{\Delta }}\right)}^{-\left|E(S)\right|}$ factor is valid because ${\{E(K)\}}_{K\in 𝒦(S)}$ is a partition of $E(S)$.

To fit (6) into Definition 5, we call a subset $S\subseteq V$ a polymer if the induced subgraph $G[S]$ is connected. Two polymers $S_1$ and $S_2$ are compatible if ${\mathrm{dist}}_G(S_1,S_2)\ge 2$, namely when they are not adjacent. The size of a polymer is simply the number of vertices it contains. In addition, equipped with the weight function in (7), we then have that

The polymer model is useful thanks to the following theorem by Jenssen, Keevash, and Perkins [16] (building upon the works of [9, 20, 14]).

The algorithm in Proposition 8 is as follows. Given $\epsilon >0$ and a graph $G$ on $n$ vertices, let $t=\log (n/\epsilon )$. For a cluster $\mathrm{\Gamma }\in 𝒞$, extend $g$ by defining $g(\mathrm{\Gamma }):={\sum }_{\gamma \in \mathrm{\Gamma }}g(\gamma )$. Moreover, recall the Ursell function in (3). Then,

1. 1.

   Enumerate all clusters $\mathrm{\Gamma }\in 𝒞$ with ;

2. 2.

   For each such $\mathrm{\Gamma }$, compute $\mathrm{\Phi }(\mathrm{\Gamma })$, ${\prod }_{\gamma \in \mathrm{\Gamma }}w(\gamma )$, and $g(\mathrm{\Gamma })$;

3. 3.

   Compute

4. 4.

   Output $\exp (T_t(G))$.

Roughly speaking, this yields a good approximation because the KP criterion in Proposition 7 holds. All the computation is efficient because of the algorithmic techniques in [9, 20, 14].

Now we turn our attention to the hypergraph case and show Theorem 4. Let $H=(V,E)$ be a hypergraph. We will assume throughout this section that, for some constants $\mathrm{\Delta },k\ge 2$, vertices of $H$ have maximum degree $\mathrm{\Delta }$, and hyperedges of $H$ have maximum size $k$. Recall that the fractional hypergraph matching polytope is defined in (2), and the truncated version $P_{H,\delta }$ is defined by intersecting $P_H$ with $M_{\delta }^{}{}_{}{}^E$.

Our $\delta$ will satisfy that , in which case, if the degree of some $v$ is at most $\mathrm{\Delta }-1$, the corresponding constraint is always satisfied. Thus, we may assume that ${\mathrm{deg}}_H(v)=\mathrm{\Delta }$ for all $v\in V$.

Let $\mathrm{Flat}(H)$ be the flattened graph of $H$, namely its vertex set is still $V$, and for $u,v\in V$, $u$ and $v$ are adjacent if they appear in the same hyperedge $e$ for some $e\in E$. In other words, we replace each hyperedge $e$ by a clique on the vertex set of $e$. Notice that the maximum degree of $\mathrm{Flat}(H)$ is at most $\mathrm{\Delta }(k-1)$. Similar to (5), we have

where $𝒦(S)$ denote the connected components of the induced subgraph $\mathrm{Flat}(H)[S]$. Thus, we have a similar polymer model partition function

where

While (12) and (13) look identical to (6) and (7), the underlying graph is different and consequently Lemma 10 no longer applies. We may view this as a polymer model over $\mathrm{Flat}(H)$, by treating connected induced subgraphs of $\mathrm{Flat}(H)$ as polymers.

Directly applying the method of Lemma 10 would yield

This bound can only validate the Kotecký-Preiss criterion up to $\delta =\mathrm{\Theta }{\left(\frac{1}{\mathrm{\Delta }k}\right)}^{k-1}$. To get a better bound, we need a different polymer model.