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 .

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

CONJUNTO INDEPENDIENTE( , , )${\estilo de visualización G}$${\estilo de visualización w}$${\displaystyle \épsilon}$
    Elija un vértice arbitrario 
    y encuentre los niveles de búsqueda en amplitud para rooteado en :${\estilo de visualización r}$
    ${\displaystyle k=1/\épsilon}$${\estilo de visualización G}$${\estilo de visualización 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 ,}$${\estilo de visualización G}$${\displaystyle V_{\ell}}$

    para  
       calcular , el conjunto independiente de peso máximo de${\displaystyle i=1,2,\lpuntos}$${\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 }}$

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 }}$${\estilo de visualización k}$${\estilo de visualización k}$