<p>Playing around I ran into a problem which looks like a Exact Set Covering / Partition Problem, but I am unable to find a reduction to categorize the complexity of the problem, despite it looks NP-Hard. I will informally state the problem and some of the properties, since describing the problem as a whole would be too lengthy. </p>

<blockquote>
  <h3><strong>Non-linear Constrained Optimal Exact Cover</strong></h3>
  
  <p>Consider a finite set $C=\{1,2,\ldots,m\}$ of elements and a vector $\mathbf{w}=\{w_j ~|~ j\in C\}$ of associated weights. 
  The collection $S=\{s_1,s_2,\ldots, s_n | s_i\subset C\}$ contains every subset of combinations of elements of $C$ <strong>that fulfills:</strong>  $$f(\mathbf{w}_{s_i})\ge 0, \forall s_i\in S;\quad \text{ where } \mathbf{w}_{s_i}=\{w_j ~|~ j\in s_i\}. $$ 
  Find the subcollection ${S}^{*}$ of $S$ such that </p>
  
  <p>($i$) each element in $C$ is contained in exactly one subset of ${S}^{*}$</p>
  
  <p>($ii$) $g(S^*)=\sum\limits_{i=1,\ldots,n} g(\mathbf{w}_{s_i})$ is maximized.</p>
  
  <p><strong>Example</strong>: 
  $C=\{1,2,3,4\}$ and $\{w_1,w_2,w_3,w_4\}$.</p>
  
  <p>Given the weights, the non linear constraint $f(\mathbf{w_{s_i}})\ge 0$ implies:
  $$S=\{\{1\},\{2\},\{3\},\{4\},\{1,2\},\{2,3\},\{1,4\},\{1,2,3\},\{1,3,4\}\}$$
  having each subset $s_i\in S$:
  $$\{g(\mathbf{w_{s_i}}) ~|~ s_i\in S\}=\{4,2,1,5,2,7,8,2,3\}.$$
  <strong>Solution</strong>: $S^*=\{\{2,3\},\{1,4\}\},$ since each of the elements of $C$ is contained in exactly one subset of $S^*$ and $g(S^*)$ is the maximum possible. </p>
</blockquote>

<p>Note that the <a href="https://www.nada.kth.se/~viggo/wwwcompendium/node147.html" rel="nofollow noreferrer">Minimum Exact Cover Problem</a> is related but deals with a different objective function (minimize the cardinality of the set) and the general description of the problem does not constrain the subsets that can appear in an instance for S (unlike this problem).</p>

<p>My feeling is that the problem is NP-Hard, since as increasing the size of $C$, the possible set of partitions increase quickly (<a href="https://en.wikipedia.org/wiki/Catalan_number" rel="nofollow noreferrer">Catalan numbers</a>). However, I do understand that the reduction in the feasible space may vary the complexity.</p>

<p>My goal is to find the conditions on the functions such that the
problem remains NP-Hard or, if none if it is NP-hard for any pair besides the trivial functions. I have been working a bit into that, but this is not my field of expertise and I am suspicious that a similar work has been done or that a reduction in trivial for expert eyes or at least a categorization of the problem. </p>

<hr>

