Elegir una cubierta mínima evitando subconjuntos "malo".

Question

$\newcommand{set}[1]{\left\{#1\right\}}$ Deje $S$ a un y $\mathcal B\subseteq \mathcal P(S)$ una colección de subconjuntos; llamaremos a $B\in \mathcal B$ un mal subconjunto de $S$. Asumimos, además, que todos los malos subconjuntos $B$ ha $|B|>1$.

Supongamos $\mathcal C\subseteq \mathcal P(S)$ es una cubierta de $S$; es decir, $S= \bigcup_{C\in\mathcal C} C$. We say a subset $T\subconjunto S$ is good if $B\no\subconjunto T$ for any $B\in \mathcal B$; that $\mathcal C$ is good if any $C\in \mathcal C$ is good; and that $\mathcal C$ is minimal good if $|\mathcal C|$ is minimal among all good coverings of $S$.

Por ejemplo, si $S=\{a,b,c\}$ e $\mathcal B=\{\{a,b\},\{b,c\}\}$, el singleton conjunto $\{\{a\},\{b\},\{c\}\}$ es una buena cobertura, y $\{\{a,c\},\{b\}\}$ es el único con un mínimo de buena cobertura. Sin embargo, si $S=\{a,b,c,d\}$ e $\mathcal B=\{\{a,b\},\{c,d\}\}$, $\{\{a,c\},\{b,d\}\}$ e $\{\{a,d\},\{b,c\}\}$ son mínimos buenas coberturas.

Pregunta: Dado $S$, $\mathcal B$, hay una forma sencilla de generar un mínimo de buena cobertura, ya sea directamente o con un algoritmo eficiente?

(O dicho de otra manera: ¿cómo podemos generar una mínima colección de conjuntos que dominan todos los subconjuntos (en la inclusión de orden parcial) a excepción de aquellos que son superseries de una colección particular de conjuntos.)

Ingenuamente, esto requiere de la búsqueda de $\mathcal P(S)$, por lo que es exponencial en $|S|$. Algunas observaciones:

1. Si hay un subconjunto $X\subset S$ ejemplo de que cualquiera de las $X\subseteq B$ o $X\cap B=\emptyset$ para todos los $B\in \mathcal B$, entonces podemos cociente por $X$ (es decir, de identificar aquellos elementos) y resolver el problema de $S'$, donde $|S'|=|S|-|X|+1$.

2. Si podemos encontrar una máxima buen conjunto; es decir, un buen conjunto $T\subset S$ tal que $|T|$ es maximal con esta propiedad; entonces si $\mathcal C'$ es un mínimo de buena cobertura de $S-T$, $\mathcal C'\cup \{T\}$ es un buen recubrimiento de $S$. Sin embargo, puede no ser mínimo: por ejemplo, si $S=\set{a,b,c,d,e}$, e $B=\set{B\subset S\mid |B|\geq 4}\cup\set{\set{a,b}}$, a continuación, $T=\set{c,d,e}$ es máxima bueno, y $\mathcal C'=\set{\set{a},\set{b}}$. Sin embargo, es fácil ver que $\set{\set{a,d,e},\set{b,c}}$ es un mínimo de buena cobertura.

Edit (para la posteridad): Este problema es equivalente a encontrar un mínimo hypergraph para colorear, el cual, como en la respuesta se señala, incluye gráfico para colorear como un subcase.

Answer 1

Edit: Después de un vergonzoso defectuoso respuesta, me produce una respuesta (abajo) que es correcta, pero manifiestamente demasiado difícil. En realidad, la reducción es casi trivial.

El problema es NP-completo, porque gráfico para colorear es un caso especial de la misma. Tenga en cuenta que para una buena cobertura, no podemos, sin pérdida de generalidad tomar todos sus elementos a ser distinto, porque podemos tomar los elementos de distancia de conjuntos si ya están en otros conjuntos.

Ahora vamos a $G = (S, B)$ un gráfico. Entonces el problema es exactamente el problema de la determinación de la cromática número de un gráfico.

---

Lamentablemente (?), el problema es NP-completo.

Que está en NP es claro, así que vamos a mostrar es NP-duro. Supongamos que podemos resolver su problema de manera eficiente, y vamos a demostrar que también podemos resolver el 3 dimensiones coincidentes problema de manera eficiente. En concreto, vamos a demostrar que podemos decidir si existe un perfecto 3D coincidencia si podemos resolver su problema de manera eficiente. Incluso este problema es NP-completo, como se indica en la "Decisión de Problema" parte de la página de la Wikipedia.

Deje $X, Y, Z$ se establece de igual cardinalidad $k$, y deje $T \subseteq X \times Y \times Z$. (Vamos a pasar por alto la distinción entre una tupla $(x, y, z)$ y el conjunto de $\{x, y, z\}$.) Queremos decidir si podemos tomar $k$ elementos de $T$, de modo que cada elemento de a$X, Y, Z$ aparece en una de las $k$ elementos. Ahora vamos a $S = X \sqcup Y \sqcup Z$, y deje $B$ se componen de dos elementos, subconjuntos de a$X$, todos por dos elementos, subconjuntos de a$Y$, todos por dos elementos, subconjuntos de a$Z$, y todos los elementos de a$X \times Y \times Z \setminus T$. Tenga en cuenta que la cardinalidad de a$B$ es el polinomio en $k$.

Con esto $B$, una buena cobertura para la $S$ sólo contiene subconjuntos de más de 3 elementos, y cualquiera de los 3 elementos del subconjunto que contiene debe ser un elemento de $T$, ya que todos los otros 3 elementos de los subconjuntos en $B$. Por lo tanto, si una buena cobertura ha $k$ elementos, que es mínimo, debe consistir de sólo 3 elementos de los subconjuntos, y por lo tanto, ser un perfecto 3D coincidencia. Por el contrario, un perfecto 3D coincidencia es claramente una buena cobertura con $k$ elementos.

Por lo tanto, hay un $k$-elemento de cubierta perfecta para este conjunto si y sólo si existe un perfecto 3D coincidentes en nuestro 3D problema de coincidencia.