29
$\begingroup$

How does the computational complexity of the Subset Sum problem depend on the parameter $\alpha(S)$ of the input $(S, t)$, defined as follows?

Considering $S$ under the divisibility partial order, i.e. $s_1 \prec s_2 \iff s_1 \mid s_2$, define

$\qquad\qquad \displaystyle \alpha(S) = \max \{|V| \mid V\subseteq S, V$ an antichain$\}$

to be the maximum size of any subset of $S$ whose elements are pairwise relatively prime.

Subset Sum instances with $\alpha(S)=1$ are solvable in polynomial time. For example, if $S$ contains only powers of two, then $\alpha(S) = 1$, and an instance with set $S$ and any target $t$ is solvable in polynomial time.

In fact, when $\alpha(S)=1$, even the (harder) Knapsack problem is known to be solvable in polynomial time.$\dagger$

Are all Subset Sum instances with, say, $\alpha(S) = O(1)$ solvable in polynomial time?


$\dagger$ Solving sequential knapsack problems by M. Hartmann and T. Olmstead (1993)


$\endgroup$
1
  • 1
    $\begingroup$ Instead of "relation", I suggest using the terms "partial order". Also, on minimal thought, the Frobenius coin problem might be relevant (of course, not sure, though) $\endgroup$
    – Aryabhata
    Jul 12, 2013 at 0:58

1 Answer 1

4
$\begingroup$

This problem can be solved in polynomial time using linear programming, and this is actually true for any partial order $(S,\le)$. By the way, we can prove by induction that for any finite partial order set $(S,\le)$, there exists a finite set $S'\subseteq\mathbb{N}$ and a bijection $f:S\rightarrow S'$, such that for all $s_1,s_2\in S, s_1\le s_2 \Leftrightarrow f(s_1) | f(s_2)$.

Let $\mathcal{C}$ be the set formed by the chains in $S$. Remind that $C$ is a chain iff for all $v,v'$ in $C$, $v\le v'$ or $v'\le v$

Now create a boolean variable $x_v$ for each $v\in S$, and a boolean variable $y_C$ for each chain $C$. We can write the following linear program $(P)$ for our problem : $$ \begin{split} \text{Max} \displaystyle\sum\limits_{v\in S} x_v \\ \text{subject to} \displaystyle\sum\limits_{v\in C} &x_v \le 1, \forall C\in\mathcal{C}\\ &x_v \in \{0,1\}, v\in S \end{split} $$

and its dual $(D)$ :

$$ \begin{split} \text{Min} \displaystyle\sum\limits_{C\in \mathcal{C}} y_C\\ \text{subject to} \displaystyle\sum\limits_{C:v\in C} &y_C \ge 1, \forall v\in S\\ &y_C \in \{0,1\}, C\in \mathcal{C} \end{split} $$

Then the problem of finding the minimum cover of an ordered set by chains is the dual of our problem. Dilworth's theorem states that

There exists an antichain A, and a partition of the order into a family P of chains, such that the number of chains in the partition equals the cardinality of A

which means that the optimal solution of these two problems match : $Opt(P)=Opt(D)$

Let $(P^*)$ (resp. $(D^*)$) be the relaxation of $(P)$ (resp. $(D)$) i.e. the same linear program where all constraints $x_v\in\{0,1\}$ (resp. $y_C\in\{0,1\}$) are replaced by $x_v\in [0,1]$ (resp. $y_C\in [0,1]$). Let $Opt(P^*)$ and $Opt(D^*)$ be their optimal solutions. Since $\{0,1\}\subseteq [0,1]$ we have : $$ Opt(P)\le Opt(P^*) \text{ and } Opt(D^*)\le Opt(D) $$ and weak duality theorem establishes that $Opt(P^*)\le Opt(D^*)$ then by putting everything together we have : $$ Opt(P)= Opt(P^*)=Opt(D^*)=Opt(D) $$

Then, using Ellipsoid method, we can compute $Opt(P^*)$ ( $=Opt(P)$) in polynomial time. There are an exponential number of constraints but there exists a polynomial time separation oracle. Indeed given a solution $X$, we can enumerate all couples $s_1,s_2\in X$ and check if $s_1\le s_2$ or $s_2\le s_1$, and therefore decide in polynomial time whether $X$ is feasible or otherwise the constraint associated to the chain $\{v_1,v_2\}$ is violated.

$\endgroup$
3
  • $\begingroup$ Ellispoid method works whatever the number of constraints, if we have (1) a polynomial number of variables and (2) a separation oracle which given any solution $x$ decides in polynomial time whether $x$ is feasible or find a constraints violated by $x$. I recommend reading [www-math.mit.edu/~goemans/18433S09/ellipsoid.pdf], wikipedia is not very clear on this point $\endgroup$ May 25, 2018 at 18:01
  • $\begingroup$ Thanks for explaining why the exponential number of constraints is not a problem, and the relevance of duality. Very nice! $\endgroup$
    – D.W.
    May 25, 2018 at 20:12
  • $\begingroup$ I think this answer doesn't address the question, which seems to be about how the complexity of solving the Subset Sum Problem for a given set $S$ depends on $\alpha(S)$. And BTW, instead of Ellipsoid, can't one just use max-flow (and min-cut) to find the maximum anti-chain? See e.g. here... $\endgroup$
    – Neal Young
    Mar 13 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.