Маркировка графа, в которой два цикла делят не более одной вершины

Question

Доброе утро. Мой друг дал мне интересную проблему с графиком, которая описана ниже.

Для простого графа, в котором два цикла делят не более одной вершины, как пометить ребра неотрицательным вещественным числом так, чтобы для каждой вершины сумма меток ребер, попадающих на нее, не превышала данную константу (скажем, K) и сумма меток на всех ребрах графа максимальна. Заранее благодарны за Вашу помощь.

Answer 1

Тьфу, это использует кувалду, чтобы убить муху, но здесь идет.

Класс входных графов - это класс графов, которые запрещают этот минор:

  *
 /|\
* | *
 \|/
  *

Поскольку запрещенный минор плоский, класс имеет ограниченную ширину дерева, и мы можем извлечь подходящее разложение дерева за линейное время. Общий многогранник с дробным соответствием является полуцелым, поэтому существует оптимальное решение с метками ребер в {0, 1/2, 1}. Мы можем использовать динамическое программирование по разложению дерева, чтобы найти оптимальное решение за линейное время.