Complejidad de encontrar el número máximo de conjuntos disjuntos por pares

Suponga que tengo conjuntos de con elementos tomados de posibles. Cada conjunto es de tamaño ( ), donde los conjuntos pueden superponerse. Quiero determinar si los siguientes dos problemas son NP completos o no: $P$ $r$ $n$ $n<r$

Problema A. ¿Hay ( ) conjuntos distintos dentro de los conjuntos (es decir, su intersección por pares está vacía)? $M$ $1 \le M \le P$ $P$

Problema B. Ahora se pueden elegir ( ) elementos de cada conjunto. ¿Existen ( ) conjuntos distintos de tamaño cada uno dentro de los conjuntos ? Tenga en cuenta que solo se puede tomar un conjunto de elementos de cada conjunto de elementos. $k$ $k<n$ $L$ $1 \le L \le P$ $k$ $P$ $k$ $n$

Observación : Estoy interesado principalmente en el caso donde son fijos ( ). $k,n$ $n \ge 2, k \ge 2$

Creo que Problema A puede ser pensado como un Uniform problema de la concordancia -partite hiper-gráfico. Es decir, tenemos los elementos de como vértices, y cada hiper-borde contiene un subconjunto de vértices del gráfico. $n$ $r$ $r$ $n$

En el Uniform problema de la concordancia -partite hiper-gráfico NP-completo? $n$ $r$
Creo que el problema B es equivalente a encontrar el número de hiper-bordes distintos de cardinalidad tomados de hiper-bordes de cardinalidad . ¿Es esta versión restringida (en el sentido de que cada conjunto de cardinalidad se toma de un conjunto preseleccionado de elementos en lugar de tomarse arbitrariamente de elementos) del problema A NP-completo? $k$ $n$ $k$ $n$ $r$

Ejemplo ( ): $n=3,r=5, P=3$

, , $A=\{1,2,3\}$ $B=\{2,3,4\}$ $C=\{3,4,5\}$

Si , solo hay un conjunto distinto, que es o o , ya que cada uno de los pares , , tiene intersección vacía $k=n=3$ $M=1$ $A$ $B$ $C$ $(A,B)$ $(A,C)$ $(B,C)$

Si , tenemos conjuntos distintos: una solución es , (subconjuntos de y ). $k=2$ $L=2$ $\{1,2\}$ $\{3,4\}$ $A$ $B$

graph-theory np-hardness MJK
fuente

Este es un caso especial del problema de empaquetado máximo y los problemas A y B son NP-completos . Tenga en cuenta que el problema es simplemente un problema de coincidencia si y también es fácil si . Entonces supondré . $n=2$ $n=1$ $n \ge 3$

En lugar de hacer la pregunta,

¿Hay conjuntos disjuntos entre los conjuntos ? $M$ $P$

Hagamos la siguiente pregunta

¿Cuál es el número máximo de conjuntos disjuntos que podemos obtener de los conjuntos ? $P$

Está claro que si la segunda pregunta es responsable en el tiempo polinómico, entonces también es la primera, ya que todo lo que tenemos que hacer es comparar este valor máximo con y generar SÍ si es menor o igual a este máximo y NO en caso contrario. $M$ $M$

Además, si la primera pregunta es responsable en tiempo polinómico, entonces la segunda también lo es, ya que podemos usar la búsqueda binaria en y obtener la respuesta a la segunda pregunta y solo agregar un factor de $M$ $O(\log{M})$

Entonces podemos concluir que ambas preguntas son equivalentes. es decir, la pregunta 1 se puede resolver en tiempo polilomial si y solo si la pregunta 2 también lo es.

También está claro que los problemas están en NP, ya que podemos verificar fácilmente que los conjuntos de superados son disjuntos. $M$

Entonces, la pregunta ahora es ¿cómo reducimos un problema NP-Hard conocido a esto? Para hacer esto, reducimos del problema de empaquetado máximo establecido . Simplemente me enfocaré en el problema A, ya que el problema B se puede demostrar fácilmente que es difícil estableciendo $k=n-1$

Considere una instancia arbitraria del problema de empaquetamiento máximo conjunto . Tenga en cuenta que la única diferencia entre el problema A y el problema de empaquetado del juego máximo original es que en el problema A, el tamaño de los juegos tiene que ser igual. Vamos ser el máximo cardinalidad entre todos los conjuntos en . Si cada conjunto en tiene la misma cardinalidad, hemos terminado y el problema de la cubierta del conjunto es exactamente el problema A. Ahora suponga que para algún conjunto , tenemos . Simplemente agregamos elementos a $T$ $t$ $T$ $T$ $S_i \in T$ $|S_i| < t$ $(t-|S_i|)$ que no son elementos de cualquier conjunto en . Repetimos este proceso hasta que todos los conjuntos tengan el mismo tamaño. Está claro que agregar nuevos elementos de esta manera no cambia el tamaño del número máximo de conjuntos disjuntos. $S_i$ $T$ $S_i \in T$

Entonces, si podemos resolver el problema en tiempo polinómico, podemos resolver el problema de empaquetado máximo establecido en tiempo polinómico ya que todo lo que tenemos que hacer es eliminar los elementos adicionales que hemos agregado, y hacer esto no cambia el tamaño del número máximo de conjuntos disjuntos en . $A$ $T$

EDITAR - Alguna información adicional sobre el problema B

$T$ $n$ $d$ $T$

$n$

$M$ $T$ $M$ $(M-1)$ $P=NP$

Obinna
fuente

n + 1

$n+1$

n = 3, P = 3

$n=3, P=3$

n - 1 = 2

$n-1=2$

{1, d}, {2, 3}, {4, 5}

$\left\{ {1,d} \right\},\left\{ {2,3} \right\},\left\{ {4,5} \right\}$ . Sin embargo, la solución al problema A es que solo hay un conjunto. En otras palabras, no veo cómo una solución para el problema B da una aproximación constante del factor al problema A.

MJK

A' = {1, 2, 3, d}, B' = {2, 3, 4, d}

$A′= \left\{ {1,2,3,d} \right\}, B′= \left\{ {2,3,4,d} \right\}$

C' = {3, 4, 5, d}

$C′= \left\{ {3,4,5,d} \right\}$

n = 4

$n=4$

n = 4

$n=4$

k = 3

$k=3$

n = 2

$n=2$

k = 2

$k=2$

Complejidad de encontrar el número máximo de conjuntos disjuntos por pares

Respuestas: