É necessário chamar multiplicação de matrizes

Uma garra é um . Um algoritmo trivial detectará uma garra em . Isso pode ser feito em , onde é o expoente da multiplicação rápida de matrizes, como segue: pegue o subgrafo induzido por para cada vértice e encontre um triângulo em seu complemento. $K_{1,3}$ $O(n^4)$ $O(n^{\omega+1})$ $\omega$ $N[v]$ $v$

Tanto quanto eu sei, esses algoritmos básicos são conhecidos apenas. Spinrad listou em seu livro "representações gráficas eficientes" a detecção de uma garra no tempo como um problema em aberto (8.3, página 103). Para o limite inferior, sabemos que um algoritmo de tempo implicará um algoritmo de tempo para encontrar um triângulo. Portanto, podemos considerar como um limite inferior. $o(n^{\omega+1})$ $O(n^c)$ $O(n^{\max{(c,2)}})$ $\Omega(n^\omega)$

Questão:

Existe algum progresso nisso? Ou algum progresso em mostrar que é impossível?
Existem outros problemas naturais com os algoritmos de tempo $O(n^{\omega+1})$ que são os melhores?

Observação:

Estou pedindo explicitamente a detecção de uma garra, em vez do reconhecimento de gráficos sem garras. Embora um algoritmo geralmente resolva os dois, existem poucas exceções.
Alega-se no Manual de Algoritmos e Ciência da Computação Teórica que ele pode ser encontrado em tempo linear, mas foi apenas um erro de digitação (consulte "representações gráficas eficientes").

graph-theory graph-algorithms graph-classes Yixin Cao
fonte

Você pode usar o método de Alon et al. Para encontrar triângulo em , para cada nó que termina em um que é melhor que se o gráfico não for muito denso.

O (| E |^{1.41})

$O(|E|^{1.41})$

O (| V | \cdot | E |^{1.41})

$O(|V|\cdot |E|^{1.41})$

| V |^{ω + 1}

$|V|^{\omega+1}$

@RB, obrigado por apontar isso. A idéia básica ainda é executar o algoritmo de detecção de qualquer triângulo vezes, que é o que eu quero evitar.

n

$n$

Yixin Cao

Como podemos esperar encontrar algum algoritmo que não esteja relacionado à descoberta de triângulos? Porque qualquer que seja o algoritmo, verifique os vizinhos de cada vértice. Quero dizer que a propriedade é uma propriedade muito local, exceto com a constante diferença de fator que todo vértice deve ser visto. (Ou não consigo imaginar nenhum algoritmo natural que evite essa localidade). Você tem alguma idéia vaga?

Saeed

Talvez seja bom mencionar que, se pudermos encontrar uma garra no tempo f (n), também podemos encontrar um triângulo no tempo f (n + 1) (basta pegar o complemento do gráfico e adicionar mais um vértice conectado a todos ), portanto, não devemos esperar encontrar algo melhor que .

n^{ω}

$n^\omega$

Domotorp

@domotorp, parece que parte é clara, o contrário não é claro, quero dizer por que precisamos de pesquisa linear. Como Yixin também apontou, pode haver outro algoritmo que não usa um algoritmo de busca de triângulo e resolve o problema em

, o que eu acho difícil encontrar esse algoritmo e provavelmente é mais fácil mostrar que qualquer O algoritmo usa a descoberta de triângulo como sub-rotina (ou pode ser convertida) com pesquisa linear nela.

o (n^{ω + 1})

$o(n^{\omega +1})$

Saeed

Respostas:

Penso que podemos fazer um pouco melhor que para gráficos densos, usando multiplicação de matriz retangular. Uma idéia semelhante foi usada por Eisenbrand e Grandoni ("Sobre a complexidade da camarilha de parâmetro fixo e do conjunto dominante", Theoretical Computer Science Volume 326 (2004) 57-67) para detecção de 4 camaradas. $O(n^{1+\omega})$

Seja o gráfico no qual queremos detectar a existência de uma garra. Vamos ser o conjunto de (ordenadas) em pares de vértices . Considere a seguinte matriz booleana de tamanho : cada linha é indexada por alguns , cada coluna é indexada por alguns , e a entrada correspondente é uma se e somente se $G=(V,E)$ $A$ $V$ $M$ $|V|\times |A|$ $u\in V$ $(v,w)\in A$ , e . Considere o produto matriz booleano de e sua transposta . O gráfico tem uma garra, se e somente se existir modo que a entrada de na linha indexada por e a coluna indexada por seja uma. $\{u,v\}\in E$ $\{v,w\}\in E$ $\{u,w\}\notin E$ $M$ $M^T$ $G$ $\{u,v\}\notin E$ $MM^T$ $u$ $v$

A complexidade desse algoritmo é essencialmente a complexidade de calcular o produto booleano de uma matriz por uma matriz , em que indica o número de vértices no gráfico. Sabe-se que esse produto de matriz pode ser calculado no tempo , o que é melhor que para o limite superior mais conhecido em . Obviamente, se (como conjecturado), então as duas abordagens apresentam a mesma complexidade $n\times n^2$ $n^2\times n$ $n$ $O(n^{3.3})$ $O(n^{1+\omega})$ $\omega$ $\omega=2$ . $O(n^3)$

Francois Le Gall
fonte

Ótimo! É exatamente isso que eu quero para a minha primeira pergunta: apenas uma chamada de multiplicação de matrizes, embora seja maior. Vou esperar por mais comentários ou respostas na minha segunda pergunta antes de tomá-la como resposta.

Yixin Cao

Não sei como evitar a multiplicação de matrizes, mas você pode analisá-las de maneira que o tempo seja efetivamente o de um número menor. Esse truque é de $n$

Kloks, Ton; Kratsch, Dieter; Müller, Haiko (2000), "Localizando e contando pequenos subgráficos induzidos eficientemente", Information Processing Letters 74 (3–4): 115-121, doi: 10.1016 / S0020-0190 (00) 00047-8, MR 1761552.

A primeira observação é que, quando você vai multiplicar matrizes, as matrizes não são realmente , mas onde é o grau de cada vértice, porque o que você está procurando é um co-triângulo na vizinhança de cada vértice. $n\times n$ $d\times d$ $d$

Segundo, em um gráfico sem garras, todo vértice deve ter vizinhos. Pois, caso contrário, o conjunto de vizinhos teria poucas arestas para evitar ter um triângulo no complemento. Então, quando você está fazendo multiplicações de matrizes, você só precisa fazer isso em matrizes de tamanho $O(\sqrt m)$ ao invés de. $O(\sqrt m)$ $n$

Além disso, cada aresta pode contribuir para o tamanho do problema de multiplicação de matrizes para apenas dois vértices, seus pontos finais. O pior caso ocorre quando os para o tamanho total desses problemas de multiplicação da matriz são espalhados em $2m$ subproblemas do tamanho $O(\sqrt m)$ cada um, o que fornece um limite de tempo total de, uma melhoria para gráficos esparsos sobre olimite demencionado por R B. $O(\sqrt m)$ $O(m^{(1+\omega)/2})$ $O(nm^{\omega/2})$

David Eppstein
fonte

Uau, essa é uma ideia inteligente, eu estava pensando se é possível fazer uma pesquisa sublinear (na verdade, refutando isso) e nem sequer pensei nas propriedades intrínsecas do problema.

Saeed

Obrigado David. Deixo em aberto por um momento, pois minha segunda pergunta ainda não foi percebida.

Yixin Cao