The Complexity of Recognizing Facets for the Knapsack Polytope

By Theorem 2.1, it suffices to show that is reducible to CSS. Given instance $(V,E,k)$ of the exact vertex cover problem, define the following CSS instance. Assume $V=\{v_{1},\ldots,v_{n}\}$ and $E=\{e_{1},\ldots,e_{m}\}$. For $i=1,\ldots,n$, define $w_{i}:=1+\sum_{j=1}^{m}(n+1)^{j}\mathbbm{1}(v_{i}\in e_{j})$. For $j=1,\ldots,m$, define $w_{n+j}:=(n+1)^{j}$. Define $t:=n-k+1+\sum_{j=1}^{m}(n+1)^{j}$. Then the CSS instance $(w,t)$ has polynomial encoding size with respect to the input size of the EVC instance $(V,E,k)$.

Let $\tilde{I}:=\{i_{1},\ldots,i_{p}\}\subseteq[n]$ and $\tilde{V}:=\{v_{i_{1}},\ldots,v_{i_{p}}\}\subseteq V$. Note that $\tilde{V}$ is a vertex cover of $G$ if and only if the ($q+1$)-th digit of $w(\tilde{I})$ (in base $n+1$) is at least $1$ for $q=1,\ldots,n$. Define $\bar{I}:=[n]\setminus\tilde{I}$. Then $\tilde{V}$ is a vertex cover of $G$ if and only if the ($q+1$)-th digit of $w(\bar{I})$ is at most $1$ for $q=1,\ldots,n$. Also note that the first digit of $w(\bar{I})$ is $n-p$. Define $\bar{J}:=\{n+j:j\in[m],~{}e_{j}\cap\bar{V}=\emptyset\}$. Then $\tilde{V}$ being a vertex cover of $G$ implies $w(\bar{I}\cup\bar{J})=n-p+\sum_{j=1}^{m}(n+1)^{j}$. On the other hand, $w(S)=n-p+\sum_{j=1}^{m}(n+1)^{j}$ implies $|[n]\setminus S|=p$ and $\{v_{i}:i\in[n]\setminus S\}$ being a vertex cover of $G$. Then by definitions of the EVC instance $(V,E,k)$ and the CSS instance $(w,t)$, we have the EVC instance has a “yes” anwser if and only if the CSS instance has a “yes” answer.

It is easy to see that EK$\in$$\mathsf{D^{p}}$. We next show a reduction from CSS to EK. Let $(w,t)$ be a CSS instance. Then this instance has “yes” answer if and only if $\max\{w^{\mathsf{T}}x:w^{\mathsf{T}}x\leq t,x\in\{0,1\}^{n}\}=t-1$, which is a “yes” answer to a particular EK instance. ∎

By Theorem 2.2, it suffices to establish that CSS is reducible to the KP supporting hyperplane problem. Given a CSS instance $(w,t)$, consider the following instance of the KP supporting hyperplane problem: Given an inequality $\sum_{i=1}^{n}w_{i}x_{i}\leq t-1$ and a KP $\operatorname{conv}\left(\{x\in\{0,1\}^{n}:\sum_{i=1}^{n}w_{i}x_{i}\leq t\}\right)$, is it true that this inequality is valid for the KP and the corresponding hyperplane has a nonempty intersection with the KP? It is easy to see that this KP supporting hyperplane instance has a “yes” answer if and only if $\sum_{i=1}^{n}w_{i}x_{i}=t$ has no solution over $x\in\{0,1\}^{n}$, but there exists $x^{*}\in\{0,1\}^{n}$ such that $\sum_{i=1}^{n}w_{i}x^{*}_{i}=t-1$. This is equivalent to saying that the CSS instance $(w,t)$ has a “yes” answer. ∎

