Re: Graph problem, is it NP-Complete?

In <1193407493.598304.95330@xxxxxxxxxxxxxxxxxxxxxxxxxxx> arcadiorubiogarcia@xxxxxxxxx writes:

Hi,

I'm trying to solve the following problem, which I suspect is NP-
Complete. I would appreciate any suggestions on how to prove its NP-
Completeness, and a possible algorithm for finding suboptimal
solutions. Thanks in advance.

- The input to the problem is:

1. An undirected weighted graph, whose weights are non-zero natural
numbers. The graph has always a "line-like" structure, i.e. it is
acyclic and all its vertices have 2 neighbours, except 2 that have 1
neighbour. Example:

(1)--2--(2)--5--(3)--3--(4)--3--(5)--1--(6)

Note: (1) is a vertex, --2-- is an edge of weight 2.

2. A non-zero natural number K.

- The output of the decision version of the problem should be:

YES if there exists a set of size <= K of connected subgraphs of the
input graph, that satisfy the following property:

The sum of all the weights of each edge of each subgraph that "map" to
each edge of the graph should be the same. Additionally, all the edges
of each subgraph must have the same weights.

Unless I'm missing something, the problem statement seems unnecessarily
complex. Rather than a graph there is a sequence of n positive integers,
and a solution is a set of subsequences whose "sum" is the sequence,
where each subsequence can only contain a particular unique value.

It's better to see an
example:

Problem:

(1)--2--(2)--5--(3)--3--(4)--3--(5)--1--(6)

Possible solution:

(1)--2--(2)--2--(3)

(2)--3--(3)--3--(4)--3--(5)

(5)--1--(6)

- Output of the optimization version: A set of minimal size of such
subgraphs

It may help to think of the sequence as a histogram. The problem
then becomes to find a minimal set of rectangles that cover the
histogram, where you're allowed to slide the columns up and down
relative to each other.

Even though it's thus a packing problem, I suspect it's in P.

Some obvious observations:

You can discard an adjacent repeated value without affecting k,
e.g. 2,5,3,3,1 and 2,5,3,1 have the same k.

If the value at either end is greater than it's neghbour, it's going
to cost you one subsequence, so discard it and solve the subproblem
then add 1 to the k value obtained.

If an interior value is greater than the sum of its neighbours, it
too must cost you one subsequence, so discard it and solve as above.

If an interior value is equal to the sum of its neighbours, then k
is the minimum of the sum of solving the left and right subproblems
separately, and 1 + k of solving the subproblem when it's removed.

I haven't thought through the other cases yet, so no algorithm, sorry.

HTH,
David
.

Relevant Pages