Connect nodes in the tree

Hypothetical question. Say I was given a tree T and a list of pairs of nodes (x, y) in T. They ask me how many of the two pairs I can connect at the same time (connect x with y), using each edge in T no more than once,

How to do it?

+4
source share
1 answer

It is not NP-hard for trees. For example, you can do the following.

  • The roots of the tree are arbitrary.

  • For each vertex v, calculate the optimal solution bounded by the v subtree.

  • In addition, for each v for each path p that includes the v parent edge, it computes the optimal solution bounded by the v subtree, except for the path p.

(2) and (3) can be calculated using solutions of smaller problems inside the v subtree.

It is probably easier to look at steps 1, 2 and 3 and find out what the repetition is, but just to give you an idea, (2) can be calculated by taking a maximum of several solutions: one that summarizes the solutions for children v (t ie the sum of the decisions created in step 2 for each child), and one for each path, which includes v plus the solutions for step 2 for other children (this will essentially include the sum of one or two decisions obtained in step 3 for v children, plus the sum of the decisions obtained in stage 2 for other children).

+2
source

All Articles