<p>Suppose I have $n$ variables $x_1,\ldots,x_n$ that satisfy some inequalities that are highly symmetric, e.g., for all $S\subset [n], |S|=k$ we have $\sum_{i\in S} f(x_i,k)\le \sum_{i\in [n]} g(x_i,k)$, where $f$ and $g$ are some simple functions, e.g., composed of addition, minimum etc.
Is there a polynomial algorithm to decide whether this system has an integer solution?
What if the situation is a bit more complex, like we have several inequalities of the above form and/or additional individual inequalities, e.g., $x_i\le b_i$?</p>

<p>Motivation:
Many classic problems can be brought to the above form, e.g., <a href="http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Gallai_theorem" rel="nofollow">http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Gallai_theorem</a> and <a href="http://en.wikipedia.org/wiki/Fulkerson%E2%80%93Chen%E2%80%93Anstee_theorem" rel="nofollow">http://en.wikipedia.org/wiki/Fulkerson%E2%80%93Chen%E2%80%93Anstee_theorem</a>.
For example in Erdos-Gallai we have $f=x_i+\min(x_i,k)-(k-1)$ and $g=\min(x_i,k)$.</p>

<p>Seems related but I don't see a direct connection:
<a href="http://arxiv.org/abs/1012.4941" rel="nofollow">http://arxiv.org/abs/1012.4941</a>.</p>

CC BY-SA 3.0
2015-01-21T12:36:13.490Z
Does addition distribute over $f$ and $g$?
András Salamon
CC BY-SA 3.0
2015-01-21T13:31:33.187Z
I am trying to see if there is some kind of algebraic structure.  As far as I understand, you have addition as one operation, and $f/g$ as other operations.  It then seems natural to ask whether $f(x)+f(y)=f(x+y)$, or even whether something like $f(x)+f(y)\ge f(x+y)$ always holds.
András Salamon
CC BY-SA 3.0
2015-01-21T15:17:23.373Z
@András: I didn't have any such things in mind, but if you have a positive result using stronger assumptions, I am also interested.
domotorp
CC BY-SA 3.0
2015-01-25T17:01:08.180Z
Taking the problem specification literally, it seems to me that the role of $S$ is unclear.  Isn't the condition on $f$ and $g$ equivalent to $\forall i. f(x_i) \le g(x_i)$?
Neal Young
CC BY-SA 3.0
2015-01-25T19:42:24.987Z
@Neal: Oops, I forgot that $f$ and $g$ can also depend on $|S|$, I hope it makes sense now.
domotorp
<linear-programming><integer-programming>
Are highly symmetric inequalities solvable over integers?
domotorp
# Are highly symmetric inequalities solvable over integers?

(Asked by: username_0 on 2015-01-20)

Suppose I have $n$ variables $x\_1,\ldots,x\_n$ that satisfy some inequalities that are highly symmetric, e.g., for all $S\subset [n], |S|=k$ we have $\sum\_{i\in S} f(x\_i,k)\le \sum\_{i\in [n]} g(x\_i,k)$, where $f$ and $g$ are some simple functions, e.g., composed of addition, minimum etc.
Is there a polynomial algorithm to decide whether this system has an integer solution?
What if the situation is a bit more complex, like we have several inequalities of the above form and/or additional individual inequalities, e.g., $x\_i\le b\_i$?

Motivation:
Many classic problems can be brought to the above form, e.g., <http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Gallai_theorem> and <http://en.wikipedia.org/wiki/Fulkerson%E2%80%93Chen%E2%80%93Anstee_theorem>.
For example in Erdos-Gallai we have $f=x\_i+\min(x\_i,k)-(k-1)$ and $g=\min(x\_i,k)$.

Seems related but I don't see a direct connection:
<http://arxiv.org/abs/1012.4941>.

**Tags:** linear-programming, integer-programming
> **Comments:**
> **username_1**: Does addition distribute over $f$ and $g$?  
> **username_1**: I am trying to see if there is some kind of algebraic structure.  As far as I understand, you have addition as one operation, and $f/g$ as other operations.  It then seems natural to ask whether $f(x)+f(y)=f(x+y)$, or even whether something like $f(x)+f(y)\ge f(x+y)$ always holds.  
> **username_0**: @András: I didn't have any such things in mind, but if you have a positive result using stronger assumptions, I am also interested.  
> **username_2**: Taking the problem specification literally, it seems to me that the role of $S$ is unclear.  Isn't the condition on $f$ and $g$ equivalent to $\forall i. f(x_i) \le g(x_i)$?  
> **username_0**: @Neal: Oops, I forgot that $f$ and $g$ can also depend on $|S|$, I hope it makes sense now.  

---

## 0 answers

