Cluster de consenso usando união de conjuntos

Já publiquei essa pergunta há algum tempo no MathOverflow , mas, pelo que sei, ela ainda está aberta, por isso estou publicando-a aqui na esperança de que alguém possa ter ouvido falar dela.

Declaração do problema

Seja , e três partes em partes não vazias (indicadas por 's, ' e 's) do conjunto { }. Encontre duas permutações e que minimizem $P$ $Q$ $R$ $p$ $P_h$ $Q_i$ $R_j$ $1,2,\ldots,n$ $\pi$ $\sigma$

\sum_{i = 1}^{p} | P_{i} \cup Q_{π_{i}} \cup R_{σ_{i}} | .

$\sum_{i=1}^p\left|P_i\cup Q_{\pi_i}\cup R_{\sigma_i}\right|.$

Questões

1) Qual é a complexidade deste problema (ou do problema de decisão correspondente)?

2) Se o problema é realmente solucionável no tempo polinomial, ele permanece verdadeiro para qualquer número de partições? $k\geq 4$

Trabalho prévio

Berman, DasGupta, Kao e Wang ( http://dx.doi.org/10.1016/j.ipl.2007.06.008 ) estudam um problema semelhante para partições , mas usando 's emparelhados em vez de nas opções acima soma. Eles provam que o problema é MAX-SNP-difícil para , mesmo quando cada parte possui apenas dois elementos, reduzindo MAX-CUT em gráficos cúbicos para um caso especial do problema e fornecendo um - aproximação para qualquer . Até agora, não pude encontrar meu problema na literatura ou adaptar sua prova. $k$ $\Delta$ $\cup$ $k=3$ $(2-2/k)$ $k$

Subcasas fáceis

Aqui estão algumas subcasas que considero solucionáveis em tempo polinomial:

o caso ; $k=2$
o caso , para qualquer ; $p=2$ $k$

Além disso, quando , não há duas partes iguais e todas as partes têm tamanho , temos o limite inferior (não sei se está apertado). $k=3$ $2$ $3p+1$

co.combinatorics np-hardness Anthony Labarre
fonte

Respostas:

O problema é NP-difícil. A prova é por redução do seguinte problema:

Dado um gráfico tripartido com vértices em cada parte, existem triângulos separados por vértices em ? $G$ $N$ $N$ $G$

Aqui está a redução: dada uma instância do problema acima, deixe , , denotar o conjunto de vértices em cada parte de e seja o conjunto de arestas entre e . Além disso, o número de vértices em cada parte por . $G$ $A_1$ $A_2$ $A_3$ $G$ $E_{ij}$ $A_i$ $A_j$ $1,\dotsc,N$

Construímos uma instância do seu problema com , onde é um número grande (digamos, ) . O primeiroelementos de correspondem às arestas de . A partição é definida da seguinte forma: para é o conjunto de arestas que têm o ésimo vértice de como um de seus pontos finais. Claramente esses conjuntos são disjuntos e sua união é . é tudo o resto, ou seja, $n = |E(G)| + M$ $M$ $M = 10 |E(G)|$ $p = N + 1$ $|E(G)|$ $\{1,\dotsc,n\}$ $G$ $P$ $P_i$ $i=1,\dotsc,N$ $i$ $A_1$ $E_{1,2} \cup E_{1,3}$ $P_{N+1}$ $E_{2,3} \cup \{|E(G)| + 1, \dotsc, |E(G)| + M\}$ . Da mesma forma, definimos usando vez de e usando vez de . $Q$ $A_2$ $A_1$ $R$ $A_3$ $A_1$

$3|E(G)| - 3N + M$ $G$ $N$ $M$ $2 M$ $P_{N+1}$ $Q_{N+1}$ $R_{N+1}$ $|E(G)| + M$ $2 |E(G)| - 3 N$ . Agora, nota que a interseção de cada e cada é no máximo um (e similarmente para e , e também para e ). Portanto, a função objetivo é minimizada se todas essas interseções puderem ser 1 ao mesmo tempo. Isto corresponde a disjuntos triângulos em . $P_i$ $Q_j$ $P_i$ $R_k$ $Q_j$ $R_k$ $N$ $G$

Mohammad
fonte