Graph problem, is it NP-Complete?

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. 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

.

Relevant Pages

  • Re: Problem on an nxn grid
    ... "See Spot Run" in the vocabulary of Graph Theory. ... Gibbons's "Algorithmic Graph Theory" gives a pseudo-code ... parts of the Edmonds algorithm (such as the Hungarian ... All weights are assumed to be ...
    (sci.math)
  • Re: How to optimize Scheme code
    ... This is my first post on Usenet ever, and it is about my first Scheme ... identify disjoint subgraphs in it. ... The graph is specified as a long ...
    (comp.lang.scheme)
  • Re: Standard graph API?
    ... I would rather have the weights be a separate dict ... >or function or whatever passed to the graph algorithm. ... [snip stuff about using dicts] ... "properties as separate mappings" and the Level 2 Graph API could add ...
    (comp.lang.python)
  • Re: Shortest Path finding with mutating weights
    ... > Dijkstra's algo can be used to find shortest path between 2 nodes in ... > a weighted graph. ... > How to find shortest paths in a graph with mutating weights? ... Connections from one time slice to the another ...
    (comp.theory)
  • Re: Modeling General Graphs in SQL
    ... You don't mention assigning weights to the edges, so can we assume that the ... Therefore a minimal spanning tree of a graph with n ... Or you might need to test if the graph is cyclic or acyclic. ... return the minimum path between two vertices (wow, ...
    (comp.databases)