De ancho doble

El ancho gemelo de un grafo no dirigido es un número natural asociado con el grafo, que se utiliza para estudiar la complejidad parametrizada de los algoritmos de grafos . Intuitivamente, mide cuán similar es el grafo a un cografo , un tipo de grafo 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 se requiere que los vértices sean gemelos, pero tienen conjuntos de vecinos casi iguales.

Definición

El ancho gemelo se define para grafos simples no dirigidos finitos. Estos tienen un conjunto finito de vértices y un conjunto de aristas que son pares de vértices no ordenados. El vecindario abierto de cualquier vértice es el conjunto de otros vértices con los que está emparejado en las aristas del grafo; el vecindario cerrado se forma a partir del vecindario abierto al incluir el propio vértice. Dos vértices son gemelos verdaderos cuando tienen el mismo vecindario cerrado y gemelos falsos cuando tienen el mismo vecindario abierto; de manera más general, tanto los gemelos verdaderos como los gemelos falsos pueden llamarse gemelos, sin calificación. ^[1]

Los cografos tienen muchas definiciones equivalentes, ^[2] pero una de ellas es que son los grafos que se pueden reducir a un único vértice mediante un proceso de búsqueda repetida de dos vértices gemelos cualesquiera y su fusión en un único vértice. Para un cografo, este proceso de reducción siempre tendrá éxito, sin importar qué elección de gemelos se haga en cada paso. Para un grafo que no es un cografo, siempre se quedará atascado en un subgrafo con más de dos vértices que no tiene gemelos. ^[1]

La definición de twin-width imita este proceso de reducción. Una secuencia de contracción , en este contexto, es una secuencia de pasos, comenzando con el gráfico dado, en la que cada paso reemplaza un par de vértices por un único vértice. Esto produce una secuencia de gráficos, con aristas de color rojo y negro; en el gráfico dado, se supone que todas las aristas son negras. Cuando dos vértices se reemplazan por un único 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; todas las demás aristas están coloreadas en rojo. ^[1]

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

Un grafo denso puede tener un ancho de gemelos acotado; por ejemplo, los cografos incluyen todos los grafos completos . Una variación del ancho de gemelos, el ancho de gemelos disperso , se aplica a familias de grafos en lugar de a grafos individuales. Para una familia de grafos que está cerrada bajo la influencia de subgrafos inducidos y tiene un ancho de gemelos acotado, las siguientes propiedades son equivalentes: ^[3]

• Los gráficos de la familia son dispersos, lo que significa que tienen un número de aristas delimitado 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 subgráfico.
• La familia de todos los subgrafos de grafos en 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 de este tipo tiene un ancho de gemelos disperso y limitado. ^[3]

El concepto de ancho de gráfico se puede generalizar a partir de 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 no ordenados. ^[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 tener un grado acotado. ^[5]

Gráficas de ancho gemelo acotado

Los cografos tienen un ancho de gemelos cero. En el proceso de reducción de los cografos, no habrá aristas rojas: cuando se fusionan dos vértices, sus vecindarios son iguales, por lo que no hay aristas que provengan de solo uno de los dos vecindarios para colorearlas de rojo. En cualquier otro grafo, cualquier secuencia de contracción producirá algunas aristas rojas y el ancho de gemelos será mayor que cero. ^[1]

Los grafos de trayectoria con tres vértices como máximo son cografos, pero cada grafo de trayectoria más grande tiene un ancho gemelo de uno. Para una secuencia de contracción que fusiona repetidamente los dos últimos bordes de la trayectoria, solo el borde incidente al único vértice fusionado será rojo, por lo que se trata de una secuencia 1. Los árboles tienen un ancho gemelo de dos como máximo, y para algunos árboles esto es ajustado. Una secuencia de 2-contracción para cualquier árbol se puede encontrar eligiendo una raíz y luego fusionando repetidamente dos hojas que tienen 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 un ancho gemelo acotado, y se puede encontrar para ellos una secuencia de contracción de ancho acotado en tiempo polinomial:

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

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

Existen grafos de ancho gemelo ilimitado dentro de las siguientes familias de grafos:

• 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 se deduce de un argumento contable: hay más gráficos del tipo dado que gráficos de ancho gemelo acotado. ^[1]

Propiedades

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

Algoritmos

Los grafos con un ancho de gemelos como máximo uno pueden reconocerse en tiempo polinomial . ^[8] Sin embargo, es NP-completo determinar si un grafo dado tiene un ancho de gemelos como máximo cuatro, y NP-duro aproximar el ancho de gemelos con una razón de aproximación mejor que 5/4. Bajo la hipótesis del tiempo exponencial , calcular el ancho de gemelos requiere un tiempo al menos exponencial en grafos de , sobre -vértice. ^[11] En la práctica, es posible calcular el ancho de gemelos de grafos de tamaño moderado utilizando solucionadores SAT . ^[12] Para la mayoría de las familias conocidas de grafos de ancho de gemelos 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 con ella, en muchos casos de manera más eficiente que la que es posible para grafos que no tienen un ancho de gemelos acotado. Como se detalla a continuación, estos incluyen algoritmos parametrizados exactos y algoritmos de aproximación para problemas NP-hard, así como algunos problemas que tienen algoritmos de tiempo polinomial clásicos pero que, no obstante, se pueden acelerar utilizando el supuesto de un ancho de gemelos acotado.

Algoritmos parametrizados

Un problema algorítmico en grafos que tienen un parámetro asociado se denomina manejable con parámetros fijos si tiene un algoritmo que, en grafos 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 se aplica generalmente 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 de gemelos 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 grafos de ancho de gemelos acotado enumeradas anteriormente, para las que 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 grafo arbitrario de ancho de gemelos bajo, cuando no se conoce ninguna otra estructura en el grafo. ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle O(n^{c}\,f(k))}$ ${\displaystyle c}$ ${\displaystyle f}$ ${\displaystyle O(n2^{k})}$

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

