Funções interessantes em gráficos que podem ser eficientemente maximizados.

Digamos que eu tenha um gráfico ponderado $G = (V,E,w)$ tal que seja a função de ponderação - observe que pesos negativos são permitidos.$w:E\rightarrow [-1,1]$

Digamos que define uma propriedade de qualquer subconjunto dos vértices . S ⊂ $f:2^V\rightarrow \mathbb{R}$$S \subset V$

Pergunta: Quais são alguns exemplos interessantes de s para os quais o problema de maximização: pode ser executado em tempo polinomial?$f$$\arg\max_{S \subseteq V}f(S)$

Por exemplo, a função de corte do gráfico

Vou deixar a definição de "interessante" um tanto vaga, mas quero que o problema de maximização não seja trivial. Por exemplo, não é possível determinar a resposta sem examinar as bordas do gráfico (portanto, funções constantes e a função de cardinalidade não são interessantes). Também não deve ser o caso de $f$ estar apenas codificando alguma outra função com um domínio de tamanho polinomial, preenchendo-o no domínio $2^V$ (ou seja, eu não quero que exista um pequeno domínio $X$ e alguma função $m:2^S\rightarrow X$ conhecido antes de olhar para o gráfico de tal modo que a função de interesse é realmente $g:X\rightarrow \mathbb{R}$ , e $f(S) = g(m(S))$ Se for esse o caso, o problema da "maximização" é realmente apenas uma questão de avaliar a função em todas as entradas.)

Edit: É verdade que, às vezes, os problemas de minimização são fáceis se você ignorar os pesos das bordas (embora não minimize a função de corte, pois eu permito pesos negativos nas bordas). Mas estou explicitamente interessado em problemas de maximização. Porém, isso não se torna um problema de problemas naturais ponderados.

Sempre que conta o número de arestas satisfazem algum predicado booleano definido em termos de e , o que você escreveu é apenas um 2-CSP booleano. A função objetivo pede para maximizar o número de cláusulas satisfeitas em todas as atribuições para as variáveis. Sabe-se que é NP-hard e o limite exato de dureza também é conhecido assumindo UGC (consulte Raghavendra'08).( u , v ) u ∈ S v ∈ $f(S)$$(u,v)$$u\in S$$v\in S$

Existem muitos exemplos positivos naturais quando você deseja maximizar subconjuntos de arestas, por exemplo, a correspondência máxima é um exemplo de um problema de tempo polinomial nesse caso.

Divisória temática / 2 cores fracas.

(Neste caso, se cada v ∈ S tiver um vizinho em V ∖ S e vice-versa. Caso contrário, f ( S ) = 0. Uma solução com f ( S ) = 1 sempre existe se não houver isolado. nós e pode ser encontrado facilmente em tempo polinomial.)$f(S) = 1$$v \in S$$V \setminus S$$f(S) = 0$$f(S) = 1$

Corte mínimo (especificamente, corte de vértice).

(Nesse caso, seria algo como isto: 0 se a remoção dos nós no conjunto S não particionar G em pelo menos dois componentes e | V | - | S | caso contrário. Maximizar f é equivalente a encontrar um corte mínimo , o que pode ser feito em tempo polinomial.)$f$$S$$G$$|V| - |S|$$f$

Você também pode definir uma função semelhante que corresponda a cortes mínimos nas bordas.

(Por exemplo, é 0 se S = ∅ ou S = V ; caso contrário, é | E | - | X | , onde X é o conjunto de arestas que possuem um ponto final em S e o outro ponto final em V ∖ S. )$f(S)$$S = \emptyset$$S = V$$|E| - |X|$$X$$S$$V \setminus S$

Conjunto independente máximo.

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