It suffices to show that CSS is reducible to KNAPSACK FACETS, as CSS is $\mathsf{D^{p}}$-complete according to Theorem 2.2. Consider any CSS instance $(w,t)$, i.e., “is it true that there exists $S\subseteq[n]$ such that $w(S)=t-1$, but there does not exist $T\subseteq[n]$ such that $w(T)=t$?” Without loss of generality, here we assume that $w_{i}\leq t-1$ for all $i\in[n]$ and $t\geq 2$.

We next construct a KNAPSACK FACETS instance. Let $L=w([n]),~{}r=\lceil\log_{2}(30L+20)-1\rceil$, and

Here $N:=2r+n+4$ is the dimension of the vectors $a$ and $\alpha$. Consider the following instance of KNAPSACK FACETS: Given an inequality $\alpha^{\mathsf{T}}x\leq\beta$ and a KP $\operatorname{conv}(\{x\in\{0,1\}^{N}:a^{\mathsf{T}}x\leq b\})$, is this inequality facet-defining to the KP? It is easy to verify that the input size of this KNAPSACK FACETS instance is polynomial of that of the CSS instance $(w,t)$. To complete the proof of this theorem, we are going to show: there is a “yes” answer to the CSS problem $(w,t)$ if and only if $\alpha^{\mathsf{T}}x\leq\beta$ is a facet-defining inequality to the KP $\operatorname{conv}(\{x\in\{0,1\}^{N}:a^{\mathsf{T}}x\leq b\})$.

Given the CSS instance and the KNAPSACK FACETS instance, we have the following claims.

• Proof of claim. The claim follows from $\sum_{i=1}^{2r}f_{i}=f_{2r+2}\geq\frac{\sqrt{2}-1}{4}\sqrt{2}^{2r+2}>2^{r+1}/10\geq 2^{\log_{2}(30L+20)}/10=3L+2$, where the first equality is from Observation 1, the second inequality is from Observation 2 and the last inequality is from the definition of $r$. $\hfill\diamond$

• Proof of claim. Note that for $\gamma=1,\ldots,r$, by our definition in (2)-(5), both inequalities $\sum_{i=1}^{2\gamma+1}\alpha_{i}x_{i}\leq\sum_{i=1}^{2\gamma}f_{i}$ and $\sum_{i=1}^{2\gamma+1}a_{i}x_{i}\leq\sum_{i=1}^{2\gamma}tf_{i}$ are identical to $\sum_{i=1}^{2\gamma+1}f_{i}x_{i}\leq\sum_{i=1}^{2\gamma}f_{i}$. We prove a stronger version of the claim: For $\gamma=1,\ldots,r$, inequality $\sum_{i=1}^{2\gamma+1}\alpha_{i}x_{i}\leq\sum_{i=1}^{2\gamma}f_{i}$ is a facet-defining inequality for KP $\operatorname{conv}(\{x\in\{0,1\}^{2\gamma+1}:\sum_{i=1}^{2\gamma+1}a_{i}x_{i}\leq\sum_{i=1}^{2\gamma}tf_{i}\})$. We proceed by induction on $\gamma$. When $\gamma=1$, the claim is: $x_{1}+x_{2}+x_{3}\leq 2$ is facet-defining for $\operatorname{conv}(\{x\in\{0,1\}^{3}:x_{1}+x_{2}+x_{3}\leq 2\})$, which is obviously true. Assume that this claim is true when $\gamma=R-1$ for some integer $R\in[2,r-1]$: $\sum_{i=1}^{2R-1}f_{i}x_{i}\leq\sum_{i=1}^{2R-2}f_{i}$ is a facet-defining inequality for $\operatorname{conv}(\{x\in\{0,1\}^{2R-1}:\sum_{i=1}^{2R-1}f_{i}x_{i}\leq\sum_{i=1}^{2R-2}f_{i}\})$. So there exists affinely independent points $v_{1},\ldots,v_{2R-1}\in\{0,1\}^{2R-1}$, satisfying $\sum_{i=1}^{2R-1}f_{i}x_{i}\leq\sum_{i=1}^{2R-2}f_{i}$ at equality. For $v\in\{0,1\}^{2R-1}$, let $(v,0,1)$ denote the binary point in $\{0,1\}^{2R+1}$ obtained by appending to $v$ two new components with values $0$ and $1$. It is then easy to verify that, for any $j\in[2R-1],x=(v_{j},0,1)$ satisfies $\sum_{i=1}^{2R+1}f_{i}x_{i}\leq\sum_{i=1}^{2R}f_{i}$ at equality as $f_{2R+1}=f_{2R}+f_{2R-1}$. Define $p:=(1,\ldots,1,0)\in\{0,1\}^{2R+1}$, then $\sum_{i=1}^{2R+1}f_{i}p_{i}=\sum_{i=1}^{2R}f_{i}$. Define $q:=(0,\ldots,0,1,1)\in\{0,1\}^{2R+1}$, then $\sum_{i=1}^{2R+1}f_{i}q_{i}=f_{2R}+f_{2R+1}=\sum_{i=1}^{2R}f_{i}$. Here the last equality is from Observation 1. Therefore, we have obtained the following $2R+1$ binary points in $\{0,1\}^{2R+1}:(v_{1},0,1),\ldots,(v_{2R-1},0,1),p,q$, where $v_{1},\ldots,v_{2R-1}$ are affinely independent in $\{0,1\}^{2R-1}$. It is easy to see that these $2R+1$ binary points are affinely independent in $\{0,1\}^{2R+1}$, and satisfy $\sum_{i=1}^{2R+1}f_{i}x_{i}\leq\sum_{i=1}^{2R}f_{i}$ at equality. $\hfill\diamond$

