O Logical Min-Cut NP-Complete é?

Definição do problema LMC (Log Min Min Cut)

Suponha-se que é um digrama não ponderada, s e t são dois vértices de V , e t é acessível a partir de s . Os estudos LMC problema como podemos fazer t inacessível a partir de s pela remoção de algumas arestas de G seguintes as seguintes restrições:$G = (V, E)$$s$$t$$V$$t$$s$$t$$s$$G$

1. O número de arestas removidas deve ser mínimo.
2. Não podemos remover todas as arestas de saída de nenhum vértice de (ou seja, nenhum vértice com arestas de saída pode ter todas as suas arestas de saída removidas).$G$

Essa segunda restrição é chamada remoção lógica. Então, procuramos uma remoção lógica e mínima de algumas arestas de modo que t seja inacessível a partir de s .$G$$t$$s$

Tentativas de solução

Se ignorarmos a restrição de remoção lógica do problema do LMC, será o problema do min-cut no dígrafo não ponderado , portanto será polinomialmente solucionável (teorema do min-cut de fluxo máximo).$G$

Se ignorarmos a restrição mínima de remoção do problema do LMC, ele será novamente solucionável polinomialmente em um DAG: encontre um vértice tal que k seja alcançável de s e t não seja alcançável de k . Em seguida, considere um caminho p que é um caminho arbitrário de s para k . Agora considere o caminho p como um subgrafo de G : a resposta será cada extremidade de saída do subgrafo p . É óbvio que o vértice k pode ser encontrado pelo DFS em G no tempo polinomial. Infelizmente esse algoritmo não funciona em geral$k$$k$$s$$t$$k$$p$$s$$k$$p$$G$$p$$k$$G$ para um gráfico direcionado arbitrário.

Tentei resolver o problema do LMC por uma técnica de programação dinâmica, mas o número de estados necessários para resolver o problema tornou-se exponencial. Além disso, tentei reduzir alguns problemas do NP-Complete, como 3-SAT, max2Sat, max-cut e clique para o problema do LMC, que não consegui encontrar uma redução.

Pessoalmente, acho que o problema do LMC é o NP-Complete, mesmo que seja um DAG binário (ou seja, um DAG em que nenhum nó tem um grau superior a 2).$G$

Questões

1. O problema do LMC é NP-Complete em um dígrafo arbitrário ? (questão principal)$G$
2. O problema do LMC é NP-Complete em um DAG arbitrário ?$G$
3. O problema do LMC é NP-Complete em um DAG binário arbitrário ?$G$

Seja G = (V, E) um DAG ponderado, se t sejam dois vértices de G, e LSTMC = (G, s, t) seja uma instância do problema lógico de corte mínimo. É óbvio que o problema LSTMC é NP. Agora, devemos mostrar que o LSTMC é NP-rígido. Reduzimos o problema do conjunto de batidas para o problema LSTMC. Seja S = {s1, s2, ..., sn} os conjuntos dados e {a1, a2, ..., am} seja a união de todos os conjuntos. Dado o número k1, o problema de decisão do problema do conjunto de ocorrências indica se existe um conjunto A com elementos k1, de modo que todo elemento de S (todo conjunto se st i = 1..n) contenha pelo menos um elemento de A. denotar o problema do conjunto de batidas como HS (S). Construímos o DAG G ′ ponderado do conjunto S pelo algoritmo HS2LSTMC. Este algoritmo considera s como o vértice de origem do DAG G '. Para cada conjunto si de HS st i = 1..n, o algoritmo considera o vértice correspondente, si e adiciona uma aresta com peso infinito de s a cada si. Então, para cada elemento aj da união dos conjuntos de entradas st j = 1..m, o algoritmo considera o vértice correspondente, aj, e adiciona uma aresta com peso zero de cada si a qualquer aj st aj ∈si no HS. Finalmente, o algoritmo considera dois vértices finais chamados tek e adiciona duas arestas de cada aj st j = 1..m aos dois vértices finais. É claro que G 'pode ser feito em tempo polinomial.

Agora, devemos demonstrar que HS (S) tem uma resposta com elementos k1 se e somente se LSTMC = (G ′, s, t) tiver uma resposta com algumas arestas removidas logicamente, de modo que a soma dos pesos das arestas removidas seja k1.

Para simplificar, realizamos esta parte da prova, fornecendo um exemplo:

Na figura a seguir, suponha que S = {s1, s2, s3} seja tal que s1 = {1, 2, 3}, s2 = {1, 4} e s3 = {2, 5}. A Fig. 2 mostra o DAG G ′ ponderado do problema LSTMC correspondente ao problema do conjunto de batidas HS (S). Neste exemplo, o conjunto A, ou seja, a união de todos os elementos de S, é A = {1, 2, 3, 4, 5}. Nós temos | S | = 3 e | A | = 5. Este exemplo mostra como uma instância arbitrária do problema do conjunto de ocorrências pode ser resolvida com a ajuda de uma instância específica do problema lógico de corte mínimo em um DAG ponderado. Se calcularmos uma resposta para LSTMC = (G ′, s, t) e considerarmos as arestas removidas da resposta que estão na forma de (aj, t) chamadas E1 (1 ≤ j ≤ m), então o conjunto final de E1 é uma resposta para HS (S). Uma resposta para o problema LSTMC é o conjunto de bordas E1 = {(s1, 2), (s1, 3), (s2, 4), (s3, 5), (1, t), (2, t)}. Portanto, o conjunto final do subconjunto E2 = {(1, t), (2,

$G$

Isso responde à pergunta nº 3. (Desculpe pela redação bagunçada antes do tempo. :))

$s$$s$$t$

$A$$B$$v \in G-\{s, t\}$

$v$$t$$v$$A$$v$$B$

$A$$B$$s$$A$$A$$t$$A$$B$$B$$t$

$A$$\{a^*\}$$A$

$a^*$$a^*$$t$$s$$t$$a^*$$a^*$$B$$A$$a^*$$A$$a^*$$A$$t$

$\{a^*\}$$B$$\{a^*\}$$t$$a^*\rightarrow t$

$|\{a^*\}|$$a^*\rightarrow t$$s$$t$$a^*$$t$$a^*$$a^*\rightarrow t$

$|\{a^*\}|$$\{a^*\}\rightarrow t$$k < |\{a^*\}|$$A$$s$$\{a^*\}$$t$

$G$

$\{a^*\}$

$\{a^*\}$$B$

$\{a^*\}$$\{a^*\}$$t$$\{a^*\}$

$\{a^*\}$$\{a^*\}$

$\{a^*\}$$t$$s$

$\{a^*\}$

$\{a^*\}$$t$$\{a^*\}$$t$$s$$t$$s$

$A$

$O(|E|)$$O(|E|^2)$$O(|E|)$.

$O(|V|\cdot(|V|+|E|))$$O(|V|^3)$$O(|E|^2)$$O(|V|^2+|E||V|+|V|^3+|E|^2) = {\bf O(|V|^3+|E|^2)}$

$s$$t$