Tesis:
Resolución exacta del problema del máximo clique, paralelización y aplicaciones
- Autor: LÓPEZ ANTEQUERA, Álvaro
- Título: Resolución exacta del problema del máximo clique, paralelización y aplicaciones
- Fecha: 2024
- Materia:
- Escuela: E.T.S. DE INGENIEROS INDUSTRIALES
- Departamentos: INGENIERIA ELECTRICA, ELECTRONICA AUTOMATICA Y FISICA APLICADA
- Acceso electrónico: https://oa.upm.es/80781/
- Director/a 1º: SAN SEGUNDO CARRILLO, Pablo
- Resumen: Esta tesis gira en torno al problema del máximo clique (MCP), un problema NP-difícil muy conocido y estudiado de la teoría de grafos. Para un grafo dado, el MCP busca determinar un subgrafo completo de tamaño máximo, esto es, el mayor subgrafo tal que sus vértices están conectados entre sí, todos con todos.
Los mejores algoritmos existentes en la actualidad para la resolución exacta del MCP son del tipo ramificación-y-poda. Este trabajo se inicia con un análisis exhaustivo de las técnicas de vanguardia empleadas por estos algoritmos, y abarcan aspectos como, por ejemplo, la enumeración exhaustiva, el preprocesamiento inicial y la determinación de umbrales superiores para el problema. Como consecuencia de este análisis, se obtiene un primer resultado. En concreto, se observa que las dos técnicas de ramificación más frecuentes empleadas para resolver el MCP de manera exacta, i.e., la ramificación clásica e incremental, enumeran exactamente los mismos subproblemas pero en orden inverso. Automáticamente surge la pregunta de por qué los últimos algoritmos publicados tienen preferencia por la ramificación incremental. Por último, se propone un nuevo algoritmo de ramificación clásica que, a tenor de lo observado, se presupone tan eficiente como el mejor algoritmo existente en la actualidad.
Otra aportación de esta tesis surge tras el estudio de las técnicas de preprocesamiento de los mejores algoritmos para el MCP. En concreto, se propone un nuevo ordenamiento inicial de los vértices, que denominamos DEG-SORT-HYB, y un nuevo algoritmo, bautizado como NEW-SORT. Este último trata de determinar el mejor orden inicial posible de los vértices en función de cada instancia particular.
Sin duda la contribución más importante de esta tesis es el diseño e implementación del algoritmo BBMCSP, que permite resolver el MCP en grafos reales masivos de muchos millones de vértices. En las pruebas realizadas, BBMCSP resulta ser órdenes de magnitud más rápido que un algoritmo de referencia en este campo. En la actualidad, BBMCSP es un referente para la comunidad científica; prueba de ello es que de este trabajo se han derivado otras publicaciones tanto teóricas como aplicadas. Como trabajo complementario al anterior, también se presenta un algoritmo paralelo orientado a grafos masivos, denominado BBMCPara, que ejecuta una versión modificada de BBMCSP en cada hilo.
En la parte final de esta tesis se exploran aplicaciones prácticas de estos algoritmos en el ámbito de la localización global y del registro de imágenes. Esta investigación más aplicada incluye el estudio de posibles adaptaciones, para estos problemas reales, de algunos de los algoritmos propuestos con anterioridad.
ABSTRACT
This thesis evolves around the maximum clique problem (MCP), a well-known and deeply studied NP-hard problem from graph theory. Given a simple graph, the MCP calls for finding a largest complete subgraph, i.e, a subgraph such that all its vertices are pairwise connected.
Today's best algorithms for the exact solving of the MCP are branch-and-bound algorithms. This work starts with a detailed analysis of the cutting-edge techniques used by these algorithms, such as, e.g., implicit enumeration, preprocessing and upper bounds. As a result of this analysis, a first result is obtained. Specifically, we observe that the two main branching techniques, i.e., classical branching and incremental branching, enumerate exactly the same subproblems, but in reverse order. This immediately raises the question of why the algorithms most recently published prefer incremental branching. Finally, a new classical branching algorithm is proposed that is expected to perform comparable to the best current algorithm (which employs incremental branching).
Another contribution of this thesis is the result of a deep study of the preprocessing techniques used by the most efficient algorithms for the MCP. Specifically, a new initial order of vertices, called DEG-SORT-HYB, and a new adpative procedure, called NEW-SORT, are proposed. The latter procedure attempts to determine the best possible initial order of vertices depending on each specific instance.
Undoubtedly, the most important contribution of this thesis is the design and implementation of the algorithm BBMCSP , which is able to solve real-world massive graphs with many millions of vertices. According to the tests reported, BBMCSP outperforms the previous reference algorithm by many orders of magnitude in some cases. At the time of writing, BBMCSP is a reference for the computer science community in this field. The proof of this is that many publications have appeared after the algorithm was first published, both theoretical and applied.
In addition to the research mentioned above, this thesis also includes a new parallel algorithm called BBMCPara, which runs a customized variant of BBMCSP in each thread.
In the final part of this dissertation, practical applications are explored in the scope of global localization and image registration. This applied research includes the customization of some of the MCP algorithms for the specific real problems studied.