Doble ancho

El ancho gemelo de un gráfico no dirigido es un número natural asociado con el gráfico, que se utiliza para estudiar la complejidad parametrizada de los algoritmos de gráficos . Intuitivamente, mide qué tan similar es el gráfico a un cografo , un tipo de gráfico que se puede reducir a un solo vértice fusionando repetidamente gemelos , vértices que tienen los mismos vecinos . El ancho gemelo se define a partir de una secuencia de fusiones repetidas donde no es necesario que los vértices sean gemelos, pero tienen conjuntos de vecinos casi iguales.

Definición

El ancho gemelo se define para gráficos no dirigidos simples finitos. Estos tienen un conjunto finito de vértices y un conjunto de aristas que son pares de vértices desordenados . La vecindad abierta de cualquier vértice es el conjunto de otros vértices con los que está emparejado en los bordes del gráfico; la vecindad cerrada se forma a partir de la vecindad abierta incluyendo el propio vértice. Dos vértices son verdaderos gemelos cuando tienen la misma vecindad cerrada y falsos gemelos cuando tienen la misma vecindad abierta; De manera más general, tanto los gemelos verdaderos como los falsos gemelos pueden ser llamados gemelos, sin ninguna calificación. ^[1]

Los cografos tienen muchas definiciones equivalentes, ^[2] pero una de ellas es que son gráficos que se pueden reducir a un solo vértice mediante un proceso de encontrar repetidamente dos vértices gemelos cualesquiera y fusionarlos en un solo vértice. Para un cografo, este proceso de reducción siempre tendrá éxito, sin importar qué gemelos se elijan fusionar en cada paso. Para un gráfico que no es un cografo, siempre quedará atrapado en un subgrafo con más de dos vértices que no tiene gemelos. ^[1]

La definición de ancho gemelo imita este proceso de reducción. Una secuencia de contracción , en este contexto, es una secuencia de pasos, que comienza con el gráfico dado, en la que cada paso reemplaza un par de vértices por un solo vértice. Esto produce una secuencia de gráficos, con bordes coloreados en rojo y negro; En el gráfico dado, se supone que todos los bordes son negros. Cuando dos vértices son reemplazados por un solo vértice, la vecindad del nuevo vértice es la unión de las vecindades de los vértices reemplazados. En esta nueva vecindad, una arista que proviene de aristas negras en las vecindades de ambos vértices permanece negra; todos los demás bordes son de color rojo. ^[1]

Una secuencia de contracción se llama secuencia -si, a lo largo de la secuencia, cada vértice toca como máximo los bordes rojos. El ancho gemelo de un gráfico es el valor más pequeño de para el cual tiene una secuencia. ^[1] ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d}$

Un gráfico denso aún puede tener un ancho gemelo acotado; por ejemplo, los cografos incluyen todos los gráficos completos . Una variación de ancho gemelo, ancho gemelo disperso , se aplica a familias de gráficos en lugar de a gráficos individuales. Para una familia de gráficos que está cerrada tomando subgrafos inducidos y tiene ancho gemelo acotado, las siguientes propiedades son equivalentes: ^[3]

• Los gráficos de la familia son escasos, lo que significa que tienen un número de aristas delimitadas por una función lineal de su número de vértices.
• Los gráficos de la familia excluyen algún gráfico bipartito completo fijo como subgrafo.
• La familia de todos los subgrafos de gráficos de la familia dada tiene un ancho gemelo acotado.
• La familia tiene una expansión limitada , lo que significa que todos sus menores superficiales son escasos.

Se dice que una familia así tiene un ancho gemelo disperso limitado. ^[3]

El concepto de ancho gemelo se puede generalizar desde gráficos a varias estructuras totalmente ordenadas (incluidos gráficos equipados con un ordenamiento total en sus vértices) y es, en muchos sentidos, más simple para estructuras ordenadas que para gráficos desordenados. ^[4] También es posible formular definiciones equivalentes para otras nociones de ancho de gráfico utilizando secuencias de contracción con requisitos diferentes a los de un grado acotado. ^[5]

