Алгоритм полиномиального времени

Question

что может быть алгоритмом полиномиального времени, который находит вершины [V / 2], которые вместе составляют не менее трех четвертей (3/4) ребер в произвольном неориентированном графе ??

любезнопомощь

Answer 1

Если подумать, это не имеет смысла. Я все еще думаю, что жадное решение будет работать, хотя; если вы продолжаете выбирать вершины, по крайней мере, со средней степенью, мне кажется, что вы получите большую часть всех ребер к концу. Но я не уверен насчет доказательства.

Answer 2

Вот доказательство того, что оно существует:

Рассмотрим алгоритм, который выбирает половину вершин случайным образом. Для любого заданного ребра вероятность того, что была выбрана хотя бы одна из двух его конечных точек, равна 3/4, поэтому ожидаемое число покрытых ребер равно 3 | E | / 4. Таким образом, согласно вероятностному методу , должно существовать хотя бы одно покрытие из> = 3 | E | / 4 ребер, использующее всего 1/2 вершины. Недетерминированный алгоритм следует немедленно.

Использование детерминистического алгоритма *1008*, основанного на этом, является упражнением в дерандомизации (попробуйте использовать метод условных ожиданий ).

Answer 3

Есть один?Я подозреваю, что нет, но я честно не знаю;покрытие вершин является NP-полным, и это близко (мы спрашиваем, если G имеет покрытие вершин размером не более |V| / 2, охватывающее три четверти ребер.

Очевидно, попробуйте жадный алгоритмсначала выбираются вершины с наивысшей степенью.