Particionando gráficos enquanto minimiza arestas entre partições

Estou trabalhando para tentar particionar um gráfico triangulado em subgráficos conectados com algumas garantias sobre o número de arestas entre partições. Aqui está um exemplo de um gráfico triangulado que foi particionado em 4 "clusters":

O que eu queria originalmente era um algoritmo que pudesse criar partições de aproximadamente k triângulos (poderia haver algum erro, desde que não fosse muito grande), e consegui descobrir um (em que p é o número total de partições) que poderia encontrar essa partição. Percebi então que ter um grande número de bordas entre partições era prejudicial para a aplicação para a qual eu precisava desse algoritmo.$O(k^2p^2(v+e))$

Idealmente, eu gostaria de um algoritmo que possa manter cada partição dentro de um intervalo de , idealmente que seja um fator constante como 2. Além disso, eu gostaria de poder fazer com que o número de inter-bordas tenha um limite superior isso é "baixo".$k$

Além disso, outro problema que tenho é se eu tenho uma partição que possui essas propriedades e modifico o gráfico seguindo um destes procedimentos:

• Adicionando um conjunto de arestas conectando a vértices existentes
• Adicionando um vértice e um conjunto de arestas conectando ao vértice adicionado
• Removendo um conjunto de arestas
• Removendo um vértice e todas as arestas que se conectam a esse vértice

Quero poder particionar o gráfico e ainda ter cada partição com o tamanho número de arestas cortadas minimizados. (Esta é a solução pela qual estou oferecendo uma recompensa). Isso significa que, usando esse algoritmo, podemos construir qualquer partição começando com um gráfico vazio e adicionando vértices e arestas uma a uma e reparticionando.$k$

Aqui estão algumas restrições adicionais para o problema:

