Как доказать NP-полноту самого длинного пути между двумя вершинами, полагающимися Hamilton NP-трудной проблемой

Question

У меня есть этот вопрос: у меня есть неопрятный график g (v, e) (где v= набор вершин, e= набор краев).Рассмотрим максимальный путь между двумя вершинами S и T:

LPATH = {⟨G,s,t,k⟩|There is in G a simple path as long as at least k from s to t}

.

Простой путь - это путь без какой-либо повторной вершины, то есть каждая вершина может быть посещена только один раз.Длина пути предоставляется из краев, из которых он состоит.

Итак, как я могу показать, что lpath - это проблема с NP-полной, используя проблему на пути Hamilton в качестве проблемной проблемой NP в качестве справки?

Answer 1

Добро пожаловать на сайт! Пусть $ g= (v, e) $ - неопрятный график. Если $ G $ является гамильтонианом, то существует простой цикл $ C $ в $ g $ содержащий каждую вершину, то есть длина $ C $ - $ | V | $ . Обратите внимание, что если вы удалите любой Edge $ VW $ from $ C $ , вы заканчиваете путь Длина $ | V | - 1 $ между $ v $ и $ W $ . И наоборот, если вы найдете простой путь $ p $ длина $ | V | - 1 $ между двумя вершинами $ v, w $ Подключен к краю, вы можете добавить краю $ vw $ на $ p $ для получения гамильтонового цикла (как $ p $ не может содержать $ vw $ Из-за простых путь). Также соблюдайте, что выбор $ v $ и $ W $ производит, пока они связаны край.

Итак, мы можем получить следующее уменьшение: Начиная с некоторых графиков $ g= (v, e) $ , выберите какой-то край $ vw \ in in $ И удалите его, чтобы получить новый график $ g '= (v, e \ setminus \ {vw \}) $ . Используя наблюдения, которые мы сделали, из этого следует, что $ G '$ имеет путь $ p $ между $ v $ и $ W $ длина $ | V | - 1 $ Если и только при добавлении $ vw $ на $ p $ дает гамильтониан Цикл в исходном графике $ g $ . Как $ G '$ можно вычислить из $ g $ в многочленом времени, у нас есть полиномиальное сокращение < Spaness Class= «Математический контейнер»> $ \ mathrm {hamiltonian Cycle} \ leq_ \ mathsf {p} \ mathrm {long path} $ , что показывает, что ваша проблема - $ \ mathsf {np} $ -hard (потому что $ \ mathrm {hamiltonian Цикл} $ - $ \ mathsf {np} $ уже).

Чтобы показать, что $ \ mathrm {длинный путь} $ в $ \ mathsf {np} $ Мы отмечаем, что путь в графе может быть эффективно закодирован как список его краев и проверяет, что строка фактически кодирует путь на графике, а затем подсчитывать количество ребер, чтобы определить, достаточно ли достаточно долго, можно сделать в полиноме время.

Следовательно, мы находим, что $ \ mathrm {длинный путь} $ IS $ \ mathsf {np} $ -Complete.