<p>Consider three distinct sets <span class="math-container">$A, B, C$</span> of <span class="math-container">$N$</span> elements respectively. For each pair of sets, say <span class="math-container">$A,B$</span>, we introduce an variable for each combination of values <span class="math-container">$a,b$</span> as <span class="math-container">$x_{ab}$</span>. Similarly, we introduce a variable <span class="math-container">$y_{bc}$</span> for each <span class="math-container">$b \in B, c \in C$</span>, and <span class="math-container">$z_{ac}$</span> for each <span class="math-container">$a \in A$</span>, <span class="math-container">$c \in C$</span>.</p>

<p>Consider the following integer programming with the optimal solution as <span class="math-container">$OPT$</span>.</p>

<p><span class="math-container">$$\ \ \ \ \ \ \max \sum _{a \in A, b \in B, c \in C} x_{ab} \cdot y_{bc} \cdot z_{ac}$$</span>
<span class="math-container">$$s.t. \sum_{a \in A, b \in B} x_{ab} \le N$$</span>
<span class="math-container">$$\ \ \ \ \sum_{b \in B, c \in C} y_{bc} \le N$$</span>
<span class="math-container">$$\ \ \ \ \sum_{a \in A, c \in C} z_{ac} \le N$$</span>
<span class="math-container">$$x_{ab}, y_{bc}, z_{ac} \in \{0,1\}, \forall a \in A, b \in B, c \in C$$</span></p>

<p>Is the following decision problem polynomial-time solvable or NP-hard:
Given an input integer <span class="math-container">$k$</span>, whether <span class="math-container">$OPT &gt; k$</span> or not?</p>

CC BY-SA 4.0
2020-05-05T17:25:28.283Z
I think the maximum value is $N^{3/2}$. Each of the three conditions form a relation of size $N$. Given three relations $R(a,b), S(b,c), T(a,c)$, you can use AGM bound to upper bound the join size (which is number of triangles) as $N^{3/2}$. This bound is tight. You can see that by choosing $\sqrt{N}$ values in $A,B,C$ and forming a cartesian product. Take a look at worst-case optimal join in database literature.
karmanaut
CC BY-SA 4.0
2020-05-05T21:41:58.277Z
The $N^{3/2}$ is just an asymptotically tight upper bound, but not exact bound. How about when $\sqrt{N}$ is not a integer?
Xiao
CC BY-SA 4.0
2020-05-07T20:11:29.043Z
Since you ask about time poly$(N)$, and the only input is $N$, I assume you intend that $N$ is encoded in unary (so the input size is $N$).  Also, to ask about NP-hardness, you'd need to formulate it as a decision problem, which would presumably mean adding an additional parameter $k$ (also in unary?) and asking whether the value is at least $k$.  With these assumptions, the corresponding language is sparse, so is not NP-hard [unless P=NP](https://en.wikipedia.org/wiki/Sparse_language).
Neal Young
CC BY-SA 4.0
2020-05-09T21:24:23.527Z
I think sets A, B, C should also be taken as inputs？
Xiao
CC BY-SA 4.0
2020-05-10T20:54:04.597Z
But as you've defined the problem only the sizes of $A$, $B$, and $C$ matter, so the problem instance is fully specified by the single parameter $N$.  Unless I'm missing something.
Neal Young
CC BY-SA 4.0
2020-05-11T02:37:18.990Z
I see. On the other hand, is there any poly-time algorithm for answering this question?
Xiao
CC BY-SA 4.0
2020-05-27T09:14:10.207Z
The problem you give is not an integer programming, at least not one I know of. Moreover, it sounds to me more like a mathematical question, with no algorithmic flavor.
Yixin Cao
<integer-programming>
An integer programming on maximum number of triangles
Xiao
# An integer programming on maximum number of triangles

(Asked by: username_0 on 2020-05-05)

Consider three distinct sets $A, B, C$ of $N$ elements respectively. For each pair of sets, say $A,B$, we introduce an variable for each combination of values $a,b$ as $x\_{ab}$. Similarly, we introduce a variable $y\_{bc}$ for each $b \in B, c \in C$, and $z\_{ac}$ for each $a \in A$, $c \in C$.

Consider the following integer programming with the optimal solution as $OPT$.

$$\ \ \ \ \ \ \max \sum \_{a \in A, b \in B, c \in C} x\_{ab} \cdot y\_{bc} \cdot z\_{ac}$$
$$s.t. \sum\_{a \in A, b \in B} x\_{ab} \le N$$
$$\ \ \ \ \sum\_{b \in B, c \in C} y\_{bc} \le N$$
$$\ \ \ \ \sum\_{a \in A, c \in C} z\_{ac} \le N$$
$$x\_{ab}, y\_{bc}, z\_{ac} \in \{0,1\}, \forall a \in A, b \in B, c \in C$$

Is the following decision problem polynomial-time solvable or NP-hard:
Given an input integer $k$, whether $OPT > k$ or not?

**Tags:** integer-programming
> **Comments:**
> **username_1**: I think the maximum value is $N^{3/2}$. Each of the three conditions form a relation of size $N$. Given three relations $R(a,b), S(b,c), T(a,c)$, you can use AGM bound to upper bound the join size (which is number of triangles) as $N^{3/2}$. This bound is tight. You can see that by choosing $\sqrt{N}$ values in $A,B,C$ and forming a cartesian product. Take a look at worst-case optimal join in database literature.  
> **username_0**: The $N^{3/2}$ is just an asymptotically tight upper bound, but not exact bound. How about when $\sqrt{N}$ is not a integer?  
> **username_2**: Since you ask about time poly$(N)$, and the only input is $N$, I assume you intend that $N$ is encoded in unary (so the input size is $N$).  Also, to ask about NP-hardness, you'd need to formulate it as a decision problem, which would presumably mean adding an additional parameter $k$ (also in unary?) and asking whether the value is at least $k$.  With these assumptions, the corresponding language is sparse, so is not NP-hard [unless P=NP](https://en.wikipedia.org/wiki/Sparse_language).  
> **username_0**: I think sets A, B, C should also be taken as inputs？  
> **username_2**: But as you've defined the problem only the sizes of $A$, $B$, and $C$ matter, so the problem instance is fully specified by the single parameter $N$.  Unless I'm missing something.  
> **username_0**: I see. On the other hand, is there any poly-time algorithm for answering this question?  
> **username_3**: The problem you give is not an integer programming, at least not one I know of. Moreover, it sounds to me more like a mathematical question, with no algorithmic flavor.  

---

## 0 answers