Gráficas de ancho gemelo acotado

Los cografos tienen doble ancho cero. En el proceso de reducción de cografos, no habrá aristas rojas: cuando se fusionan dos vértices, sus vecindades son iguales, por lo que no habrá aristas que provengan de solo una de las dos vecindades para colorearse de rojo. En cualquier otro gráfico, cualquier secuencia de contracción producirá algunos bordes rojos y el ancho gemelo será mayor que cero. ^[1]

Los gráficos de ruta con como máximo tres vértices son cografos, pero cada gráfico de ruta más grande tiene uno de doble ancho. Para una secuencia de contracción que fusiona repetidamente los dos últimos bordes del camino, solo el borde incidente en el único vértice fusionado será rojo, por lo que esta es una secuencia de 1. Los árboles tienen un ancho doble como máximo de dos, y para algunos árboles esto es ajustado. Se puede encontrar una secuencia de 2 contracciones para cualquier árbol eligiendo una raíz y luego fusionando repetidamente dos hojas que tengan el mismo padre o, si esto no es posible, fusionando la hoja más profunda con su padre. Los únicos bordes rojos conectan las hojas con sus padres, y cuando hay dos en el mismo padre se pueden fusionar, manteniendo el grado rojo como máximo dos. ^[1]

De manera más general, las siguientes clases de gráficos tienen ancho gemelo acotado, y se puede encontrar una secuencia de contracción de ancho acotado para ellos en tiempo polinómico:

• Cada gráfico de ancho de camarilla acotado , o de ancho de rango acotado , también tiene ancho gemelo acotado. El ancho gemelo es como máximo exponencial en el ancho de camarilla y como máximo doblemente exponencial en el ancho de rango. ^[1] Estos gráficos incluyen, por ejemplo, los gráficos hereditarios de distancia , las potencias de k hojas para valores acotados de k y los gráficos de ancho de árbol acotado .
• Los gráficos de indiferencia (equivalentemente, gráficos de intervalo unitario o gráficos de intervalo propio) tienen ancho gemelo como máximo dos. ^[6]
• Los gráficos de discos unitarios definidos a partir de conjuntos de discos unitarios que cubren cada punto del plano un número acotado de veces tienen un ancho gemelo acotado. Lo mismo ocurre con los gráficos de bolas unitarias en dimensiones superiores. ^[1]
• Los gráficos de permutación que provienen de permutaciones con un patrón de permutación prohibido tienen ancho gemelo acotado. Esto permite aplicar el ancho gemelo a problemas algorítmicos en permutaciones con patrones prohibidos. ^[1]
• Cada familia de gráficos definidos por menores prohibidos tiene un ancho gemelo acotado. Por ejemplo, según el teorema de Wagner , los menores prohibidos para las gráficas planas son las dos gráficas y , por lo que las gráficas planas tienen ancho gemelo acotado. ^[1] ${\displaystyle K_{5}}$ ${\displaystyle K_{3,3}}$
• Cada gráfico de número de pila acotado o número de cola acotado también tiene un ancho gemelo acotado. ^[3] Existen familias de gráficos de ancho gemelo disperso acotado que no tienen un número de pila acotado, pero la pregunta correspondiente al número de cola permanece abierta. ^[7]
• El producto fuerte de dos gráficos cualesquiera de ancho gemelo acotado, uno de los cuales tiene grado acotado, nuevamente tiene ancho gemelo acotado. Esto se puede utilizar para demostrar el ancho gemelo acotado de clases de gráficos que tienen descomposiciones en productos fuertes de caminos y gráficos de ancho de árbol acotado, como los k -gráficos planos . ^[3] Para el producto lexicográfico de gráficos , el ancho gemelo es exactamente el máximo de los anchos de los gráficos de dos factores. ^[8] El ancho gemelo también se comporta bien con varios otros productos de gráficos estándar, pero no con el producto modular de gráficos . ^[9]

