An interesting graph task

Question

There is a tree with n vertices. We are asked to calculate minimum size of a multiset S such for each edge (u,v) in the tree at least one of the following holds:

• u ∈ S
• v ∈ S
• there are at least two vertices in S, each of which is adjacent to u or v.

Since S is a multiset, a vertex may be in S multiple times.

My hunch is the following. First of all, we take into consideration the following fact: in optimal solution each vertex is in S at most twice. So we can traverse tree in post-order and calculate results for the three cases where a vertex is not in the optimal S, it's in once and it's in twice.

Unfortunately I can't link relations between subproblems and I'm not sure if this idea would be correct.

Hints or references are both welcome. Many thanks.

Answer 1

Represent trees like so (untested Haskell).

> data Tree a = Node a
>             | Cons (Tree a) (Tree a)

The tree

  1
 /|\
2 3 4
  |
  5

is

(Cons (Node 2)
      (Cons (Cons (Node 5) (Node 3))
            (Cons (Node 4) (Node 1)))) :: Tree Int .

Here's a bottom-up verification function.

> type ZeroOneOrTwo = Int
> data Result = Failure
>             | Success { numDist0Provided :: ZeroOneOrTwo
>                       , numDist1Provided :: ZeroOneOrTwo
>                       , numDist1Required :: ZeroOneOrTwo
>                       }
>
> plus, minus :: ZeroOneOrTwo -> ZeroOneOrTwo -> ZeroOneOrTwo
> x `plus` y = min 2 (x + y)
> x `minus` y = max 0 (x - y)
>
> evaluate :: Tree ZeroOneOrTwo -> Bool
> evaluate t = case evaluate' t of
>   Failure -> False
>   s -> 0 == numDist1Required s
>
> evaluate' :: Tree ZeroOneOrTwo -> Result
> evaluate' (Node x) = Success { numDist0Provided = x
>                              , numDist1Provided = 0
>                              , numDist1Required = 0
>                              }
> evaluate' (Cons t1 t2) = case (evaluate' t1, evaluate' t2) of
>   (Failure, _) -> Failure
>   (_, Failure) -> Failure
>   (s1, s2) ->
>     if numDist0Provided s2 < numDist1Required s1 then Failure
>       else Success { numDist0Provided = numDist0Provided s2
>                    , numDist1Provided = numDist1Provided s2 `plus` numDist0Provided s1
>                    , numDist1Required = max (numDist1Required s2 `minus` numDist0Provided s1)
>                                           (if 0 < numDist0Provided s1 || 0 < numDist0Provided s2 then 0
>                                              else 2 `minus` (numDist1Provided s1 `plus` numDist1Provided s2))
>                    }

I'll leave the corresponding linear-time DP as an exercise.