2
$\begingroup$

Is the following problem NP Complete?

We have $n$ variables $x_1$,$x_2$,....,$x_n$ and a set of constraints:

$\sum_{i=a_1}^{b_1}x_i = h_1$

$\sum_{i=a_2}^{b_2}x_i = h_2$

$\sum_{i=a_3}^{b_3}x_i = h_3$

......

where $h_1$,$h_2$,...,$h_n$ are integers. We ask for an integer assignment of $x_1$,$x_2$,...,$x_n$.

The constraint matrix does not seem to be totally unimodular. Is the problem NP Complete?

$\endgroup$
5
  • 2
    $\begingroup$ I took the liberty of reformatting your question. It is a good idea to write your question with care if you want useful answers. Does NPC stand for NP Complete? $\endgroup$ May 26, 2010 at 0:52
  • $\begingroup$ Thanks Francois. Yes, NPC stands for NP Complete. -Jian. $\endgroup$
    – Jian
    May 26, 2010 at 15:39
  • $\begingroup$ I think I got a proof that the constraint matrix is totally unimodular. but still be great if any one can provide a ref. $\endgroup$
    – Jian
    May 26, 2010 at 16:19
  • $\begingroup$ Could you clarify whether the number of constraints is fixed at three, or are we considering the general problem with an arbitrary number of constraints? And it is truly important for you that the constraints range over an interval of the indices? For example, if we are allowed to form constrainsts from any subset of the indices, then it would seem easier to prove NP Completeness. Finally, could you edit the question and title to expand the abbreviation NPC? Click on 'edit'. $\endgroup$ May 28, 2010 at 13:02
  • $\begingroup$ THere could be arbitrary number of constraints. Each one is a range sum constraint. The constraint matrix is totally unimodular, thus the problem is in P. Thanks anyway. $\endgroup$
    – Jian
    Jun 4, 2010 at 21:51

2 Answers 2

2
$\begingroup$

The problem is equivalent to checking whether the vector $(h_1,\dots,h_m)$ belong to the integer lattice $$\{ Ax \mid x\in \mathbb{Z}^n \}$$ where $A$ is a given $m\times n$ integer matrix. This problem is known to belong to $P$.

However, there exists a similar problem that is indeed $NP$-complete - namely, checking whether a given vector belongs to the integer cone $$\{ Ax \mid x\in \mathbb{Z}_+^n \}.$$

The crucial difference is that in the first problem variables $x_1,\dots,x_n$ can be arbitrary integers, while in the second problem they have to be nonnegative integers. And this nonnegativity requirement turns a polynomial-time problem into an $NP$-complete one.

$\endgroup$
0
$\begingroup$

I'm neither an expert nor too sure, but couldn't this be transformed to a boolean satisfiability problem ? If so, it would be NP-complete.

$\endgroup$
1
  • $\begingroup$ You've got to reduce in the other direction to make this conclusion. That is, you would want instead to reduce the satisfiabiliy problem to this one. $\endgroup$ May 28, 2010 at 12:17

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.