• Proof of claim. First, let’s verify that $\sum_{i=1}^{2r+2}\alpha_{i}x_{i}\leq\sum_{i=1}^{2r}f_{i}$ is valid for such KP. When $x_{2r+2}=0$, it is trivially valid. When $x_{2r+2}=1$, the knapsack constraint implies that $\sum_{i=1}^{2r+1}tf_{i}x_{i}\leq\sum_{i=1}^{2r}tf_{i}-t(2L+1)-1$. In this case $\sum_{i=1}^{2r+1}f_{i}x_{i}\leq\sum_{i=1}^{2r}f_{i}-2L-2$, which means that $\sum_{i=1}^{2r+1}f_{i}x_{i}+(2L+2)x_{2r+2}\leq\sum_{i=1}^{2r}f_{i}$ is a valid inequality. Second, from the last Claim 2, it suffices to show that there exists a binary point $x^{*}\in\{0,1\}^{2r+2}$ with $x^{*}_{2r+2}=1$, such that $\sum_{i=1}^{2r+1}a_{i}x^{*}_{i}+a_{2r+2}\leq\sum_{i=1}^{2r}tf_{i}$ while $\sum_{i=1}^{2r+1}\alpha_{i}x^{*}_{i}+\alpha_{2r+2}=\sum_{i=1}^{2r}f_{i}$. By definition of $a$ in (2) and $\alpha$ in (4), it suffices to find a binary point $x^{*}$, such that $\sum_{i=1}^{2r+1}f_{i}x^{*}_{i}=\sum_{i=1}^{2r}f_{i}-2L-2$. From the above Claim 1, $\sum_{i=1}^{2r}f_{i}-2L-2\geq L$. By Lemma 1, we know such binary point $x^{*}$ must exist. $\hfill\diamond$

