Poder de la hoja

En el área matemática de la teoría de grafos , una potencia de $k$ hojas de un árbol $T$ es un grafo $G$ cuyos vértices son las hojas de $T$ y cuyas aristas conectan pares de hojas cuya distancia en $T$ es como máximo $k$ . Es decir, $G$ es un subgrafo inducido de la potencia del grafo ⁠ ⁠ $Estilo de visualización Tk$ , inducido por las hojas de $T$ . Para un grafo $G$ construido de esta manera, $T$ se llama raíz $de k$ hojas de $G$ .

Un gráfico es una potencia de hoja si es una potencia $de k$ hojas para algún $k$ . ^[1] Estos gráficos tienen aplicaciones en filogenia , el problema de reconstruir árboles evolutivos.

Clases relacionadas de gráficos

Dado que las potencias de los grafos fuertemente cordales son fuertemente cordales y los árboles son fuertemente cordales, se deduce que las potencias de las hojas son grafos fuertemente cordales. ^[2] En realidad, las potencias de las hojas forman una subclase propia de los grafos fuertemente cordales; un grafo es una potencia de las hojas si y solo si es un grafo NeST de tolerancia fija ^[3] y tales grafos son una subclase propia de los grafos fuertemente cordales. ^[4]

En Brandstädt et al. (2010) se demuestra que los grafos de intervalos y la clase más amplia de grafos de trayectorias dirigidas con raíz son potencias de hojas. Los grafos de indiferencia son exactamente las potencias de hojas cuyos árboles subyacentes son árboles de orugas .

Las potencias de hoja $k para valores acotados de$ $k$ tienen un ancho de camarilla acotado , pero esto no es cierto para las potencias de hoja con exponentes ilimitados. ^[5]

Estructura y reconocimiento

Un grafo es una potencia de 3 hojas si y solo si es un grafo cordal libre de (toro, dardo, gema) . ^[6] Con base en esta caracterización y otras similares, las potencias de 3 hojas pueden reconocerse en tiempo lineal . ^[7]

Rautenbach (2006) y Brandstädt, Le y Sritharan (2008) ofrecen caracterizaciones de potencias de 4 hojas, que también permiten el reconocimiento en tiempo lineal. Chang y Ko (2007) ^[8] y Ducoffe (2018), ^[9] también resuelven el reconocimiento de los gráficos de potencia de 5 y 6 hojas en tiempo lineal , respectivamente.

Para $k \geq 7,$ el problema de reconocimiento de potencias $de k$ hojas no se resolvió durante mucho tiempo, pero Lafond (2021) demostró que las potencias $de k$ hojas se pueden reconocer en tiempo polinomial para cualquier $k$ fijo . Sin embargo, la alta dependencia del parámetro $k$ hace que este algoritmo no sea adecuado para el uso práctico.

Además, se ha demostrado que el reconocimiento de potencias $de k$ hojas es manejable con parámetros fijos cuando se parametriza mediante $k$ y la degeneración del gráfico de entrada. ^[10]

Notas

^ Nishimura, Ragde y Thilikos (2002).
^ Dahlhaus y Duchet (1987); Lubiw (1987); Raychaudhuri (1992).
^ Brandstädt y otros (2010); Hayward, Kearney y Malton (2002).
^ Broin y Lowe (1986); Bibelnieks y Dearing (1993).
^ Brandstädt y Hundt (2008); Gurski y Wanke (2009).
^ Dom y otros (2006); Rautenbach (2006)
^ Brandstädt y Le (2006).
^ Ko, Ming-Tat; Chang, Maw-Shang (21 de junio de 2007). "El problema de la raíz de 3-Steiner". Conceptos de teoría de grafos en informática . Apuntes de clase en informática. Vol. 4769. Springer, Berlín, Heidelberg. págs. 109-120. doi :10.1007/978-3-540-74839-7_11. ISBN 9783540748380.
^ Ducoffe, Guillaume (4 de octubre de 2018). "Reconocimiento de potencias de 4-Steiner en tiempo polinomial". arXiv : 1810.02304 [cs.CC].
^ Eppstein, David; Havvaei, Elham (1 de agosto de 2020). "Reconocimiento de potencia de hoja parametrizada mediante incrustación en productos de gráficos". Algorithmica . 82 (8): 2337–2359. arXiv : 1810.02452 . doi :10.1007/s00453-020-00720-8. ISSN 1432-0541. S2CID 218988055.

Referencias

