Qual é a noção mais importante de esparsidade para o design de algoritmos de grafos eficientes?

12

Existem várias noções concorrentes de um "gráfico esparso". Por exemplo, um gráfico incorporado na superfície pode ser considerado esparso. Ou um gráfico com densidade de arestas delimitadas. Ou um gráfico com alta circunferência. Um gráfico com grande expansão. Um gráfico com largura de árvore limitada. (Mesmo dentro do subcampo dos gráficos aleatórios, é um pouco ambíguo quanto ao que poderia ser chamado de esparso.) Et cetera.

Que noção de "gráfico esparso" teve o maior impacto no design de algoritmos de gráfico eficientes e por quê? Da mesma forma, que noção de "gráfico denso" ...? (Nota: Karpinski trabalhou bastante nos resultados de aproximação para um modelo padrão de gráficos densos.)

Acabei de ver uma palestra de J. Nesetril em um programa dele (junto com P. Ossona de Mendez) para capturar medidas de escarsidade em gráficos dentro de uma estrutura unificada (assintótica). Minha pergunta - sim, talvez bastante subjetiva e espero campos diferentes - é motivada pelo desejo de capturar uma perspectiva multifacetada sobre o uso da escarsidade em algoritmos (e de preencher lacunas no meu próprio entendimento da questão).

RJK
fonte
Você acha que um gráfico completo também é escasso? Gráficos completos têm grande expansão e largura de cliques limitada.
Yoshio Okamoto
@Yoshio Okamoto: bom ponto - Suponho treewidth teria sido uma escolha melhor lá ...
RJK
6
O programa de J. Nesetril e P. Ossona de Mendez que você mencionou agora é um livro .
vb le

Respostas:

16

Penso que, por qualquer padrão razoável, um gráfico tridimensional n × n × n teria que ser considerado esparso, e isso exclui a maioria das definições candidatas que envolvem revestimentos de superfície ou menores. (Porém, a largura da árvore sublinhada ainda seria possível.)

Minha atual medida favorita de esparsidade é a degeneração . A degenerescência de um gráfico é o mínimo, em todas as ordenações lineares dos vértices do gráfico, do grau máximo negativo na orientação acíclica direcionada do gráfico formada pela orientação de cada aresta dos vértices anteriores para os posteriores na ordenação. Equivalentemente, é o máximo, em todos os subgráficos, do grau mínimo no subgráfico. Assim, por exemplo, gráficos planares têm degeneração cinco porque qualquer subgrafo de um gráfico planar tem um vértice de grau no máximo cinco. A degenerescência é fácil de calcular em tempo linear, e a ordem linear que vem da definição é útil em algoritmos .

A degeneração está dentro de um fator constante de algumas outras medidas padrão, incluindo arboricidade, espessura e o grau médio máximo de qualquer subgráfico, mas acho que é mais difícil usá-las.

David Eppstein
fonte
Esta é uma resposta bastante agradável. Ele destaca como estruturas aparentemente simples, como grades, podem causar danos ao pensar em gráficos esparsos. (Acho que não é muito surpreendente, considerando a importância dos menores da grade para a teoria de Robertson-Seymour.) Seria justo dizer que a degenerescência é para o algoritmo ganancioso, assim como a largura da árvore para a programação dinâmica? Ou talvez haja mais a dizer sobre medidas de esparsidade que impliquem boas ordenações, por exemplo, largura de caminho?
RJK 14/04
@RJK: Para levar esse argumento ao extremo, as grades planares regulares 3 (grades hexagonais / gráficos de parede) têm largura de árvore ilimitada, mas são as mais escassas possível.
András Salamon
@ Andras: Claro, mas que tal um gráfico com pouca largura de árvore que não seja escasso? Nesse sentido (unidirecional), acho que a largura da árvore também se qualifica como uma medida de escarsidade.
RJK 15/04
knkΩ(logn)Θ(logn/loglogn)
8

Parece haver muitas noções "boas" de esparsidade, mas há algo de hierarquia para as noções estruturais de esparsidade que têm um sabor teórico-modelo. Penso que estes tiveram um forte impacto em algoritmos de gráficos eficientes.

kKk+2

As notas do curso de Anuj Dawar de novembro de 2010 também discutem a largura da árvore limitada localmente, o que é incomparável com menores excluídos. Grau delimitado define claramente gráficos esparsos, e esses gráficos limitaram a largura da árvore local, mas não são definíveis por um conjunto de menores excluídos.

O impacto do grau delimitado é claro: geralmente é uma das primeiras restrições mostradas para tornar um problema difícil tratável, por exemplo, o algoritmo de Luks para isomorfismo de gráfico em gráficos de grau delimitado. O impacto de excluir um menor também é claro, pelo menos sob o disfarce de largura de árvore limitada (como Suresh apontou).

A noção de excluir localmente um menor generaliza tanto a largura de árvore limitada localmente quanto os menores excluídos, formando assim a classe "mais geral" na hierarquia. No entanto, ainda não está claro como fazer uso dessa propriedade em algoritmos práticos. Mesmo o caso "tratável" de excluir um menor não tem necessariamente bons algoritmos práticos; constantes grandes abundam nos algoritmos teóricos do modelo. Espero que algumas dessas classes tenham algoritmos praticamente eficientes a longo prazo.

Veja também minha resposta: o que é fácil para gráficos com exclusão menor? para outros comentários relacionados.

András Salamon
fonte
6

Não consigo pensar em nenhuma propriedade de gráfico que tenha tido tanto impacto no design de algoritmos eficientes quanto em largura de árvore limitada e bidimensionalidade em geral.

Suresh Venkat
fonte
1
Oi Suresh: Eu diria que esta é a resposta "certa" para a pergunta principal, mas você gostaria de aprimorar um pouco sua postagem? Sei que são coisas básicas, mas já cometi o erro de estender demais a validade de um conceito de largura - largura de cliques - para gráficos esparsos.
RJK 14/04
1

Pode-se pensar em um gráfico como uma matriz de adjacência - existem várias definições para a escarsidade da matriz (% de zero entradas, por exemplo) que podem ser traduzidas de volta para o próprio gráfico. Além de% de zero entradas, a largura de banda da matriz sob uma reordenação pode ser um bom proxy para a esparsidade do gráfico (parece que a largura de banda está relacionada à degeneração).

lince
fonte