• Proof of claim. By definition of $a$ in (2) and $\alpha$ in (4), we need to show that inequality

  $$\sum_{i=1}^{2r+1}f_{i}x_{i}+\left(2L+2\right)x_{2r+2}+\sum_{i=2r+3}^{2r+n+2}w_{i-2r-2}x_{i}\leq\sum_{i=1}^{2r}f_{i}$$

  (6)

  is facet-defining for the KP defined by the following knapsack constraint:

  $$\sum_{i=1}^{2r+1}tf_{i}x_{i}+\big{(}t(2L+1)+1\big{)}x_{2r+2}+\sum_{i=2r+3}^{2r+n+2}(t+1)w_{i-2r-2}x_{i}\leq\sum_{i=1}^{2r}tf_{i}.$$

  (7)

  First of all, we verify that inequality (6) is indeed valid for the KP defined by constraint (7). For any binary point $x\in\{0,1\}^{2r+n+2}$, knapsack constraint (7) implies that

  $$\sum_{i=1}^{2r+1}f_{i}x_{i}\leq\sum_{i=1}^{2r}f_{i}-(2L+1)x_{2r+2}\\ -\sum_{i=2r+3}^{2r+n+2}w_{i-2r-2}x_{i}-\left\lceil\frac{x_{2r+2}+\sum_{i=2r+3}^{2r+n+2}w_{i-2r-2}x_{i}}{t}\right\rceil.$$

  Therefore, we have

  $$\sum_{i=1}^{2r+1}f_{i}x_{i}+\left(2L+2\right)x_{2r+2}+\sum_{i=2r+3}^{2r+n+2}w_{i-2r-2}x_{i}\\ \leq\sum_{i=1}^{2r}f_{i}+x_{2r+2}-\left\lceil\frac{x_{2r+2}+\sum_{i=2r+3}^{2r+n+2}w_{i-2r-2}x_{i}}{t}\right\rceil\leq\sum_{i=1}^{2r}f_{i},$$

  i.e., inequality (6) is valid. To complete the proof, it suffices to show that there exist $2r+n+2$ affinely independent binary points satisfying the knapsack constraint (7), on which (6) holds at equality. From the last Claim 3, we can find $2r+2$ affinely independent binary points $v_{1},\ldots,v_{2r+2}$ in $\{0,1\}^{2r+2}$ satisfying $\sum_{i=1}^{2r+1}f_{i}x_{i}+\big{(}2L+2\big{)}x_{2r+2}=\sum_{i=1}^{2r}f_{i}$ and $\sum_{i=1}^{2r+1}tf_{i}x_{i}+\left(t(2L+1)+1\right)x_{2r+2}\leq\sum_{i=1}^{2r}tf_{i}.$ It implies that $(v_{1},0,\ldots,0),\ldots,(v_{2r+2},0,\ldots,0)$ are affinely independent in $\{0,1\}^{2r+n+2}$, satisfying the knapsack constraint (7), and satisfying (6) at equality. Now, for each $i\in[n]$, consider $\sum_{i=1}^{2r}f_{i}-2L-2-w_{i}$. By Claim 1, we know that $\sum_{i=1}^{2r}f_{i}-2L-2-w_{i}\geq 0$. So from Lemma 1, we can find $x^{*}$ with $x^{*}_{2r+2}=x^{*}_{2r+2+i}=1$, and $x^{*}_{2r+2+j}=0$ for all $j\in[n]\setminus\{i\}$, and $\sum_{i=1}^{2r+1}f_{i}x^{*}_{i}=\sum_{i=1}^{2r}f_{i}-2L-2-w_{i}$. Also note that $w_{i}\leq t-1$. It is then easy to verify that $x^{*}$ satisfies the knapsack constraint (7), and satisfies (6) at equality. Therefore, we have found in total $2r+n+2$ binary points that satisfy knapsack constraint (7), and satisfy (6) at equality. Moreover, these $2r+n+2$ points are obviously affinely independent. $\hfill\diamond$

Now, we are ready to prove the validity of the reduction: there is a “yes” answer to the CSS instance $(w,t)$ if and only if $\alpha^{\mathsf{T}}x\leq\beta$ is a facet-defining inequality for the KP $\operatorname{conv}(\{x\in\{0,1\}^{N}:a^{\mathsf{T}}x\leq b\})$.

