2
$\begingroup$

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 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). 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).
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Neal Young Jan 5 '18 at 14:30
  • $\begingroup$ 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? $\endgroup$ – Paul Knight Jan 5 '18 at 14:34
  • 1
    $\begingroup$ 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. $\endgroup$ – Neal Young Jan 6 '18 at 0:58
  • $\begingroup$ 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. $\endgroup$ – Neal Young Jan 12 '18 at 20:56
  • $\begingroup$ 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. $\endgroup$ – Paul Knight Jan 12 '18 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.