The Minimum Vertex Sum Sitting Arrangement on the Cycle: Problem Definition and Empirical Analysis

Abstract

This paper addresses the Cyclic Minimum Vertex Sum Sitting Arrangement (CMinVSSA), a graph layout optimization problem where the vertices of an input signed graph, containing positive and negative edges, must be assigned to those of a cyclic host graph in a one-to-one correspondence. The objective is to minimize the number of vertices that experience any conflict, defined as a situation in which a vertex connected by a negative edge lies on the shortest path to a vertex connected by a positive edge. We analyze the similarities and differences between the CMinVSSA and other variants belonging to the Cyclic Sitting Arrangement family. A comparison of optimal solutions on small instances reveals its unique structural properties, confirming that the CMinVSSA requires a dedicated optimization process. We then analyze different heuristic algorithms for this problem by adapting two state-of-the-art methods from the related literature: a Multi-Armed Bandit (MAB) hyper-heuristic and a Basic Variable Neighborhood Search (BVNS). Experimental results on 30 representative instances of varying size show that the BVNS outperforms the MAB, a result attributed to its flat-landscape navigation mechanisms, which prove effective in the count-based objective landscape of the CMinVSSA, while also highlighting the potential for developing fully problem-specific approaches.

Marcos Robles

Artificial Intelligence Phd Student

Marcos Robles graduated in Software Engineering from the Rey Juan Carlos University in 2022. He is working here as a predoctoral researcher focusing in Graph Layout Problems.

Sergio Cavero

Phd in Artificial Intelligence

Sergio Cavero was born Madrid (Spain) on September 24, 1997. He graduated in Software Engineering from Universidad Politécnica de Madrid in 2019. During his undergraduate studies he made a stay at the University of Bradford (UK). In addition, he was awarded twice with the ‘Beca de Excelencia of the Comunidad de Madrid, and also awarded for the Best Final Degree Project. Later, he completed a Master’s Degree in Artificial Intelligence at the same university (UPM) obtaining awards for Best Academic Record (‘Premio José Cuena’) and Best Master’s Thesis. He academic results lend him be beneficiary of one of the ‘Ayudas Para la Formación de Profesorado Universitario (FPU)’, funded by the Spanish Government. He is currently carrying out his doctoral thesis at the Universidad Rey Juan Carlos, supervised by Professors Abraham Duarte and Eduardo G. Pardo. His main research interests focus on the interface among Computer Science, Artificial Intelligence and Operations Research. Most of his publications deal with the development of metaheuristics procedures for optimization problems modeled by graphs.

Eduardo García Pardo

Full Professor

One of the founders of the investigation group GRAFO, whose main line of research is the development of algorithms to tackle optimization problems, the topic of the researcher’s Doctoral Thesis and which their most notable publications are framed.