Encontrar una subdistribución

Question

Dejemos que $\alpha$ sea una composición de $n$ en partes no nulas y que $\mathcal L$ sea un conjunto de permutaciones de un subconjunto finito que tenga $n$ elementos, de manera que cada elemento de $\mathcal L$ es constante en cada parte de $\alpha$ .

Por ejemplo, para $n=8$ podríamos tener $\alpha=(3, 2, 1, 1, 1)$ y $\mathcal L = \{ A A A | B B | A | B | C | , B B B | A A | C | A | A \}$ .

¿Existe un buen algoritmo para decidir si existe un subconjunto no trivial $S$ de las partes de $\alpha$ tal que para todos los elementos $w$ en $\mathcal L$ el conjunto de elementos correspondientes en $w$ es el mismo?

En el ejemplo anterior, tomando $S=\{1,2,4\}$ designa una subdistribución no trivial, compuesta por tres $A$ y tres $B$ 's.

Más generalmente, ¿podemos encontrar eficientemente todos los subconjuntos $S$ que son mínimos con respecto a la inclusión?

Como ejemplo adicional, si todas las partes de $\alpha$ son iguales a $1$ y $\mathcal L$ consiste en la permutación de identidad de $\{1,\dots,n\}$ y otra permutación $\pi$ , entonces los subconjuntos $S$ son precisamente los índices de los elementos de los ciclos de $\pi$ . Por tanto, admite una subdistribución no trivial si y sólo si $\pi$ no es un ciclo.

Answer 1

Se puede resolver el problema mediante programación lineal entera de la siguiente manera. Sea $a_{i,j,k}$ denotan el número de veces en permutación $i$ y parte $j$ esa carta $k$ aparece. Sea la variable de decisión binaria $x_j$ indicar si una parte $j$ está seleccionado. Sea la variable de decisión entera no negativa $y_k$ representan el número de veces que la letra $k$ se selecciona en cada permutación. El problema es minimizar $\sum_j x_j$ con sujeción a \begin{align} \sum_j a_{i,j,k} x_j &= y_k &&\text{for all $i$ and $k$}\tag1 \\ \sum_j x_j &\ge 1 \tag2 \end{align} Restricción $(1)$ obliga a cada permutación $i$ para tener el mismo número de apariciones de la letra $k$ en todas las partes seleccionadas. Restricción $(2)$ evita la solución trivial cero.

Para sus datos de muestra, una solución óptima es $x=(0,0,1,0,1)$ y $y=(1,0,1)$ que corresponde a $S=\{3,5\}$ , con una $A$ y una $C$ .

Answer 2

Este problema es NP-completo porque se puede reducir 3DM a ella. Supongamos que se nos da un hipergrafo 3uniforme $(V,E)$ como entrada de 3DM. Los vértices del hipergrafo $V$ corresponderá a las permutaciones de $\mathcal L$ de tal manera que cada permutación consistirá en A's y B's únicas, excepto el final, que tiene una C, luego dos C's, luego $n-3$ D, por ejemplo, A|B|B|A|A|C|CC|(n-3)D. Elegimos $n=|E|+3$ el número de aristas del hipergrafo más tres. Si un vértice es incidente a una arista, entonces ponemos una B a la parte correspondiente, en caso contrario una A. Además, tenemos una permutación especial que está toda vacía, excepto sus 3 últimas partes, donde tiene xA|B|CCC, donde $x=|V|/3-1$ , por lo que parece D|D..D|xA|B|CCC. Es sencillo ver que esto tiene una solución si y sólo si el 3DM tuviera una.