Localizando subgráficos com alta largura de árvore e grau constante

9

Recebo um gráfico com largura de árvore ke grau arbitrário, e gostaria de encontrar um subgrafo H de G (não necessariamente um subgrafo induzido), de modo que H tenha um grau constante e sua largura de árvore seja a mais alta possível. Formalmente, meu problema é o seguinte: tendo escolhido um grau vinculado d N , qual é a "melhor" função f : NN, de modo que, em qualquer gráfico G com largura de árvore k , eu possa encontrar (esperançosamente eficientemente) um subgrafo H de G com grau máximo dG kHGHdNf:NNGkHGde largura da árvore .f(k)

Obviamente, devemos tomar pois não existem gráficos de alta largura de árvore com grau máximo < 3 . Para d = 3 Eu sei que você pode tomar f tal que f ( k ) = Ω ( k 1 / 100 ) ou assim, apelando para o Chekuri e Chuzhoy grade resultado extração de menord3<3d=3ff(k)=Ω(k1/100)(e usá-lo para extrair um gráfico de grau 3 de alta largura de árvore, por exemplo, uma parede, como menor topológico), com o cálculo do subgrafo sendo possível (em RP). No entanto, este é um resultado muito poderoso com uma prova elaborada, por isso parece errado usá-lo para o que parece ser um problema muito mais simples: eu gostaria de encontrar qualquer subgrafo de grau constante e alta largura de árvore, não um específico como no resultado deles. Além disso, o limite de não é tão bom quanto eu esperava. Claro, ele é conhecido que ele pode ser feito Ω ( k 1 / 20 ) (até desistir eficiência da computação), mas eu espero para algo como Ω ( k )fΩ(k1/20)Ω(k). Então, é possível mostrar que, dado um gráfico de largura de árvore k , existe um subgrafo de G com grau constante e largura de árvore linear em k ?GkGk

Também estou interessado na mesma pergunta exata para largura de caminho em vez de largura de árvore. Para a largura de caminho, não conheço nenhuma extração analógica para a grade menor, então o problema parece ainda mais misterioso ...

a3nm
fonte

Respostas:

12

Veja o artigo de Julia Chuzhoy e eu sobre esparsificadores Treewidth. Mostra-se que se pode obter um grau subgráfico de, no máximo, 3 com treewidth onde k é o treewidth de L . https://arxiv.org/abs/1410.1016 A prova é mais curta que a dos menores da rede, mas ainda assim não é tão fácil assim e se baseia em várias ferramentas anteriores.Ω(k/polylog(k))kG

Suponha que você se contentar com um alvo mais fácil - grau 4 e treewidth , então você pode obtê-lo muito mais facilmente através de resultado de Reed e madeira na grade-like menores. https://arxiv.org/abs/0809.0724Ω(k1/4)

Outro resultado fácil que você pode obter é o seguinte, que é um ponto de partida para algumas das provas mais envolvidas. Você pode obter um subgráfico do de degrau 2 ( k ) e da largura da árvore Ω ( k / p o l y l o g ( k ) ) . Você pode ver o documento sparsifier de largura de árvore para o argumento para conseguir isso.log2(k)Ω(k/polylog(k))

Chandra Chekuri
fonte
11
Comentário adicional. Se alguém pode obter um subgrafo com largura de árvore e grau constante é um problema em aberto muito interessante. Fizemos essa pergunta no papel de dispersão de largura de árvore, mas não temos um bom senso da resposta certa. Um gráfico interessante sobre o qual Bart Jansen perguntou é o hipercubo em n nós com largura de árvore Θ ( n / log n ) e grau inicial Θ ( log n ) . Ω(k)nΘ(n/logn)Θ(logn)
Chandra Chekuri
Obrigado por apontar para Reed e Wood! Vou preencher os detalhes. Thm 1.2 de seu artigo diz que um gráfico G com largura de árvore contém uma grade menor como a ordem l. Agora, um M semelhante a uma grade menor é um subgrafo de G formado por caminhos com um gráfico de interseção bipartido H, portanto, todo vértice em M pertence a no máximo 2 caminhos de M (caso contrário, é um triângulo em H); portanto, M tem um grau máximo 4. Além disso, M possui uma largura de árvore Ω ( l ) : de fato, qualquer árvore dec de M de largura k produz uma árvore dec de H de largura <= 2k (substituindo cada vértice por seus caminhos de membros, no máximo 2), e H temΩ(l4polylog(l))Ω(l)sou menor de idade. Kl
a3nm
Novamente, isso é muito útil, obrigado. É interessante que a questão da largura da árvore linear ainda esteja aberta. (Dito isso, se eu entendi direito, a Conjectura 1.2 no seu artigo sobre sparsifier é sobre um problema um pouco diferente: ele exige que o subgráfico seja uma subdivisão de algum H de tamanho polinomial em k, enquanto eu não estou pedindo isso e só quero o subgrafo possui um grau constante.) Uma última coisa: você sabe se alguma coisa é conhecida sobre esse problema em aberto, exceto a largura do caminho, e não a largura da árvore? Obrigado novamente!
a3nm
@ a3nm Por que você está surpreso que a questão da largura da árvore linear esteja aberta? Atualmente, não temos uma aproximação fatorial constante para a largura da árvore. No que se refere largura de caminho, agora a única maneira de pathwidh aproximado é através da relação entre a largura de caminho treewdith e que mostra . Através da esparsificação de largura de árvore, também é possível obter esparsificação de largura de caminho, mas perdemos um fator log n. Seria bom se esse fosse apenas o fator log pw (G), mas não tenho certeza de como fazê-lo ou se é conhecido. tw(G)pw(G)O(logn)tw(G)
Chandra Chekuri
Obrigado pelas explicações sobre o status da três larguras lineares e também pelas explicações sobre a dispersão de largura de caminho. A última coisa que você mencionou é o tipo de resultado que precisaríamos; pena que a questão ainda esteja aberta. De qualquer forma, muito obrigado novamente por suas explicações!
a3nm