En cada familia hereditaria de grafos de ancho gemelo acotado, es posible encontrar una familia de órdenes totales para los vértices de sus gráficas de modo que el orden heredado en un subgrafo inducido sea también un ordenamiento en la familia, y de modo que la familia es pequeño con respecto a estos pedidos. Esto significa que, para un orden total de vértices, el número de gráficos en la familia consistentes con ese orden es como máximo exponencialmente simple en . Por el contrario, cada familia hereditaria de grafos ordenados que es pequeña en este sentido tiene ancho gemelo acotado. ^[4] Originalmente se conjeturó que cada familia hereditaria de gráficos etiquetados que es pequeña, en el sentido de que el número de gráficos es como máximo un factor exponencial único multiplicado por , tiene un ancho gemelo acotado. ^[3] Sin embargo, esta conjetura fue refutada utilizando una familia de subgrafos inducidos de un gráfico de Cayley infinito que son pequeños como gráficos etiquetados pero que no tienen un ancho gemelo acotado. ^[10] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n!}$

Existen gráficos de ancho gemelo ilimitado dentro de las siguientes familias de gráficos:

• Gráficas de grado acotado . ^[1]
• Gráficas de intervalos . ^[1]
• Gráficos de discos unitarios . ^[1]

En cada uno de estos casos, el resultado sigue un argumento de conteo: hay más gráficos del tipo dado que gráficos de ancho gemelo acotado. ^[1]

Propiedades

Si un gráfico tiene un ancho gemelo acotado, entonces es posible encontrar un árbol de contracciones versátil . Esta es una gran familia de secuencias de contracción, todas de algún ancho acotado (mayor), de modo que en cada paso de cada secuencia hay linealmente muchos pares de vértices disjuntos, cada uno de los cuales podría contraerse en el siguiente paso de la secuencia. De esto se deduce que el número de gráficos de ancho gemelo acotado en cualquier conjunto de vértices dados es mayor que por un solo factor exponencial, que los gráficos de ancho gemelo acotado tienen un esquema de etiquetado de adyacencia con solo un número logarítmico de bits por vértice, y que tienen gráficos universales de tamaño polinómico en los que cada gráfico de vértice de ancho gemelo acotado se puede encontrar como un subgrafo inducido . ^[3] ${\displaystyle n}$ ${\displaystyle n!}$ ${\displaystyle n}$

Algoritmos

Las gráficas de ancho gemelo como máximo uno se pueden reconocer en tiempo polinómico . ^[8] Sin embargo, es NP-completo determinar si un gráfico dado tiene un ancho gemelo como máximo cuatro, y NP-difícil aproximar el ancho gemelo con una relación de aproximación mejor que 5/4. Según la hipótesis del tiempo exponencial , calcular el ancho gemelo requiere un tiempo al menos exponencial en gráficos de vértices. ^[11] En la práctica, es posible calcular el ancho gemelo de gráficos de tamaño moderado utilizando solucionadores SAT . ^[12] Para la mayoría de las familias conocidas de gráficos de ancho gemelo acotado, es posible construir una secuencia de contracción de ancho acotado en tiempo polinomial. ^[1] ${\displaystyle n/\log n}$ ${\displaystyle n}$

Una vez que se ha dado o construido una secuencia de contracción, se pueden resolver muchos problemas algorítmicos diferentes usándola, en muchos casos de manera más eficiente de lo que es posible para gráficos que no tienen ancho gemelo acotado. Como se detalla a continuación, estos incluyen algoritmos parametrizados exactos y algoritmos de aproximación para problemas NP-difíciles, así como algunos problemas que tienen algoritmos de tiempo polinómico clásicos pero que, sin embargo, pueden acelerarse utilizando el supuesto de ancho gemelo acotado.