We first verify that $w(S)\neq t$ for all $S\subseteq[n]$ if and only if inequality $\alpha^{\mathsf{T}}x\leq\beta$ is valid for the KP defined by $a^{\mathsf{T}}x\leq b$. In other words, we would like to show that $w(S)\neq t$ for all $S\subseteq[n]$ if and only if for all $\bar{x}\in\{0,1\}^{N}$ with $a^{\mathsf{T}}\bar{x}\leq b$, we have $\alpha^{\mathsf{T}}\bar{x}\leq\beta$. Consider an arbitrary $\bar{x}\in\{0,1\}^{N}$ with $a^{\mathsf{T}}\bar{x}\leq b$. Depending on the values of $\bar{x}_{N-1}$ and $\bar{x}_{N}$, we consider the following four cases.

1. (1)

   $\bar{x}_{N-1}=1,\bar{x}_{N}=0$. In this case, $a^{\mathsf{T}}x\leq b$ reduces to $\sum_{i=1}^{2r+n+2}a_{i}x_{i}\leq\sum_{i=1}^{2r}tf_{i}$, and $\alpha^{\mathsf{T}}x\leq\beta$ is the same as $\sum_{i=1}^{2r+n+2}\alpha_{i}x_{i}\leq\sum_{i=1}^{2r}f_{i}$. From Claim 4, we have that $\alpha^{\mathsf{T}}\bar{x}\leq\beta$ is always satisfied in this case.

2. (2)

   $\bar{x}_{N-1}=1,\bar{x}_{N}=1$. From $a^{\mathsf{T}}\bar{x}\leq b$, we have

   $$\sum_{i=1}^{2r+1}tf_{i}\bar{x}_{i}+\big{(}t(2L+1)+1\big{)}\bar{x}_{2r+2}+(t+1)\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}\leq\sum_{i=1}^{2r}tf_{i}-t-1.$$

   Since $\bar{x}\in\{0,1\}^{N}$, we have $\sum_{i=1}^{2r+1}f_{i}\bar{x}_{i}\in\mathbb{Z}$. It implies that

   $$\sum_{i=1}^{2r+1}f_{i}\bar{x}_{i}\leq\sum_{i=1}^{2r}f_{i}-1-(2L+1)\bar{x}_{2r+2}\\ -\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}-\left\lceil\frac{1+\bar{x}_{2r+2}+\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}}{t}\right\rceil.$$

   Hence, in this case we always have

   	$\displaystyle\alpha^{\mathsf{T}}\bar{x}=$	$\displaystyle\sum_{i=1}^{2r+1}f_{i}\bar{x}_{i}+(2L+2)\bar{x}_{i+2r+2}+\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}+f_{2r+1}+t+2L+1$
   	$\displaystyle\leq$	$\displaystyle\sum_{i=1}^{2r+1}f_{i}+\bar{x}_{2r+2}+t+2L-\left\lceil\frac{1+\bar{x}_{2r+2}+\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}}{t}\right\rceil$
   	$\displaystyle\leq$	$\displaystyle\sum_{i=1}^{2r+1}f_{i}+t+2L=\beta-1.$