<blockquote>
  <p><strong>Notes</strong></p>
  
  <ul>
  <li>$ ~ f$ and $g$ are non linear functions that depends on the
  partition. It is hard to define them hereby, but they aim to
  evaluate the subset similarity, e.g., $f(\mathbf{w}_{s_i})\ge 0$ ensure
  that the elements weights are similar enough among each other.</li>
  <li>For any instance of the problem there exists at least one feasible
  partition. The partition that includes each element in a subset
  ${S}^{'}=\{\{1\},\{2\},\ldots,\{m\}\}$ is feasible (fulfills
  condition ($i$)), but it may not be optimal.</li>
  <li>Clearly, there are some functions for which the problem seems
  trivial, i.e., if the constraints are $f(\mathbf{w}_{s_i})=-|\mathbf{w}_{s_i}|+1 \ge 0$ then
  only the partition
  $S^{'}$ is feasible and then the solution
  can be obtained in O(1).</li>
  </ul>
</blockquote>

CC BY-SA 3.0
2018-01-05T14:30:28.137Z
Yes, I can understand the problem now.  So your question is, for what classes of pairs of functions $(f,g)$ is the resulting problem NP-hard?
Neal Young
CC BY-SA 3.0
2018-01-05T14:34:22.157Z
Right, the question would be which are the restrictions on the class of functions I shall be looking at to make sure that complexity remains NP-Hard or not, and why? If that makes sense... I have a family of functions pretty particular and I want to know what should I pay attention to?
Paul Knight
CC BY-SA 3.0
2018-01-06T00:58:53.440Z
That's a pretty open-ended question, and can probably be answered only if there happens to be someone out there who just happens to have studied your problem (or something equivalent).  You _might_ get more traction if you, say, give a particular $(f, g)$ pair and ask whether the problem is NP-hard for that pair.  Or, ask whether someone can show it is NP-hard for _any_ pair.
Neal Young
CC BY-SA 3.0
2018-01-12T20:56:36.893Z
It now says "or, if none if it is NP-hard for any pair besides the trivial functions."  I'm confused by this.  For what trivial functions is it NP-hard?  Secondly, I noticed you added a bounty.  I'd guess that to get an answer you'll need to set a more specific goal.  E.g., "show that for some pair (f, g) is is NP-hard.
Neal Young
CC BY-SA 3.0
2018-01-12T22:36:43.400Z
In my notes, you can find a function for which the solution is trivial, i.e., for which the solution is not NP-Hard but a trivial solution (Please read the 3rd bullet point).

Regarding the second point is that I deliberately do not know which function I have there.
Paul Knight
<cc.complexity-theory><np-hardness><optimization><partition-problem><covering-problems>
Is Non-linear Constrained Optimal Exact Cover NP-Hard?
Paul Knight
# Is Non-linear Constrained Optimal Exact Cover NP-Hard?

(Asked by: username_0 on 2018-01-03)

Playing around I ran into a problem which looks like a Exact Set Covering / Partition Problem, but I am unable to find a reduction to categorize the complexity of the problem, despite it looks NP-Hard. I will informally state the problem and some of the properties, since describing the problem as a whole would be too lengthy.

> ### **Non-linear Constrained Optimal Exact Cover**
>
> Consider a finite set $C=\{1,2,\ldots,m\}$ of elements and a vector $\mathbf{w}=\{w\_j ~|~ j\in C\}$ of associated weights.
> The collection $S=\{s\_1,s\_2,\ldots, s\_n | s\_i\subset C\}$ contains every subset of combinations of elements of $C$ **that fulfills:** $$f(\mathbf{w}\_{s\_i})\ge 0, \forall s\_i\in S;\quad \text{ where } \mathbf{w}\_{s\_i}=\{w\_j ~|~ j\in s\_i\}. $$
> Find the subcollection ${S}^{\*}$ of $S$ such that
>
> ($i$) each element in $C$ is contained in exactly one subset of ${S}^{\*}$
>
> ($ii$) $g(S^\*)=\sum\limits\_{i=1,\ldots,n} g(\mathbf{w}\_{s\_i})$ is maximized.
>
> **Example**:
> $C=\{1,2,3,4\}$ and $\{w\_1,w\_2,w\_3,w\_4\}$.
>
> Given the weights, the non linear constraint $f(\mathbf{w\_{s\_i}})\ge 0$ implies:
> $$S=\{\{1\},\{2\},\{3\},\{4\},\{1,2\},\{2,3\},\{1,4\},\{1,2,3\},\{1,3,4\}\}$$
> having each subset $s\_i\in S$:
> $$\{g(\mathbf{w\_{s\_i}}) ~|~ s\_i\in S\}=\{4,2,1,5,2,7,8,2,3\}.$$
> **Solution**: $S^\*=\{\{2,3\},\{1,4\}\},$ since each of the elements of $C$ is contained in exactly one subset of $S^\*$ and $g(S^\*)$ is the maximum possible.

Note that the [Minimum Exact Cover Problem](https://www.nada.kth.se/~viggo/wwwcompendium/node147.html) is related but deals with a different objective function (minimize the cardinality of the set) and the general description of the problem does not constrain the subsets that can appear in an instance for S (unlike this problem).

My feeling is that the problem is NP-Hard, since as increasing the size of $C$, the possible set of partitions increase quickly ([Catalan numbers](https://en.wikipedia.org/wiki/Catalan_number)). However, I do understand that the reduction in the feasible space may vary the complexity.

My goal is to find the conditions on the functions such that the
problem remains NP-Hard or, if none if it is NP-hard for any pair besides the trivial functions. I have been working a bit into that, but this is not my field of expertise and I am suspicious that a similar work has been done or that a reduction in trivial for expert eyes or at least a categorization of the problem.

---

> **Notes**
>
> * $ ~ f$ and $g$ are non linear functions that depends on the
>   partition. It is hard to define them hereby, but they aim to
>   evaluate the subset similarity, e.g., $f(\mathbf{w}\_{s\_i})\ge 0$ ensure
>   that the elements weights are similar enough among each other.
> * For any instance of the problem there exists at least one feasible
>   partition. The partition that includes each element in a subset
>   ${S}^{'}=\{\{1\},\{2\},\ldots,\{m\}\}$ is feasible (fulfills
>   condition ($i$)), but it may not be optimal.
> * Clearly, there are some functions for which the problem seems
>   trivial, i.e., if the constraints are $f(\mathbf{w}\_{s\_i})=-|\mathbf{w}\_{s\_i}|+1 \ge 0$ then
>   only the partition
>   $S^{'}$ is feasible and then the solution
>   can be obtained in O(1).

**Tags:** cc.complexity-theory, np-hardness, optimization, partition-problem, covering-problems

> **Comments:**
> **username_1**: Yes, I can understand the problem now.  So your question is, for what classes of pairs of functions $(f,g)$ is the resulting problem NP-hard?  
> **username_0**: Right, the question would be which are the restrictions on the class of functions I shall be looking at to make sure that complexity remains NP-Hard or not, and why? If that makes sense... I have a family of functions pretty particular and I want to know what should I pay attention to?  
> **username_1**: That's a pretty open-ended question, and can probably be answered only if there happens to be someone out there who just happens to have studied your problem (or something equivalent).  You _might_ get more traction if you, say, give a particular $(f, g)$ pair and ask whether the problem is NP-hard for that pair.  Or, ask whether someone can show it is NP-hard for _any_ pair.  
> **username_1**: It now says "or, if none if it is NP-hard for any pair besides the trivial functions."  I'm confused by this.  For what trivial functions is it NP-hard?  Secondly, I noticed you added a bounty.  I'd guess that to get an answer you'll need to set a more specific goal.  E.g., "show that for some pair (f, g) is is NP-hard.  
> **username_0**: In my notes, you can find a function for which the solution is trivial, i.e., for which the solution is not NP-Hard but a trivial solution (Please read the 3rd bullet point).  Regarding the second point is that I deliberately do not know which function I have there.  

---

## 0 answers