Algoritmos parametrizados

Un problema algorítmico en gráficos que tienen un parámetro asociado se llama tratable de parámetros fijos si tiene un algoritmo que, en gráficos con vértices y valor de parámetro , se ejecuta en el tiempo para alguna función constante y computable . Por ejemplo, un tiempo de ejecución de sería manejable con parámetros fijos en este sentido. Este estilo de análisis generalmente se aplica a problemas que no tienen un algoritmo de tiempo polinomial conocido , porque de lo contrario la manejabilidad con parámetros fijos sería trivial. Se ha demostrado que muchos de estos problemas son manejables con parámetros fijos con ancho gemelo como parámetro, cuando se proporciona una secuencia de contracción de ancho acotado como parte de la entrada. Esto se aplica, en particular, a las familias de gráficos de ancho gemelo acotado enumeradas anteriormente, para las cuales se puede construir una secuencia de contracción de manera eficiente. Sin embargo, no se sabe cómo encontrar una buena secuencia de contracción para un gráfico arbitrario de ancho gemelo bajo, cuando no se conoce ninguna otra estructura en el gráfico. ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle O(n^{c}\,f(k))}$ ${\displaystyle c}$ ${\displaystyle f}$ ${\displaystyle O(n2^{k})}$

Los problemas manejables de parámetros fijos para gráficos de ancho gemelo acotado con secuencias de contracción dadas incluyen:

• Probar si el gráfico dado modela alguna propiedad determinada en la lógica de gráficos de primer orden . Aquí, tanto el ancho gemelo como la longitud de la descripción de la propiedad son parámetros del análisis. Los problemas de este tipo incluyen el isomorfismo de subgrafos para subgrafos de tamaño acotado, y los problemas de cobertura de vértices y conjuntos dominantes para cubiertas o conjuntos dominantes de tamaño acotado. ^[1] La dependencia de estos métodos generales de la longitud de la fórmula lógica que describe la propiedad es tetracional , pero para conjuntos independientes, conjuntos dominantes y problemas relacionados se puede reducir a exponencial en el tamaño del conjunto independiente o dominante, y para el isomorfismo del subgrafo, se puede reducir a factorial en el número de vértices del subgrafo. Por ejemplo, el tiempo para encontrar un conjunto independiente de vértice, para un gráfico de vértice con una secuencia dada, es mediante un algoritmo de programación dinámica que considera pequeños subgrafos conectados de los gráficos rojos en la dirección directa de la secuencia de contracción. Estos límites de tiempo son óptimos, hasta factores logarítmicos en el exponente, según la hipótesis del tiempo exponencial . ^[6] Para una extensión de la lógica de primer orden de los gráficos a gráficos con vértices totalmente ordenados y predicados lógicos que pueden probar este orden, la verificación del modelo aún es manejable con parámetros fijos para familias de gráficos hereditarios de ancho gemelo acotado, pero no (bajo supuestos estándar de teoría de la complejidad) para familias hereditarias de ancho gemelo ilimitado. ^[13] ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle O(k^{2}d^{2k}n)}$
• Colorear gráficos de ancho gemelo acotado, utilizando una cantidad de colores acotados en función de su ancho gemelo y del tamaño de su camarilla más grande . Por ejemplo, los gráficos sin triángulos de ancho gemelo se pueden colorear mediante un algoritmo de coloración codicioso que colorea los vértices en el orden inverso al que se contrajeron. ^[6] Este resultado muestra que las gráficas de ancho gemelo acotado están acotadas por χ . ^{[6] [14]} Para familias de gráficos de ancho gemelo disperso acotado, los números de coloración generalizados están acotados. Aquí, el número de coloración generalizado es como máximo si los vértices se pueden ordenar linealmente de tal manera que cada vértice pueda alcanzar como máximo los vértices anteriores en el ordenamiento, a través de caminos de longitud a través de vértices posteriores en el ordenamiento. ^[15] ${\displaystyle d}$ ${\displaystyle (d+2)}$ ${\displaystyle \operatorname {col} _{r}(G)}$ ${\displaystyle k}$ ${\displaystyle k-1}$ ${\displaystyle r}$