Bibelnieks, E.; Dearing, PM (1993), "Gráficos de tolerancia de subárboles de vecindad", Discrete Applied Mathematics , 43 : 13–26, doi :10.1016/0166-218X(93)90165-K.
Brandstädt, Andreas; Hundt, Christian (2008), "Los grafos ptolemaicos y los grafos de intervalo son potencias de hojas", LATIN 2008: Informática teórica , Lecture Notes in Comput. Sci., vol. 4957, Springer, Berlín, págs. 479–491, doi :10.1007/978-3-540-78773-0_42, ISBN 978-3-540-78772-3, Sr. 2472761.
Brandstädt, Andreas ; Hundt, Christian; Mancini, Federico; Wagner, Peter (2010), "Los grafos de trayectorias dirigidas con raíz son potencias de hojas", Discrete Mathematics , 310 (4): 897–910, doi : 10.1016/j.disc.2009.10.006.
Brandstädt, Andreas ; Le, Van Bang (2006), "Estructura y reconocimiento temporal lineal de potencias de 3 hojas", Information Processing Letters , 98 (4): 133–138, CiteSeerX 10.1.1.144.3486 , doi :10.1016/j.ipl.2006.01.004.
Brandstädt, Andreas ; Le, Van Bang; Sritharan, R. (2008), "Estructura y reconocimiento temporal lineal de potencias de 4 hojas", ACM Transactions on Algorithms , 5 : 1–22, doi :10.1145/1435375.1435386, S2CID 6114466.
Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999), Clases de grafos: un estudio , Monografías SIAM sobre matemáticas discretas y aplicaciones, ISBN 978-0-89871-432-6.
Broin, MW; Lowe, TJ (1986), "Gráficos de tolerancia de subárboles de vecindad", SIAM J. Algebr. Discrete Methods , 7 : 348–357, doi :10.1137/0607039.
Dahlhaus, E.; Duchet, P. (1987), "Sobre grafos fuertemente cordales", Ars Combinatoria , 24 B : 23–30.
Dahlhaus, E.; Manuel, PD; Miller, M. (1998), "Una caracterización de grafos fuertemente cordales", Discrete Mathematics , 187 (1–3): 269–271, doi :10.1016/S0012-365X(97)00268-9.
Dom, M.; Guo, J.; Hüffner, F.; Niedermeier, R. (2006), "Compensación de errores en problemas de raíces foliares", Algorithmica , 44 (4): 363–381, CiteSeerX 10.1.1.218.490 , doi :10.1007/s00453-005-1180-z, S2CID 75279.
Farber, M. (1983), "Caracterizaciones de grafos fuertemente cordales", Discrete Mathematics , 43 (2–3): 173–189, doi :10.1016/0012-365X(83)90154-1.
Gurski, Frank; Wanke, Egon (2009), "El ancho NLC y el ancho clique para potencias de gráficos de ancho de árbol acotado", Discrete Applied Mathematics , 157 (4): 583–595, doi : 10.1016/j.dam.2008.08.031 , MR 2499471.
Hayward, RB; Kearney, PE; Malton, A. (2002), "Gráficos NeST", Matemáticas Aplicadas Discretas , 121 (1–3): 139–153, doi : 10.1016/s0166-218x(01)00207-4.
Lafond, Manuel (2021), "Reconocimiento de potencias de k-hojas en tiempo polinomial, para k constante", Actas del Simposio Anual ACM-SIAM de 2022 sobre Algoritmos Discretos (SODA) : 1384–1410, arXiv : 2110.15421.
Lubiw, A. (1987), "Ordenamientos doblemente léxicos de matrices", SIAM Journal on Computing , 16 (5): 854–879, doi :10.1137/0216057.
McKee, TA (1999), "Una nueva caracterización de grafos fuertemente cordales", Discrete Mathematics , 205 (1–3): 245–247, doi : 10.1016/S0012-365X(99)00107-7.
Nishimura, N.; Ragde, P.; Thilikos, DM (2002), "Sobre potencias gráficas para árboles con hojas etiquetadas", Journal of Algorithms , 42 : 69–108, CiteSeerX 10.1.1.43.1127 , doi :10.1006/jagm.2001.1195.
Rautenbach, D. (2006), "Algunas observaciones sobre las raíces de las hojas", Discrete Mathematics , 306 (13): 1456–1461, doi :10.1016/j.disc.2006.03.030.
Raychaudhuri, A. (1992), "Sobre las potencias de grafos fuertemente cordales y grafos de arco circular", Ars Combinatoria , 34 : 147–160.
Eppstein, D.; Havvaei, H. (2020), "Reconocimiento de potencia de hoja parametrizada mediante incrustación en productos de gráficos", Algorithmica , 82 (8): 2337–2359, arXiv : 1810.02452 , doi :10.1007/s00453-020-00720-8, S2CID 218988055.