Trayectorias con aristas separadas que evitan algunos subgráficos

Question

Dejemos que $G$ sea un grafo dirigido en $n$ vértices. Sea $H_1$ , ..., $H_k$ sean subgrafos marcados de $G$ . (En concreto, cada $H_i$ consiste en un subconjunto de los vértices de $G$ y un subconjunto de aristas del subgrafo inducido). Estoy interesado en un algoritmo para encontrar el máximo número de caminos disjuntos de aristas de $s \in V$ a $t \in V$ con la restricción de que ninguno de los $H_i$ está totalmente contenida en la unión de los caminos.

Sin la restricción, se trata de un problema estándar de flujo máximo. Con la restricción, se podría modificar el algoritmo de Ford-Fulkerson para que se ajuste a la restricción en todos los pasos y dar una cota inferior, pero no hay razón para esperar que sea ajustada.

Me interesa sobre todo el escenario en el que $|H_i| = O(1)$ y $1 \ll k \ll n$ . Idealmente, por supuesto, me gustaría un algoritmo que sea polinómico en todos los $n$ , $k$ y $\max_i |H_i|$ .

Estoy dispuesto a hacer algunas suposiciones sobre la $H_i$ Una suposición natural es que cada $H_i$ es un conjunto de vértices totalmente desconectado, o el subgrafo inducido completo. También estoy dispuesto a asumir que $G$ es acíclico dirigido. No sé si alguno de esos ayuda.

Answer 1

Esto parece ser un problema NP-completo. Se puede demostrar por reducción de 3-SAT, como sigue.

Para una fórmula 3-SAT dada con $p$ variables y $m$ construye un gráfico formado por $2p$ caminos internamente disjuntos entre vértices $s$ y $t$ cada camino con $m+1$ vértices internos. Para cada variable $x_i$ tenemos dos caminos $P_i, Q_i$ .

Para cada $i=1,2,\dots,p$ definimos $H_i$ como el conjunto de dos vértices de $P_i$ y $Q_i$ junto a $s$ . Este es el gadget variable. Para cada $j=1,2,\dots,m$ el gadget de la cláusula $H_{p+j}$ se compone de tres vértices, seleccionados a partir de las trayectorias correspondientes a los literales del $j$ La cláusula de $C_j$ : si $x_i$ aparece sin negación en $C_j$ seleccionamos un vértice de $P_i$ . Si $x_i$ aparece con la negación en $C_j$ seleccionamos un vértice de $Q_i$ .

Ahora hay $p$ disyuntiva $st$ -con sujeción a las restricciones si y sólo si la fórmula dada es satisfactoria.

De hecho, los caminos $P_i, Q_i$ puede tener una longitud $2$ no importa que algunos de los conjuntos $H_i$ se cruzarán.