Интересные функции на графиках, которые можно эффективно максимизировать.

Скажем, у меня есть взвешенный граф такой, что является весовой функцией - обратите внимание, что допустимы отрицательные веса.w : E → [ - 1 , 1 $G = (V,E,w)$$w:E\rightarrow [-1,1]$

Скажем , что определяет свойство любого подмножества вершин . S ⊂ $f:2^V\rightarrow \mathbb{R}$$S \subset V$

Вопрос: Какие интересные примеры s, для которых задача максимизации: может быть выполнена за полиномиальное время?$f$$\arg\max_{S \subseteq V}f(S)$

Например, функция вырезания графа

Я позволю определению «интересный» быть несколько расплывчатым, но я хочу, чтобы проблема максимизации была нетривиальной. Например, не должно быть, что вы можете определить ответ, не изучая края графика (поэтому постоянные функции и функция мощности не интересны). Также не должно быть случая, чтобы $f$ на самом деле просто кодировал какую-то другую функцию с полиномиальным размером, добавляя ее в область $2^V$ (то есть я не хочу, чтобы был какой-то маленький домен $X$ и некоторая функция $m:2^S\rightarrow X$ известно до того, как смотреть на график, так что интересующая функция действительно $g:X\rightarrow \mathbb{R}$ и $f(S) = g(m(S))$ Если это так, то проблема «максимизации» на самом деле является просто вопросом оценки функции на всех входах.)

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

Всякий раз, когда считает число ребер удовлетворяющих некоторому булеву предикату, определенному в терминах и , то то, что вы написали, является просто булевым 2-CSP. Целевая функция просит максимизировать количество удовлетворенных предложений по всем назначениям переменных. Это, как известно, является NP-твердым, и точный порог твердости также известен, предполагая UGC (см. Raghavendra'08).( u , v ) u ∈ S v ∈ $f(S)$$(u,v)$$u\in S$$v\in S$

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

Доматическая перегородка / слабая 2-раскраска.

(В этом случае если каждое имеет соседа в и наоборот. В противном случае Решение с всегда существует, если есть нет изолированных узлов, и его можно легко найти за полиномиальное время.)$f(S) = 1$$v \in S$$V \setminus S$$f(S) = 0$$f(S) = 1$

Минимальный разрез (в частности, вершинный разрез).

(В этом случае будет выглядеть примерно так: 0, если удаление узлов в множестве не разбивает по крайней мере на два компонента, а противном случае. Тогда максимизация эквивалентна нахождению минимального разреза , что можно сделать за полиномиальное время.)$f$$S$$G$$|V| - |S|$$f$

Вы также можете определить аналогичную функцию, которая соответствует минимальным срезам кромок.

(Например, равно 0, если или ; в противном случае это , где - множество ребер, которые имеют одну конечную точку в и другую конечную точку в )$f(S)$$S = \emptyset$$S = V$$|E| - |X|$$X$$S$$V \setminus S$

Максимальный независимый набор.

$f(S)$$S$$S$$V \setminus S$$S$$S$$f(S) = |V|$