3. (3)

   $\bar{x}_{N-1}=0,\bar{x}_{N}=0$. In this case, if $\bar{x}_{2r+2}=0$, then $\alpha^{\mathsf{T}}\bar{x}\leq\sum_{i=1}^{2r+1}f_{i}+\sum_{i=1}^{n}w_{i}<\beta$. So we assume $\bar{x}_{2r+2}=1$. Then from $a^{\mathsf{T}}\bar{x}\leq b$, we have

   $$\sum_{i=1}^{2r+1}tf_{i}\bar{x}_{i}+(t+1)\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}\leq\sum_{i=1}^{2r+1}tf_{i}+t^{2}+t.$$

   This implies

   $$\sum_{i=1}^{2r+1}f_{i}\bar{x}_{i}\leq\sum_{i=1}^{2r+1}f_{i}+t+1-\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}-\left\lceil\frac{\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}}{t}\right\rceil.$$

   (8)

   Depending on the value of $\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}$, we further consider the following three cases.

   • (3a)

     If $\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}\leq t-1$, then $\alpha^{\mathsf{T}}\bar{x}\leq\sum_{i=1}^{2r+2}\alpha_{i}+\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}\leq\sum_{i=1}^{2r+1}f_{i}+2L+2+t-1=\beta$.

   • (3b)

     If $\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}=t$, then consider the new point $\hat{x}\in\{0,1\}^{N}$ with $\hat{x}_{i}=1$ for $i=1,\ldots,2r+2,\hat{x}_{i}=\bar{x}_{i}$ for $i=2r+3,\ldots,2r+n+2,\hat{x}_{N-1}=\hat{x}_{N}=0$. We have $a^{\mathsf{T}}\hat{x}=\sum_{i=1}^{2r+1}tf_{i}+t(2L+1)+1+t(t+1)=b$ while $\alpha^{\mathsf{T}}\hat{x}=\sum_{i=1}^{2r+1}f_{i}+2L+2+t=\beta+1$. So here $\hat{x}$ is in the KP but it does not satisfy the inequality $\alpha^{\mathsf{T}}x\leq\beta$.

   • (3c)

     If $\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}\geq t+1$, then (8) implies that $\sum_{i=1}^{2r+1}f_{i}\bar{x}_{i}\leq\sum_{i=1}^{2r+1}f_{i}+t-\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}-1$. It implies that $\alpha^{\mathsf{T}}\bar{x}=\sum_{i=1}^{2r+1}f_{i}\bar{x}_{i}+2L+2+\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}\leq\beta$.

   Cases (3a)-(3c) imply that $\alpha^{\mathsf{T}}x\leq\beta$ is valid for any binary point $\bar{x}$ satisfying $a^{\mathsf{T}}\bar{x}\leq b$ and $\bar{x}_{N-1}=\bar{x}_{N}=0$ if there does not exist $S\subseteq[n]$ such that $w(S)=t$, in which case (3b) does not happen. On the other hand, if there exists $S\subseteq[n]$ such that $w(S)=t$, then one can construct $\hat{x}$ like in case (3b) to show that $\alpha^{\top}x\leq\beta$ is not valid. Therefore, $\alpha^{\mathsf{T}}x\leq\beta$ is valid for any binary point $\bar{x}$ satisfying $a^{\mathsf{T}}\bar{x}\leq b$ and $\bar{x}_{N-1}=\bar{x}_{N}=0$ if and only if there does not exist $S\subseteq[n]$ such that $w(S)=t$.

4. (4)

   $\bar{x}_{N-1}=0,\bar{x}_{N}=1$. In this case, if $\bar{x}_{2r+2}=0$, then $\alpha^{\mathsf{T}}\bar{x}\leq\sum_{i=1}^{2r+1}f_{i}+\sum_{i=1}^{n}w_{i}<\beta$. So we assume $\bar{x}_{2r+2}=1$. Then $a^{\mathsf{T}}\bar{x}\leq b$ reduces to

   $$\sum_{i=1}^{2r+1}tf_{i}\bar{x}_{i}+(t+1)\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}\leq\sum_{i=1}^{2r+1}tf_{i}+t^{2}-1.$$

   This implies

   $$\sum_{i=1}^{2r+1}f_{i}\bar{x}_{i}\leq\sum_{i=1}^{2r+1}f_{i}+t-\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}-\left\lceil\frac{1+\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}}{t}\right\rceil.$$

   (9)

   If $\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}\leq t-1$, then $\alpha^{\mathsf{T}}\bar{x}\leq\sum_{i=1}^{2r+2}\alpha_{i}+\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}\leq\sum_{i=1}^{2r+1}f_{i}+2L+2+t-1=\beta$. If $\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}\geq t$, then (9) yields that $\sum_{i=1}^{2r+1}f_{i}\bar{x}_{i}\leq\sum_{i=1}^{2r+1}f_{i}+t-\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}-2$. Therefore, $\alpha^{\mathsf{T}}\bar{x}=\sum_{i=1}^{2r+1}f_{i}\bar{x}_{i}+2L+2+\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}\leq\beta-1$.