Максимум K3 непересекающихся подграфов графа

Question

Я пытаюсь решить следующую проблему: у нас есть некоторый график.Как найти (только число) максимум из K3 полных графов, которые являются подграфами входного графа и не пересекаются друг с другом.

Мне НЕ нужен код, полное решение.Мне нужен совет, с чего начать.Я думал о DFU и некотором обходе, но он не дает решения, по крайней мере, с некоторой хорошей временной сложностью.

Answer 1

Под дизъюнктом я предполагаю, что вы имеете в виду, что любые два треугольника даже не разделяют вершину.

Это будет NP-Hard.

Разделение на треугольники - этоNP-Complete, и может быть сведен к вашей задаче.

Путем построения графика треугольников: каждый треугольник является вершиной, и два треугольника являются смежными, если они совместно используют узел.Вы можете свести ее к самой большой проблеме независимых множеств, которая, вероятно, содержит много литературы по алгоритмам / алгоритмам аппроксимации и т. Д.