I have a chain graph like in the picture. Each node of the graph has finite possible labels, i.e. states, which define the node's weight(non-negative) as well as the internode weight(also non-negative). Each node is connected to m previous ones. The internode weight is shown as edge and node weight as node itself. Is there an algorithm for finding labels, that result in the largest total sum of weights of the graph?

a chain graph

Here is a more formal description by @j_random_hacker: For each vertex $v$ there is a set of possible states $S_v$ and a function $f_v:S_v \to \mathbb{N}$, and for each pair of vertices $u,v$ that are connected by an edge there is a function $g_{uv}:S_u \times S_v \to \mathbb{N}$, and we want to choose a state from $S_v$ for each vertex $v$ such that the sum of all these functions is maximised. In other words, we want to choose a function $h:V \to V$ such that $h(v) \in S_v$ for each $v$, and that maximizes $\sum_v f_v(h(v)) + \sum_{u,v} g_{uv}(h(u), h(v))$, where the latter sum is over all edges $(u,v)$ in the graph.

  • $\begingroup$ OK, then for a general graph this would be NP-hard (there's a reduction from Vertex Cover: give every vertex two states, IN and OUT, with IN having weight 1 and OUT having weight 2; give every edge a large weight if at least one of its endpoints is IN, and a weight of 0 otherwise; every optimal solution will make as few vertices IN as possible in order to cover all the edges). So the chain structure will have to be exploited somehow to get a polynomial-time algorithm. $\endgroup$ – j_random_hacker Feb 7 '19 at 20:28
  • 1
    $\begingroup$ Please credit the original source of the problem. If the problem came from yourself, please claim so. $\endgroup$ – John L. Feb 8 '19 at 7:48
  • $\begingroup$ Please characterize your "chain graph" in as much detail as possible. It might make the difference between an easy problem and a NP-hard problem, as noted by @j_random_hacker. $\endgroup$ – John L. Feb 8 '19 at 7:51

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.