Hay varias nociones en competencia de un "gráfico disperso". Por ejemplo, un gráfico empotrable en la superficie podría considerarse escaso. O un gráfico con densidad de borde acotada. O un gráfico con gran circunferencia. Un gráfico con gran expansión. Un gráfico con ancho de árbol acotado. (Incluso dentro del subcampo de los gráficos aleatorios, es un poco ambiguo en cuanto a lo que podría llamarse disperso). Etcétera.
¿Qué noción de "gráfico disperso" ha tenido el mayor impacto en el diseño de algoritmos de gráficos eficientes, y por qué? Del mismo modo, ¿qué noción de "gráfico denso" ...? (Nota: Karpinski ha trabajado mucho en los resultados de aproximación para un modelo estándar de gráficos densos).
Acabo de ver una charla de J. Nesetril sobre un programa suyo (junto con P. Ossona de Méndez) para capturar medidas de escasez en gráficos dentro de un marco unificado (asintótico). Mi pregunta, sí, tal vez bastante subjetiva y espero diferentes campos, está motivada por el deseo de captar una perspectiva multifacética sobre el uso de la escasez en los algoritmos (y tapar cualquier brecha en mi propia comprensión del problema).
Respuestas:
Creo que, según cualquier estándar razonable, un gráfico de cuadrícula tridimensional n × n × n tendría que considerarse escaso, y eso descarta la mayoría de las definiciones de candidatos que incluyen incrustaciones en la superficie o menores. (Sin embargo, el ancho de árbol sublineal aún sería posible).
Mi medida de escasez favorita actual es la degeneración . La degeneración de un gráfico es el mínimo, sobre todos los ordenamientos lineales de los vértices del gráfico, del grado de salida máximo en la orientación acíclica dirigida del gráfico formado al orientar cada borde desde los vértices anteriores al posterior en el ordenamiento. De manera equivalente, es el máximo, sobre todas las subgrafías, del grado mínimo en la subgrafía. Entonces, por ejemplo, los gráficos planos tienen degeneración cinco porque cualquier subgrafo de un gráfico plano tiene un vértice de grado como máximo cinco. La degeneración es fácil de calcular en tiempo lineal, y el orden lineal que proviene de la definición es útil en algoritmos .
La degeneración está dentro de un factor constante de algunas otras medidas estándar que incluyen la arboricidad, el grosor y el grado promedio máximo de cualquier subgrafo, pero creo que son más difíciles de usar.
fuente
Parece que hay muchas nociones "buenas" de escasez, pero hay una especie de jerarquía para esas nociones estructurales de escasez que tienen un sabor de modelo teórico. Creo que estos han tenido un fuerte impacto en algoritmos de gráficos eficientes.
Las notas del curso de Anuj Dawar de noviembre de 2010 también analizan el ancho de árbol limitado localmente, que es incomparable con los menores excluidos. El grado acotado define claramente gráficos dispersos, y dichos gráficos tienen un ancho de árbol local acotado, pero no son definibles por un conjunto de menores excluidos.
El impacto del grado acotado es claro: a menudo es una de las primeras restricciones que se muestra que hace que un problema difícil sea manejable, por ejemplo, el algoritmo de Luks para el isomorfismo gráfico en gráficos de grado acotado. El impacto de excluir a un menor también es claro, al menos en forma de ancho de árbol acotado (como señaló Suresh).
La noción de excluir localmente a un menor generaliza tanto el ancho de árbol limitado localmente como los menores excluidos, formando así la clase "más general" en la jerarquía. Sin embargo, aún no está claro cómo utilizar esta propiedad en algoritmos prácticos. Incluso el caso "tratable" de excluir a un menor no necesariamente tiene buenos algoritmos prácticos; abundantes constantes abundan en los algoritmos modelo-teóricos. Espero que algunas de estas clases tengan algoritmos prácticamente eficientes a largo plazo.
Vea también mi respuesta ¿Qué es fácil para los gráficos excluidos menores? para más comentarios relacionados.
fuente
No puedo pensar en ninguna propiedad gráfica que haya tenido tanto impacto en el diseño de algoritmos eficientes como el ancho de árbol limitado y la bidimensionalidad en general.
fuente
Uno puede pensar en un gráfico como una matriz de adyacencia: hay varias definiciones para la dispersión de la matriz (% de entradas cero, por ejemplo) que podrían traducirse nuevamente al gráfico en sí. Aparte del% de entradas cero, el ancho de banda de la matriz bajo un reordenamiento podría ser un buen proxy para la dispersión del gráfico (parece que el ancho de banda está relacionado con la degeneración).
fuente