Técnica del panadero

En informática teórica , la técnica de Baker es un método para diseñar esquemas de aproximación en tiempo polinomial (PTAS) para problemas en grafos planares . Recibe su nombre en honor a Brenda Baker , quien la anunció en una conferencia en 1983 y la publicó en el Journal of the ACM en 1994.

La idea de la técnica de Baker es dividir el gráfico en capas, de modo que el problema pueda resolverse de manera óptima en cada capa, y luego combinar las soluciones de cada capa de una manera razonable que dé como resultado una solución factible. Esta técnica ha proporcionado PTAS para los siguientes problemas: isomorfismo de subgrafos , conjunto independiente máximo , cobertura mínima de vértices , conjunto mínimo dominante , conjunto mínimo dominante de aristas , coincidencia máxima de triángulos y muchos otros.

La teoría de bidimensionalidad de Erik Demaine , Fedor Fomin, Hajiaghayi y Dimitrios Thilikos y sus descomposiciones simplificadoras derivadas (Demaine, Hajiaghayi y Kawarabayashi (2005), Demaine, Hajiaghayi y Kawarabayashi (2011)) generaliza y expande en gran medida la aplicabilidad de la técnica de Baker para un vasto conjunto de problemas en grafos planares y, más generalmente, grafos que excluyen un menor fijo , como los grafos de género acotado, así como otras clases de grafos no cerrados bajo menores como los grafos 1-planares .

Ejemplo de técnica

El ejemplo que utilizaremos para demostrar la técnica de Baker es el problema del conjunto independiente del peso máximo.

Algoritmo

CONJUNTO INDEPENDIENTE( , , ) ${\displaystyle G}$ ${\displaystyle w}$ ${\displaystyle \epsilon }$ Elija un vértice arbitrario y encuentre los niveles de búsqueda en amplitud para rooteado en : ${\displaystyle r}$  ${\displaystyle k=1/\epsilon }$ ${\displaystyle G}$ ${\displaystyle r}$  ${\displaystyle {\pmod {k}}}$ ${\displaystyle \{V_{0},V_{1},\ldots ,V_{k-1}\}}$ para encontrar los componentes después de eliminar ${\displaystyle \ell =0,\ldots ,k-1}$ ${\displaystyle G_{1}^{\ell },G_{2}^{\ell },\ldots ,}$ ${\displaystyle G}$ ${\displaystyle V_{\ell }}$ para calcular , el conjunto independiente de peso máximo de ${\displaystyle i=1,2,\ldots }$ ${\displaystyle S_{i}^{\ell }}$ ${\displaystyle G_{i}^{\ell }}$  ${\displaystyle S^{\ell }=\cup _{i}S_{i}^{\ell }}$ Sea la solución de máximo peso entre ${\displaystyle S^{\ell ^{*}}}$ ${\displaystyle \{S^{0},S^{1},\ldots ,S^{k-1}\}}$ devolver  ${\displaystyle S^{\ell ^{*}}}$

Nótese que el algoritmo anterior es factible porque cada uno es la unión de conjuntos independientes disjuntos. ${\displaystyle S^{\ell }}$

Programación dinámica

La programación dinámica se utiliza cuando calculamos el conjunto independiente de peso máximo para cada . Este programa dinámico funciona porque cada uno es un grafo -externoplanar . Muchos problemas NP-completos se pueden resolver con programación dinámica en grafos -externoplanares. La técnica de Baker se puede interpretar como cubrir los grafos planares dados con subgrafos de este tipo, encontrar la solución para cada subgrafo utilizando programación dinámica y unir las soluciones. ${\displaystyle G_{i}^{\ell }}$ ${\displaystyle G_{i}^{\ell }}$ ${\displaystyle k}$ ${\displaystyle k}$

Referencias

• Baker, Brenda S. (1983), "Algoritmos de aproximación para problemas NP-completos en grafos planares (versión preliminar)", 24.º Simposio anual sobre fundamentos de la informática, Tucson, Arizona, EE. UU., 7-9 de noviembre de 1983 , IEEE Computer Society, págs. 265-273, doi :10.1109/SFCS.1983.7
• Baker, Brenda S. (1994), "Algoritmos de aproximación para problemas NP-completos en grafos planares", Journal of the ACM , 41 (1): 153–180, doi : 10.1145/174644.174650 , MR  1369197, S2CID  9706753
• Bodlaender, Hans L. (1988), "Programación dinámica en grafos con ancho de árbol limitado", en Lepistö, Timo; Salomaa, Arto (eds.), Autómatas, lenguajes y programación, 15.º coloquio internacional, ICALP '88, Tampere, Finlandia, 11-15 de julio de 1988, Actas , Lecture Notes in Computer Science , vol. 317, Springer, págs. 105-118, doi :10.1007/3-540-19488-6_110, hdl : 1874/16258 , ISBN 978-3-540-19488-0
• Demaine, Erik D.; Hajiaghayi, Mohammad Taghi; Kawarabayashi, Ken-ichi (2005), "Teoría algorítmica de grafos menores: descomposición, aproximación y coloración", 46.º Simposio anual IEEE sobre fundamentos de la informática (FOCS 2005), 23-25 ​​de octubre de 2005, Pittsburgh, PA, EE. UU., Actas (PDF) , IEEE Computer Society, págs. 637-646, doi :10.1109/SFCS.2005.14, ISBN 0-7695-2468-0, Número de identificación del sujeto  13238254
• Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Kawarabayashi, Ken-ichi (2011), "Descomposición de contracción en grafos libres de J-menores y aplicaciones algorítmicas", en Fortnow, Lance; Vadhan, Salil P. (eds.), Actas del 43.° Simposio ACM sobre teoría de la computación, STOC 2011, San José, CA, EE. UU., 6-8 de junio de 2011 , ACM, págs. 441-450, doi : 10.1145/1993636.1993696, hdl : 1721.1/73855 , ISBN 9781450306911, Número de identificación del sujeto  16516718
• Demaine, E. ; Hajiaghayi, M.; Nishimura, N.; Ragde, P.; Thilikos, D. (2004), "Algoritmos de aproximación para clases de grafos que excluyen grafos de cruce simple como menores.", J. Comput. Syst. Sci. , 69 (2): 166–195, doi : 10.1016/j.jcss.2003.12.001.
• Eppstein, D. (2000), "Diámetro y ancho de árbol en familias de grafos menores cerrados", Algorithmica , 27 (3): 275–291, arXiv : math/9907126v1 , doi :10.1007/s004530010020, S2CID  3172160.
• Eppstein, David (1999), "Isomorfismo de subgrafos en grafos planares y problemas relacionados", Journal of Graph Algorithms and Applications , 3 (3): 1–27, doi : 10.7155/jgaa.00014 , MR  1750082, S2CID  2303110
• Grigoriev, Alexander; Bodlaender, Hans L. (2007), "Algoritmos para gráficos integrables con pocos cruces por arista", Algorithmica , 49 (1): 1–11, doi :10.1007/s00453-007-0010-x, hdl : 1874/17980 , MR  2344391, S2CID  8174422.