Минимальное хордовое завершение нечетного графа: сложно ли NP?

Следующая интересная проблема возникла в моем исследовании недавно:

МИГ: График .$G(V, E)$

РЕШЕНИЕ: завершение неординарного нечетного цикла, определяемое как надмножество множества ребер, так что завершенный граф обладает свойством того, что каждое ребро в содержится в нечетком нечетном цикле. E G ′ ( V , E ′ ) G $E'$$E$$G'(V, E')$$G'$

ИЗМЕРЕНИЕ: Размер завершения, т.,$|E' - E|$

До сих пор нам удавалось доказать, что модифицированная версия этой задачи является NP-полной, где вместо того, чтобы требовать, чтобы «каждое ребро в содержалось в нечетном нечетном цикле », нам требуется более сильное свойство, что« каждое ребро содержится в в треугольнике (цикл длины 3) ". (Обратите внимание, что это не эквивалентно проблеме МИНИМАЛЬНОГО ХОРДАЛЬНОГО ГРАФА .)$G'$

Первое, как легко увидеть, является обобщением второго, но до сих пор все мои попытки доказать это потерпели неудачу. Может ли кто-нибудь придумать указатель / ссылку / и т.д.?

Мы доказываем, что задача NP-трудна даже в форме решения, т. Е. «Является ли входной граф уже безордовым завершением нечетного цикла?», Путем сокращения из следующей задачи:$G$

Задача P : Для графа и ребра существует ли неаккордовый нечетный цикл длины больше 3, проходящий через ?e ∈ E ( G ) $G$$e\in E(G)$$e$

Эта проблема, как известно, является NP-трудной благодаря сокращению от «обнаружения аккордовых четных циклов, проходящих через заданный узел» в ссылке, приведенной в одном из ваших комментариев, который указан в параграфе перед разделом 3, позволяя и :q = $p=0$$q=2$

Кроме того, пусть и - произвольные фиксированные целые числа. Следующие задачи являются NP-полными: содержит ли граф индуцированный цикл через заданную вершину длины (mod )? ...p ≥ 0 G u p $q>1$$p\ge 0$$G$$u$$p$$q$

(Может быть сокращение Карпа, но если мы разрешим использование Кука, рассмотрим следующее сокращение: замена данного узла степени d на полный подграф размера d с соответствующими исходящими ребрами. Затем для каждого ребра в полном графе мы можем запросить оракул, решающий проблему P. Обратите внимание, что четный цикл без аккордов, проходящий через данный узел, соответствует нечеткому нечеткому циклу длиной более 3, проходящему через одно из ребер в полном графе.)

Теперь о главном сокращении. Учитывая случай Задачи P, сначала мы обнаруживаем, есть ли треугольники, проходящие через ; если так, удалите каждый узел, который формирует треугольник с . Обратите внимание, что удаление узлов, которые образуют треугольник с , не удалит любые аккордовые нечетные циклы, проходящие через (с помощью свойства chordless).е э $e$$e$$e$$e$

Затем для каждого ребра отличного от мы добавляем вспомогательный узел и два ребра и . Заметьте, что новый граф имеет следующее свойство:e = ( u , v ) v f ( v f , u ) ( v f , v ) G $f$$e=(u,v)$$v_f$$(v_f,u)$$(v_f,v)$$G'$

e G $G$ имеет неаккордовый нечетный цикл длиной более 3, проходящий через тогда и только тогда, когда является аккордовым нечетным завершением цикла.$e$$G'$

Для единственного направления if это можно доказать, рассматривая различные типы ребер в . Каждое ребро, отличное от (включая эти вновь добавленные ребра), будет находиться как минимум в одном треугольнике (тот, который содержит вспомогательный узел); и будет в нечетном нечетном цикле в так как есть нечеткий нечетный цикл, проходящий через в , и этот цикл не удаляется во время процесса удаления узла. e e G ' e $G'$$e$$e$$G′$$e$$G$

Для направления if, поскольку все ребра, кроме должны быть хотя бы в одном треугольнике, нам нужно беспокоиться только о ребре . Там есть chordless нечетного цикл , проходящее через в ( является chordless нечетного завершения цикла). Цикл не может иметь длину 3 по построению , и так как цикл не может содержать любые вспомогательные узлы (от chordless собственности), он будет в графе , а также. Поэтому доказательство завершено.e e G ′ G ′ G ′$e$$e$$e$$G'$$G'$$G'$$G$