• Probar si el grafo dado modela alguna propiedad dada en la lógica de primer orden de grafos . Aquí, tanto el ancho gemelo como la longitud de 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 conjunto dominante para coberturas 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 el conjunto independiente, el conjunto dominante y problemas relacionados se puede reducir a exponencial en el tamaño del conjunto independiente o dominante, y para el isomorfismo de subgrafos 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értices, para un grafo de -vértices con una -secuencia dada , es , mediante un algoritmo de programación dinámica que considera pequeños subgrafos conectados de los grafos rojos en la dirección hacia adelante de la secuencia de contracción. Estos límites de tiempo son óptimos, hasta factores logarítmicos en el exponente, bajo 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 ordenamiento, la verificación de modelos todavía es manejable con parámetros fijos para familias de gráficos hereditarios de ancho gemelo acotado, pero no (bajo supuestos teóricos de complejidad estándar) para familias hereditarias de ancho gemelo ilimitado. ^[13] ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle O(k^{2}d^{2k}n)}$
• Colorear grafos de ancho gemelo acotado, usando un número de colores que está acotado por una función de su ancho gemelo y del tamaño de su clique más grande . Por ejemplo, los grafos sin triángulos de ancho gemelo pueden ser coloreados mediante un algoritmo de coloración voraz que colorea los vértices en el orden inverso al que fueron contraídos. ^[6] Este resultado muestra que los grafos de ancho gemelo acotado están acotados por χ . ^{[6] [14]} Para familias de grafos 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 pueden ordenarse linealmente de tal manera que cada vértice pueda alcanzar como máximo 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 de gemelos también se ha aplicado en algoritmos de aproximación . En particular, en los grafos de ancho de gemelos acotado, es posible encontrar una aproximación al conjunto dominante mínimo con una razón de aproximación acotada . Esto contrasta con los grafos más generales, para los cuales es NP-difícil obtener una razón de aproximación que sea mejor que la logarítmica. ^[6]

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

Referencias