Aceleraciones de algoritmos clásicos.

En gráficos de ancho gemelo acotado, es posible realizar una búsqueda en amplitud , en un gráfico con vértices, en el tiempo , incluso cuando el gráfico es denso y tiene más aristas que este límite de tiempo. ^[6] ${\displaystyle n}$ ${\displaystyle O(n\log n)}$

Algoritmos de aproximación

El ancho gemelo también se ha aplicado en algoritmos de aproximación . En particular, en las gráficas de ancho gemelo acotado, es posible encontrar una aproximación al conjunto mínimo dominante con relación de aproximación acotada . Esto contrasta con los gráficos más generales, para los cuales es NP-difícil obtener una relación de aproximación que sea mejor que la logarítmica. ^[6]

Los problemas de coloración de gráficos y conjuntos independientes máximos se pueden aproximar dentro de una relación de aproximación de , para cada , en tiempo polinómico en gráficos de ancho gemelo acotado. Por el contrario, sin el supuesto de ancho gemelo acotado, es NP-difícil lograr cualquier relación de aproximación de esta forma con . ^[dieciséis] ${\displaystyle n^{\varepsilon }}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle \varepsilon <1}$

Referencias

1. Bonnet, Édouard; Kim, Eun Jung ; Thomassé, Stéphan; Watrigant, Rémi (2022), "Twin-width I: Comprobación del modelo FO manejable", Journal of the ACM , 69 (1): A3:1–A3:46, arXiv : 2004.14789 , doi :10.1145/3486655, MR  4402362
2. "Gráficos de cografos", Sistema de información sobre inclusiones de clases de gráficos
3. Bonnet, Édouard; Geniet, Colin; Kim, Eun Jung ; Thomassé, Stéphan; Watrigant, Rémi (2022), "Twin-width II: clases pequeñas", Teoría combinatoria , 2 (2): P10:1–P10:42, arXiv : 2006.09877 , doi :10.5070/C62257876, MR  4449818
4. Bonnet, Édouard; Giocanti, Ugo; de Méndez, Patrice Ossona; Simón, Pedro; Thomassé, Stéphan; Torunczyk, Szymon (2022), "Twin-width IV: matrices y gráficos ordenados", en Leonardi, Stefano; Gupta, Anupam (eds.), STOC '22: 54.º Simposio anual ACM SIGACT sobre teoría de la informática, Roma, Italia, 20 al 24 de junio de 2022 , Asociación de Maquinaria de Computación, págs. 924–937, arXiv : 2102.03117 , doi : 10.1145/3519935.3520037, S2CID  235743245
5. Capo, Édouard; Kim, Eun Jung ; Reinaldo, Amadeo; Thomassé, Stéphan (2022), "Twin-width VI: la lente de las secuencias de contracción", en Naor, Joseph (Seffi); Buchbinder, Niv (eds.), Actas del Simposio ACM-SIAM de 2022 sobre algoritmos discretos, SODA 2022, Conferencia virtual / Alexandria, VA, EE. UU., 9 al 12 de enero de 2022 , Sociedad de Matemáticas Industriales y Aplicadas, págs. 1056, arXiv : 2111.00282 , doi : 10.1137/1.9781611977073.45, S2CID  240354166
6. Bonnet, Édouard; Geniet, Colin; Kim, Eun Jung ; Thomassé, Stéphan; Watrigant, Rémi (2021), "Ancho gemelo III: conjunto independiente máximo, conjunto dominante mínimo y coloración", en Bansal, Nikhil; Merelli, Emanuela; Worrell, James (eds.), 48.º Coloquio internacional sobre autómatas, lenguajes y programación, ICALP 2021, 12 al 16 de julio de 2021, Glasgow, Escocia (Conferencia virtual) , LIPIcs, vol. 198, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, págs. 35:1–35:20, arXiv : 2007.14161 , doi :10.4230/LIPIcs.ICALP.2021.35, ISBN 9783959771955, S2CID  235736798
7. Dujmović, Vida ; Eppstein, David ; Hickingbotham, Robert; Morín, Pat ; Wood, David R. (agosto de 2021), "El número de pila no está limitado por el número de cola", Combinatorica , 42 (2): 151–164, arXiv : 2011.04195 , doi : 10.1007/s00493-021-4585-7, S2CID  226281691
8. Bonnet, Édouard; Kim, Eun Jung ; Reinaldo, Amadeo; Thomassé, Stéphan; Watrigant, Rémi (2022), "Núcleos polinomiales y de ancho gemelo", Algorithmica , 84 (11): 3300–3337, arXiv : 2107.02882 , doi : 10.1007/s00453-022-00965-5, MR  4500778
9. Pettersson, William; Pettersson, John (junio de 2023), "Límites del ancho gemelo de gráficos de productos", Matemáticas discretas e informática teórica , 25 (1), arXiv : 2202.11556 , doi :10.46298/dmtcs.10091
10. Capo, Édouard; Geniet, Colin; Tessera, Romain; Thomassé, Stéphan (2022), "Grupos de ancho gemelo VII", arXiv : 2204.12330 [math.GR]
11. Bergé, Pierre; Bonnet, Édouard; Déprés, Hugues (2022), "Decidir que el ancho gemelo como máximo 4 es NP completo", en Bojanczyk, Mikolaj; Merelli, Emanuela; Woodruff, David P. (eds.), 49.º Coloquio internacional sobre autómatas, lenguajes y programación, ICALP 2022, 4 al 8 de julio de 2022, París, Francia , LIPIcs, vol. 229, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, págs. 18:1–18:20, arXiv : 2112.08953 , doi :10.4230/LIPIcs.ICALP.2022.18, ISBN 9783959772358, S2CID  245218775
12. Schidler, André; Szeider, Stefan (2022), "Un enfoque SAT de ancho gemelo", en Phillips, Cynthia A .; Speckmann, Bettina (eds.), Actas del Simposio sobre experimentos e ingeniería de algoritmos, ALENEX 2022, Alexandria, VA, EE. UU., 9 al 10 de enero de 2022 , Sociedad de Matemáticas Industriales y Aplicadas, págs. 67–77, arXiv : 2110.06146 , doi :10.1137/1.9781611977042.6, S2CID  238634418
13. Simón, Pedro; Toruńczyk, Szymon (2021), Gráficos ordenados de ancho gemelo acotado , arXiv : 2102.06881
14. Pilipczuk, Marek; Sokołowski, Michał (2023), "Los gráficos de ancho gemelo acotado están acotados cuasi polinomialmente", Journal of Combinatorial Theory, Serie B , 161 : 382–406, arXiv : 2202.07608 , doi : 10.1016/j.jctb.2023.02. 006, SEÑOR  4568111, S2CID  247170805 ${\displaystyle \chi }$
15. Dreier, enero; Gajarský, Jakub; Jiang, Yiting; Ossona de Méndez, Patrice; Raymond, Jean-Florent (2022), "Números de coloración generalizada y de ancho gemelo", Matemáticas discretas , 345 (3), documento 112746, arXiv : 2104.09360 , doi : 10.1016/j.disc.2021.112746, MR  4349879, S2CID  233296212
16. Bergé, Pierre; Bonnet, Édouard; Déprés, Hugues; Watrigant, Rémi (2023), "Aproximación de problemas altamente inaproximables en gráficos de ancho gemelo acotado", en Berenbrink, Petra; Bouyer, Patricia ; Dawar, Anuj; Kanté, Mamadou Moustapha (eds.), 40.º Simposio internacional sobre aspectos teóricos de la informática, STACS 2023, 7 al 9 de marzo de 2023, Hamburgo, Alemania , LIPIcs, vol. 254, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, págs. 10:1–10:15, arXiv : 2207.07708 , doi :10.4230/LIPIcs.STACS.2023.10

