Encontrando triângulos em um gráfico: outras abordagens além do teste de propriedades?

Estamos trabalhando em um artigo que apresenta alguns algoritmos para encontrar triângulos e motivos de rede (subgráficos de tamanho constante, também conhecidos como gráficos) em uma configuração distribuída. Caracterizamos a troca entre o número de triângulos no gráfico e a carga de comunicação necessária. Estou procurando referências para o trabalho realizado sobre essa questão no modelo centralizado.

O problema é que quase tudo o que encontrei neste tópico que tinha um sabor teórico estava dentro da estrutura dos testes de propriedade . Para ilustrar a diferença - considere o caso de um gráfico com vértices, composto por triângulos todos compartilhando a aresta . Do ponto de vista do teste de propriedades, esse gráfico está muito próximo de ser livre de triângulo (removendo essa aresta crítica), enquanto possui um número linear de triângulos, o que é muito para nossos padrões. $n$ $n-2$ $\left(1,2\right)$

Todas as referências serão apreciadas.

Edit: Estou interessado principalmente em algoritmos que podem determinar se o gráfico contém triângulos rapidamente. Para algoritmos de listagem de triângulo (ou outro subgráfico), o tempo de execução é naturalmente limitado a partir de baixo pelo número de triângulos no gráfico, pois o algoritmo precisa listar todos eles, tornando essas instâncias mais difíceis em certo sentido. Do ponto de vista de um problema de decisão ("sem triângulo ou não"), ter muitos triângulos realmente facilita o problema, pois é possível encontrá-lo facilmente.

reference-request graph-theory graph-algorithms Shir
fonte

Dada a resposta de David, não tenho certeza se entendo mais o que você deseja. Você não gosta da estrutura de teste de propriedades, mas deseja limites de complexidade de consultas? O exemplo que você dá à pergunta é um caso ruim porque também deseja estimar o número de triângulos?

Suresh Venkat

Aqui está o que eu quero - um algoritmo probabilístico, que consulta o gráfico e é capaz e distingue entre gráficos com muitos triângulos e gráficos sem nenhum. Veja, por exemplo, dl.acm.org/citation.cfm?id=1873611 de Gonen, Ron e Shavit. No entanto, em seu artigo, a consulta é restrita (por exemplo, se eu entendi corretamente, consultas de borda não são permitidas, a menos que amostradas em uma distribuição uniforme).

Shir

Então você quer um algoritmo sublinear que calcule o número de triângulos?

Suresh Venkat

algumas observações simples: digamos que você tenha triângulos T e que seja permitido a randomização; então você pode provar: (1) uma aresta e atingirá um triângulo com probabilidade de pelo menos ~ T ^ {2/3} / m, já que o número mínimo de arestas que você pode ter em um gráfico com triângulos T é ~ T ^ {2/3}; depois de ter uma aresta, você pode verificar se está em um triângulo em n etapas, para obter um algoritmo de tempo de execução esperado ~ mn / T ^ {2/3}; (2) você pode escolher um triplo aleatório de vértices e, com probabilidade T / n ^ 3, será um triângulo, o que lhe dará um tempo de execução de ~ n ^ 3 / T. Você também pode fazer algumas coisas um pouco mais sofisticadas. Isso ajuda?

virgi

Ah, e também qualquer algoritmo que possa detectar se um dado gráfico contém um triângulo em ~ n ^ {3-eps} pode ser convertido em um que possa multiplicar nxn matrizes booleanas em ~ n ^ {3-eps / 3} , algoritmos simples de detecção de triângulo simples também são interessantes por esse motivo, embora, é claro, as instâncias difíceis sejam quando você precisa distinguir entre os casos do triângulo 0 ou 1 e, nesse caso, não sabemos nada melhor do que computar o cubo da matriz de adjacência.

virgi

Respostas:

Para várias referências ao problema de teste para a existência de um triângulo (exatamente, não na estrutura de teste de propriedades), consulte Gráfico sem triângulo na Wikipedia. Em particular, Alon, Yuster e Zwick (ESA'94) fornecem um algoritmo O (m ^ {1.41}), e isso também pode ser feito em tempo de multiplicação de matriz rápida, melhor para gráficos densos.

Se você concorda com algo na configuração dos algoritmos de gráfico dinâmico, também tenho um para contar os triângulos:

O índice h de um gráfico e sua aplicação às estatísticas de subgráficos dinâmicos, D. Eppstein e ES Spiro, arXiv: 0904.3741 e WADS 2009.

Em nosso artigo, citamos Chiba e Nishizeki (SICOMP 1985) e Itai e Rodeh (SICOMP 1978) pelos fatos básicos do algoritmo estático que um gráfico com m arestas pode ter no máximo O (m ^ {3/2}) triângulos no na pior das hipóteses e que possam ser listados nessa quantidade de tempo.

David Eppstein
fonte

Obrigado pela resposta rápida. Vejo agora que não estava claro na minha pergunta exatamente o que estamos procurando. Naturalmente, vi as referências na Wikipedia, mas elas não se encaixam, pois estou procurando algo no domínio da complexidade da consulta ou tempo de execução de algum algoritmo probabilístico. Vou editar a pergunta para refletir isso. Então vote na resposta, mas não vou aceitá-la, pois ainda estou procurando uma resposta. :)

Shir

$\Omega(n^2)$ $n$ $O(n^2)$

Se você quiser ver o porquê, considere a seguinte família de gráficos:

$G_{0}$ $v$ $X$ $Y$ $(n - 1)/2$ $X$ $v$ $Y$ $v$

$i \in X$ $j \in Y$ $G_{ij}$ $G_0$ $ij$

$G_0$ $G_{ij}$ $G_0$ $G_{ij}$ $i$ $j$ $(n - 1)^2/4$

Artem Kaznatcheev
fonte

WRT, consulte também "Algoritmos quânticos para o problema do triângulo", Magniez, Santha e Szegedy, SODA'05 e arXiv: quant-ph / 0310134.

David Eppstein

Seu exemplo mostra apenas que, no caso de um único triângulo (eu acho que ele generaliza facilmente para O (1)), ele não caracteriza a troca entre o número de triângulos e a probabilidade de acertar um, ou sugere um boa estratégia de amostragem.

Shir

Θ (n^{2})

$\Theta(n^2)$

Ω (n)

$\Omega(n)$

Ω (\sqrt{N})

$\Omega(\sqrt{N})$

n

$n$

1 - 1 / \sqrt{n}

$1-1/\sqrt{n}$

\sqrt{n}

$\sqrt{n}$

Não entendo exatamente sua pergunta em termos de seu objetivo final. No entanto, você pode considerar a versão FPT do problema de empacotamento em triângulo, se isso ajudar de alguma forma no seu problema. Em particular, você pode considerar o EDTP (Edge Disjoint Triangle Packing) ou o VDTP (Triangle Disjoint Triangle Packing) e fazer o kernel da instância do gráfico para O (k) ou O (k ^ 2), respectivamente, em termos de número de vértices. Você também pode fazer o kernel do número de triângulos [O (k ^ 3)]. Após o kernelization, seria mais fácil analisar os triângulos na instância do gráfico.

Nikhil
fonte