1. Bonnet, Édouard; Kim, Eun Jung ; Thomassé, Stéphan; Watrigant, Rémi (2022), "Ancho gemelo I: verificació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 Cograph", Sistema de información sobre inclusiones de clases de grafos
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 Mendez, Patrice Ossona; Simon, Pierre; Thomassé, Stéphan; Torunczyk, Szymon (2022), "Twin-width IV: gráficos y matrices ordenados", en Leonardi, Stefano; Gupta, Anupam (eds.), STOC '22: 54.º Simposio anual ACM SIGACT sobre teoría de la computación, Roma, Italia, 20-24 de junio de 2022 , Association for Computing Machinery, págs. 924-937, arXiv : 2102.03117 , doi : 10.1145/3519935.3520037, ISBN 978-1-4503-9264-8, Número de identificación del sujeto  235743245
5. Bonnet, Édouard; Kim, Eun Jung ; Reinald, Amadeus; 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 2022 sobre algoritmos discretos, SODA 2022, Conferencia virtual / Alexandria, VA, EE. UU., 9 al 12 de enero de 2022 , Society for Industrial and Applied Mathematics, págs. 1036–1056, arXiv : 2111.00282 , doi :10.1137/1.9781611977073.45, ISBN 978-1-61197-707-3, Número de identificación del sujeto  240354166
6. Bonnet, Édouard; Geniet, Colin; Kim, Eun Jung ; Thomassé, Stéphan; Watrigant, Rémi (2021), "Twin-width III: Max independent set, min dominating set, and coloring", en Bansal, Nikhil; Merelli, Emanuela; Worrell, James (eds.), 48.º Coloquio Internacional sobre Autómatas, Lenguajes y Programación, ICALP 2021, 12-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, Número de identificación del sujeto  235736798
7. Dujmović, Vida ; Eppstein, David ; Hickingbotham, Robert; Morin, 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 en el ancho gemelo de los gráficos de productos", Matemáticas discretas y ciencias de la computación 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, Número de identificación del sujeto  245218775
12. Schidler, André; Szeider, Stefan (2022), "Un enfoque SAT para el ancho doble", en Phillips, Cynthia A .; Speckmann, Bettina (eds.), Actas del Simposio sobre Ingeniería de Algoritmos y Experimentos, ALENEX 2022, Alexandria, VA, EE. UU., 9 y 10 de enero de 2022 , Society for Industrial and Applied Mathematics, págs. 67–77, arXiv : 2110.06146 , doi :10.1137/1.9781611977042.6, ISBN 978-1-61197-704-2, Número de identificación del sujeto  238634418
13. Simon, Pierre; Toruńczyk, Szymon (2021), Gráficos ordenados de ancho gemelo acotado , arXiv : 2102.06881
14. Pilipczuk, Marek; Sokołowski, Michał (2023), "Los grafos de ancho gemelo acotado son cuasi-polinomialmente acotados", Journal of Combinatorial Theory, Serie B , 161 : 382–406, arXiv : 2202.07608 , doi :10.1016/j.jctb.2023.02.006, MR  4568111, S2CID  247170805 ${\displaystyle \chi }$
15. Dreier, Jan; Gajarský, Jakub; Jiang, Yiting; Ossona de Mendez, Patrice; Raymond, Jean-Florent (2022), "Números de coloración generalizados y de ancho gemelo", Discrete Mathematics , 345 (3), Paper 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

Lectura adicional

• Ahn, Jungho; Hendrey, Kevin; Kim, Donggyu; Oum, Sang-Il (2022), "Límites para el ancho gemelo de los gráficos", SIAM Journal on Discrete Mathematics , 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, Identificador único de  235669802
• Balabán, Jakub; Hlinený, Petr; Jedelský, Jan (2022), "Ancho gemelo y transducciones de grafos k -mixtos-delgados propios", en Bekos, Michael A.; Kaufmann, Michael (eds.), Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2022, Tübingen, Alemania, 22-24 de junio de 2022, Documentos revisados ​​seleccionados , Lecture Notes in Computer Science, vol. 13453, Springer, págs. 43-55, arXiv : 2202.12536 , doi :10.1007/978-3-031-15914-5_4, ISBN 978-3-031-15913-8
• 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 de banda doble en clases cerradas menores (y más allá)", arXiv : 2202.11858 [math.CO]
• Bonnet, Édouard; Nešetřil, Jaroslav; Ossona de Mendez, Patrice; Siebertz, Sebastian; Thomassé, Stephan (agosto de 2023), "Ancho gemelo y permutaciones", 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, ISBN 978-1-4503-9351-5
• 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
• Jacob, Hugo; Pilipczuk, Marcin (2022), "Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs", en Bekos, Michael A.; Kaufmann, Michael (eds.), Graph-Theoretic Concepts in Computer Science – 48th International Workshop, WG 2022, Tübingen, Alemania, 22-24 de junio de 2022, Documentos revisados ​​seleccionados , Lecture Notes in Computer Science, vol. 13453, Springer, págs. 287-299, arXiv : 2201.09749 , doi :10.1007/978-3-031-15914-5_21, ISBN 978-3-031-15913-8
• 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-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, Número de identificación del sujeto  239009596
• Przybyszewski, Wojciech (2022), Densidad de VC y descomposición de celdas abstractas para la relación de aristas 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