• O gráfico é plano
• Cada "triângulo" é um vértice que possui arestas não direcionadas em triângulos e compartilha uma aresta com
• A partir da afirmação acima, é óbvio que cada vértice neste gráfico tem grau no máximo 3
• O gráfico está conectado
• Cada subgráfico da partição está conectado
• Cada subgrafo possui aproximadamente k vértices
• Existem no máximo arestas entre partições (arestas que contêm vértices de diferentes partições). Se você encontrar um limite semelhante para as arestas entre partições, como ou , isso também funcionará. Não tenho certeza absoluta de que o limite superior das bordas entre partições possa ser menor que portanto, se você puder provar que é impossível fazer melhor, isso também é satisfatório. 2$\sqrt n$ O(logn)O(n$2\sqrt n$$O(\log n)$$O(n)$

Estou em um ponto em que estou preso, portanto, qualquer ajuda com esse problema seria adorável. Se você consegue resolver esse problema, você é o joelhos das abelhas. Caso contrário, se você souber de algum artigo, manual ou algoritmo que possa me indicar, eu agradeceria muito.

Deixe-me saber se eu preciso esclarecer alguma coisa!

EDIT: Aqui estão algumas restrições adicionais, se isso facilitar o problema.

• Estamos lidando com triangulações restritas de delaunay
• Restrições NUNCA será um único vértice
• O gráfico criado a partir da triangulação é construído da seguinte maneira: cada triângulo é representado como um vértice. Cada aresta no gráfico corresponde a uma aresta irrestrita na triangulação. Isso significa que uma aresta restrita entre dois triângulos não aparecerá na representação gráfica da triangulação.

Outra coisa que percebi é que podemos precisar modificar para crescer à medida que cresce, caso contrário, não haverá garantias sub no número de arestas entre partições.n O ( n $k$$n$$O(n)$

Rao tem dois trabalhos sobre o corte mais esparso em gráficos planares, uma aproximação de fator constante no tempo quase-linear parece possível . A bissecção recursiva, embora não seja ideal, pode ser uma abordagem viável para o seu problema.

Satish Rao. Localização de separadores ótimos em gráficos planares . No 28º Simpósio sobre Fundamentos da Ciência da Computação (FOCS), páginas 225-237, 1987.

Satish Rao. Algoritmos mais rápidos para encontrar pequenos cortes de arestas em gráficos planares (resumo estendido). No 24º Simpósio ACM sobre Teoria da Computação (STOC), páginas 229-240, 1992.

Horst D. Simon e Shang-Hua Teng. Quão boa é a bissecção recursiva? No SIAM Journal on Scientific Computing, Volume 18, Edição 5, páginas 1436-1445, 1997.

http://cse.iitkgp.ac.in/~pabitra/paper/barna-sdm07.pdf

$O(k^3)$$k = O(\log n)$

O algoritmo a seguir pode ajudar.

1. Choose any vertex from the graph.

2. Do a BFS untill $O(K)$ vertices has been visited.

3. Create a cluster with the visited vertices. (Connectivity is ensured for the cluster).

4. Remover the visited vertices from the graph.

5. Repeat 1-4 untill all nodes are visited.

$O(K)$$O(K)$$O(N/K)$

A modificação do gráfico adicionando vértices não afetaria a partição. Qualquer partição em que um dos vizinhos do novo vértice esteja, pode ser a partição do novo vértice. Portanto, pode não haver necessidade de reparticionar até que o tamanho de um cluster se torne excessivo.

Editar:

$k$$m$$\mathscr{R}$$k$$\mathscr{R}$$O(K)$$O(K)$$\mathscr{R}$$k$$O(log n)$ então pode ser que as bordas entre partições podem ser reduzidas.

fiz alguma pesquisa sobre isso, mas adiei a postar imediatamente para ver o que outras respostas se materializariam e agora estou postando isso para não jogar fora algumas idéias / leads diversos que poderiam ter algum valor (embora o autor da pergunta já tenha indicado que ele agora acha aceitável) responda).

na inspeção, existem muitas restrições sobre esse problema e é possível que seja necessário um artigo inteiro para criar um algoritmo e provar que ele satisfaz todos eles (o que obviamente está fora do escopo do formato stackexchange). no entanto, existem algumas abordagens básicas para enfrentar esse tipo de problema

1. empírico. gere gráficos aleatórios que se ajustem às restrições ou use gráficos de alguns conjuntos de dados que correspondam às condições, tente algoritmos diferentes neles e observe o desempenho. pode-se achar que um algoritmo satisfaz empiricamente as condições requeridas. se alguém for mais rigoroso, poderá tentar criar uma prova a partir da observação empírica se ela for 100% satisfeita por grandes conjuntos de dados. também para pesquisas empíricas, muitas vezes ajuda a saber como os conjuntos de dados são obtidos / gerados, qual é a sua natureza / origem.

2. a questão não tem citações relacionadas à literatura / refs. Então, quais são os tipos de algoritmos mais próximos na literatura? para esse tipo de problema, vários tipos de áreas de pesquisa podem se sobrepor. existem pesquisas sobre gráficos planares, partições de gráficos, cortes de gráficos, separadores de gráficos, gráficos triangulares de particionamento, etc .; não é óbvio descobrir o tema principal desta questão até onde foi formulada ou qual subárea de pesquisa específica (algoritmo de grafos) mais diretamente incidiria sobre ela.

dadas essas qualificações, um tema básico da pergunta parece ser "particionar gráficos planares". aqui estão algumas referências recentes importantes sobre esse tópico que podem ser úteis e mostram temas / ângulos adicionais da pesquisa relacionada atual. existem alguns algoritmos implementados e eles podem estar disponíveis mediante solicitação dos autores.

o ^terceiro envolve particionamento com pesos, o que generaliza para pesos iguais, mas fornece uma estrutura adicional para consideração / investigação: todas as condições da pergunta poderiam ser preenchidas por algum tipo de esquema de atribuição de peso? (isso também pode estar relacionado ao requisito de ter algum tipo de controle dinâmico ou ajuste das soluções também mencionadas na pergunta.)

• Trabalhos de particionamento espectral: gráficos planares e malhas por elementos finitos Spielman / Teng

• Algoritmos lineares para um problema de partição k de gráficos planares sem especificar bases Wada, Chen

• Particionando gráficos planares com custos e pesos Aleksandrov et al