Otras lecturas

• Ahn, Jungho; Hendrey, Kevin; Kim, Donggyu; Oum, Sang-Il (2022), "Límites para el ancho gemelo de gráficos", Revista SIAM de Matemáticas Discretas , 36 (3): 2352–2366, arXiv : 2110.03957 , doi : 10.1137/21M1452834, MR  4487903
• Balabán, Jakub; Hlinený, Petr (2021), "El ancho gemelo es lineal en el ancho del poset", en Golovach, Petr A.; Zehavi, Meirav (eds.), 16.º Simposio internacional sobre computación exacta y parametrizada, IPEC 2021, 8 al 10 de septiembre de 2021, Lisboa, Portugal , LIPIcs, vol. 214, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, págs. 6:1–6:13, arXiv : 2106.15337 , doi :10.4230/LIPIcs.IPEC.2021.6, ISBN 9783959772167, S2CID  235669802
• Balabán, Jakub; Hlinený, Petr; Jedelský, Jan (2022), "Ancho gemelo y transducciones de gráficos k -mixtos-delgados adecuados", en Bekos, Michael A.; Kaufmann, Michael (eds.), Conceptos de teoría de grafos en informática - 48.º taller internacional, WG 2022, Tübingen, Alemania, 22 al 24 de junio de 2022, artículos seleccionados revisados , Lecture Notes in Computer Science, vol. 13453, Springer, págs. 43–55, arXiv : 2202.12536 , doi : 10.1007/978-3-031-15914-5_4
• Bonnet, Édouard; Chakraborty, Dibyayan; Kim, Eun Jung ; Kohler, Noleen; Lopes, Raúl; Thomassé, Stéphan (2022), "Twin-Width VIII: Delineación y beneficios para todos", en Dell, Holger; Nederlof, Jesper (eds.), 17.º Simposio internacional sobre computación exacta y parametrizada, IPEC 2022, 7 al 9 de septiembre de 2022, Potsdam, Alemania , LIPIcs, vol. 249, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, págs. 9:1–9:18, arXiv : 2204.00722 , doi :10.4230/LIPIcs.IPEC.2022.9
• Bonnet, Édouard; Déprés, Hugues (2023), "El ancho gemelo puede ser exponencial en el ancho del árbol", Journal of Combinatorial Theory, Serie B , 161 : 1–14, arXiv : 2204.07670 , doi : 10.1016/j.jctb.2023.01.003, MR  4543125
• Bonnet, Édouard; Giocanti, Ugo; de Méndez, Patrice Ossona; Thomassé, Stéphan (2023), "V de ancho gemelo: menores lineales, conteo modular y multiplicación de matrices", en Berenbrink, Petra; Bouyer, Patricia ; Dawar, Anuj; Kanté, Mamadou Moustapha (eds.), 40.º Simposio internacional sobre aspectos teóricos de la informática, STACS 2023, 7 al 9 de marzo de 2023, Hamburgo, Alemania , LIPIcs, vol. 254, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, págs. 15:1–15:16, doi :10.4230/LIPIcs.STACS.2023.15
• Bonnet, Édouard; Kwon, O-joung; Wood, David R. (2022), "Ancho de banda reducido: un fortalecimiento cualitativo del ancho gemelo en clases cerradas menores (y más allá)", arXiv : 2202.11858 [math.CO]
• Bonnet, Édouard; Nešetřil, Jaroslav; Ossona de Méndez, Patrice; Siebertz, Sebastián; Thomassé, Stephan (agosto de 2023), "Twin-width and permutations", Conferencia europea sobre combinatoria, teoría de grafos y aplicaciones (EUROCOMB'23) , Masaryk University Press, págs. 156-162, arXiv : 2102.06880 , doi :10.5817/cz .muni.eurocomb23-022
• Gajarský, Jakub; Pilipczuk, Michal; Przybyszewski, Wojciech; Toruńczyk, Szymon (2022), "Tipos y anchos gemelos", en Bojanczyk, Mikolaj; Merelli, Emanuela; Woodruff, David P. (eds.), 49.º Coloquio internacional sobre autómatas, lenguajes y programación, ICALP 2022, 4 al 8 de julio de 2022, París, Francia , LIPIcs, vol. 229, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, págs. 123:1–123:21, arXiv : 2206.08248 , doi :10.4230/LIPIcs.ICALP.2022.123, ISBN 9783959772358
• Gajarský, Jakub; Pilipczuk, Michal; Toruńczyk, Szymon (2022), "Gráficos estables de ancho gemelo acotado", en Baier, Christel ; Fisman, Dana (eds.), LICS '22: 37.º Simposio anual ACM/IEEE sobre lógica en informática, Haifa, Israel, 2 al 5 de agosto de 2022 , Association for Computing Machinery, págs. 39:1–39:12, arXiv : 2107.03711 , doi : 10.1145/3531130.3533356
• Geniet, Colin; Thomassé, Stéphan (2023), "Lógica de primer orden y ancho gemelo en torneos", en Gørtz, Inge Li; Farach-Colton, Martín ; Puglisi, Simón J.; Herman, Grzegorz (eds.), 31.º Simposio europeo anual sobre algoritmos, ESA 2023, 4 al 6 de septiembre de 2023, Ámsterdam, Países Bajos , LIPIcs, vol. 274, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, págs. 53:1–53:14, arXiv : 2207.07683 , doi :10.4230/LIPICS.ESA.2023.53, S2CID  261345465
• Jacobo, Hugo; Pilipczuk, Marcin (2022), "Ancho gemelo delimitador para gráficos de ancho de árbol acotado, gráficos planos y gráficos bipartitos", en Bekos, Michael A.; Kaufmann, Michael (eds.), Conceptos de teoría de grafos en informática - 48.º taller internacional, WG 2022, Tübingen, Alemania, 22 al 24 de junio de 2022, artículos seleccionados revisados , Lecture Notes in Computer Science, vol. 13453, Springer, págs. 287–299, arXiv : 2201.09749 , doi : 10.1007/978-3-031-15914-5_21
• Pilipczuk, Michal; Sokolowski, Marek; Zych-Pawlewicz, Anna (2022), "Representación compacta para matrices de ancho gemelo acotado", en Berenbrink, Petra; Monmege, Benjamin (eds.), 39.º Simposio internacional sobre aspectos teóricos de la informática, STACS 2022, 15 al 18 de marzo de 2022, Marsella, Francia (Conferencia virtual) , LIPIcs, vol. 219, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, págs. 52:1–52:14, arXiv : 2110.08106 , doi :10.4230/LIPIcs.STACS.2022.52, ISBN 9783959772228, S2CID  239009596
• Przybyszewski, Wojciech (2022), densidad de VC y descomposición de celdas abstractas para la relación de bordes en gráficos de ancho gemelo acotado , arXiv : 2202.04006
• Thomassé, Stéphan (2022), "Un breve recorrido en doble ancho (charla invitada)", en Bojanczyk, Mikolaj; Merelli, Emanuela; Woodruff, David P. (eds.), 49.º Coloquio internacional sobre autómatas, lenguajes y programación, ICALP 2022, 4 al 8 de julio de 2022, París, Francia , LIPIcs, vol. 229, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, págs. 6:1–6:5, doi :10.4230/LIPIcs.ICALP.2022.6, ISBN 9783959772358