3
$\begingroup$

Suppose we have a set of binary variables $a_1, ..., a_n$ that $a_i\in\{0,1\}$. Now we define $m$ and functions over a subset of them: $$j\in\{1,...,m\}: f_j=x_1\land x_2\land...\land x_k$$ in which $$\{x_1,...,x_k\}\subset\{a_1,...,a_n\}$$

Suppose that each variable $a_i$ has also a cost $c_i$ assigned to it and every function $f_j$ has a profit $p_j$ associated with it. Both variables are non-negative $\forall i,j: p_j,c_i\ge 0$.

The problem is how to maximise profits minus costs over the set of all possible $a_i$s: $$(1) \max_{a_1,...,a_n} \left\{\sum_j^m p_j f_j - \sum_i^n c_i a_i \right\}$$

Another related problem is to maximise the profit with constrained costs for some constant $C$: $$(2) \max_{\sum_i c_i a_i \le C} \left\{\sum_j^n p_j f_j \right\}$$.

Now here here the questions I have:

  1. Can $(1)$ be solved in a strictly polynomial, or pseudo-polynomial way?
  2. Can $(2)$ be solved in pseudo-polynomial time?

By pseudo-polynomial we mean assuming bounds on $|c_i|$ and $|p_j|$, can a polynomial time algorithm be achieved?

It's clear that if $(2)$ pseudo-polynomial solution $(1)$ will also have a pseudo-polynomial solution, by iterating over various values of $C$. Therefore in some sense $(2)$ is a more difficult problem. Moreover, knapsack can be seen as a special case of $(2)$ if we set $f_j=a_j$. Therefore it can't be strictly polynomial. But I can't tell much more about the complexity of these two problems.

$\endgroup$
  • 1
    $\begingroup$ The version of the knapsack problem you described (with $f_j = a_j$) can be easily solved, you simply set $a_i = 1$ if $c_i \ge p_i$ and set $a_i = 0$ otherwise. $\endgroup$ – Artur Riazanov Jan 7 '18 at 12:34
  • $\begingroup$ @ArturRyazanov you are right, so maximising the difference is an easier problem than the original knapsack, which is only pseudo polynomial. $\endgroup$ – AmeerJ Jan 7 '18 at 15:13
  • 1
    $\begingroup$ $k-\mathrm{CLIQUE}$ can be reduced to (2). Create a variable for each vertex, set all $c_i = 1$, $C=k$ and for each edge $(u,v)$ add the function $u \land v$ with $p=1$. The answer for this instance of (2) equals $\binom{k}{2}$ iff the given graph has $k$-CLIQUE. Thus (2) has no pseudo-polynomial algorithm. $\endgroup$ – Artur Riazanov Jan 7 '18 at 18:04
  • 1
    $\begingroup$ One could do the same for (1): for a case that $f_j$s have only two operands construct a similar graph, $c_i$ cost for vertex $i$ and $p_{ij}$ profit for edge $e(i,j)$ if it exists. Then the problem becomes: choose a subset of vertices with the biggest profit-cost margin. Is this a studied problem, or related to a studied problem? $\endgroup$ – AmeerJ Jan 7 '18 at 18:45
  • $\begingroup$ I think (1) is, in fact, polynomially-solvable (not completely sure though), I've updated my answer. $\endgroup$ – Artur Riazanov Jan 7 '18 at 18:48
2
$\begingroup$

(1) has a polynomial solution. Consider a graph with source $s$, sink $t$, vertices $U$ corresponding to the variables and vertices $V$ corresponding to the functions. If $f_j = x_1 \land \ldots \land x_k$ then add edges $f_j \to x_i$ for each $i \in \{1,\ldots,k\}$ with capacities equal to $C$ for $C > \sum p_j$. Add edges $x_i \to t$ with capacities $c_i$ and edges $s \to f_j$ with capacities $p_j$. Consider minimum cut between $s$ and $t$ in this graph (it could be easily found with almost any maximal-flow algrorithm). Let $U_s \subseteq U$ and $V_s \subseteq V$ be the sets of vertices in the component of $s$. Then the value of the minimum cut is $$\sum\limits_{i \in U_s} c_i + \sum\limits_{j \not\in V_s} f_j = \underbrace{\sum\limits_{j\in V} f_j}_{\text{constant}} - \underbrace{\left(-\sum\limits_{i \in U_s} c_i + \sum\limits_{j \in V_s} f_j\right)}_{\text{objective function}}$$ Thus if this value is minimised, the objective function is maximised. On the other hand $U_s$ and $V_s$ for minimum cut have the property that if $x_1 \land \ldots \land x_k = f_j \in V_s$ then $x_1, \ldots, x_k \in U_s$ since otherwise the value of the cut is $\ge C$ which is not optimal. Thus setting $x=1$ for $x \in U_s$ and $x=0$ for $x \not\in U_s$ gives an optimal solution for (1).

The case with arbitrary $p_j$ is $\mathbf{NP}\text{-}\mathrm{complete}$ even with polynomially-bounded $|p_j|$.

If you allow $p_j$ to be negative, you can reduce $\mathrm{max}\text{-}\mathrm{SAT}$ to this problem. For each variable $x_i$ of $\mathrm{max}\text{-}\mathrm{SAT}$ add two variables $x_i$ and $\lnot x_i$ to your input. For each of these pair add the condition $x_i \land \lnot x_i$ with the cost $-C$ for a large enough constant $C$. For all clauses of $\mathrm{max}\text{-}\mathrm{SAT}$ input add the corresponding conjunction with all literals reversed: $x \lor \lnot y \lor z$ becomes $\lnot x \land y \land \lnot z$ (here $\lnot x$ and $\lnot z$ are variables in the new problem). $\lnot x \land y \land \lnot z \iff \lnot (x \lor \lnot y \lor z)$ therefore each unsatisfied conjunctions correspond to satisfied clauses. Thus you can set the cost $p$ for each conjunction as $-1$. For $c_i = 0$ for all $i \in \{1,\ldots, n\}$, $m -\max \left\{\sum\limits_j f_j p_j - \sum\limits_i a_i c_i\right\}$ (where $m$ is the number of clauses in the $\mathrm{max}\text{-}\mathrm{SAT}$ instance) is the maximum number of clauses that could be satisfied in the instance of $\mathrm{max}\text{-}\mathrm{SAT}$ or a value greater than or equal to $C - n$ if the instance is unsatisfiable. Thus $C = 3n$ is "big enough". I.e. for negative $p_j$ there is no polynomial solution even with bounded $|p_j|$ and $|c_j|$ unless $\mathbf{P} = \mathbf{NP}$.

$\endgroup$
  • 1
    $\begingroup$ thanks! it's really interesting how a (seemingly) small change leads to such a drastic difference in complexity. $\endgroup$ – AmeerJ Jan 7 '18 at 19:41

Your Answer

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

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