Será treewidth

Seja fixo e seja um gráfico (conectado). Se não me engano, segue-se do trabalho de Bodlaender [1, Teorema 3.11] que, se a largura de árvore de é aproximadamente pelo menos , contém uma estrela como menor. $k$ $G$ $G$ $2k^3$ $G$ $K_{1,k}$

Podemos reduzir o termo ? Ou seja, diz treewidth pelo menos já implica a existência de um -minor? Existe uma prova em algum lugar? $2k^3$ $k$ $K_{1,k}$

[1] Bodlaender, HL (1993). Em tempo linear, testes menores com pesquisa em profundidade. Journal of Algorithms, 14 (1), 1-23.

graph-theory treewidth graph-minor Juho
fonte

Um resultado vagamente relacionados de Demaine e Hajiaghayi : Para um gráfico fixo

, qualquer

-minor-livre gráfico de treewidth

tem uma

da grade do gráfico menor.

H

$H$

H

$H$

w

$w$

Ω (w) \times Ω (w)

$\Omega(w) \times \Omega(w)$

Mhum

@mhum a constante no

depende exponencialmente de

, aplicá-lo diretamente resultará em um limite inferior a

Ω

$\Omega$

| H |

$|H|$

2 k^{3}

$2k^3$

Daniello

@daniello Esse é realmente o caso. A constante não é muito agradável e a especialização em gráficos livres de menores de

também não é ótima. Eu só queria apontar um resultado vagamente relacionado.

H

$H$

Mhum

É verdade que cada grafo sem menor tem treewidth no máximo . Provamos isso abaixo, primeiro algumas definições: $G$ $K_{1,k}$ $k-1$

Deixe- ser o treewidth de e ser o tamanho máximo de um bando em . Um gráfico é uma triangulação de se é um subgrafo de e é cordal (isto é, não possui ciclos induzidos em pelo menos vértices). Uma triangulação de é uma triangulação mínima, se não subgráfico adequada de é também uma triangulação de . Um subconjunto de vértices de $tw(G)$ $G$ $\omega(G)$ $G$ $H$ $G$ $G$ $H$ $H$ $4$ $H$ $G$ $H$ $G$ $X$ $G$ $H$ $G$ $X$ $H$

t w (G) = min_{H} ω (H) - 1

$tw(G) = \min_{H} \omega(H) - 1$

H

$H$

G

$G$

A fórmula acima implica que para provar que é suficiente provar que todas as possíveis panelinhas máximas de têm tamanho no máximo . Agora provamos isso. Seja uma potencial camarilha máxima de e suponha que . $tw(G) \leq k-1$ $G$ $k$ $X$ $G$ $|X| \geq k+1$

Usaremos a seguinte caracterização de potenciais cliques máximos: um conjunto de vértices é um clique máximo potencial em se, e somente se, para cada par , de vértices não adjacentes (distintos) em houver um caminho a partir de para em com todos os seus vértices internos fora de . Essa caracterização pode ser encontrada no artigo Largura da árvore e preenchimento mínimo: agrupando os separadores mínimos de Bouchitte e Todinca. $X$ $G$ $u$ $v$ $X$ $P_{u,v}$ $u$ $v$ $G$ $X$

Com essa caracterização é fácil derivar uma menor de . Vamos . Para cada vértice , quer é uma aresta de ou há um caminho a partir de para , com todos os vértices internos fora . Para todos os que não são adjacentes a contratam todos os vértices internos de em . Terminamos com um menor de no qual é adjacente a todo o , e $K_{1,k}$ $X$ $u \in X$ $v \in X \setminus \{u\}$ $uv$ $G$ $P_{u,v}$ $u$ $v$ $X$ $v \in X$ $u$ $P_{u,v}$ $u$ $G$ $u$ $X$ $|X| \geq k+1$ . Portanto, o grau de nesse menor é pelo menos , completando a prova. $u$ $k$

daniello
fonte

Obrigado Daniel! Você sabe se o mesmo argumento (ou resultado, na verdade) foi publicado em algum lugar?

Juho

Não tenho uma referência, mas me lembro que um argumento semelhante (possivelmente menos restritivo) para gráficos livres de está escrito em algum lugar. Infelizmente não tenho um ponteiro mais concreto.

K_{2, r}

$K_{2,r}$

Daniello

Será treewidth

Respostas: