We study the Cyclic Min-Max Sitting Arrangement (CMMSA) problem on signed graphs, which seeks to place vertices around a cycle so that the maximum number of conflicts experienced by any single vertex is minimized. A conflict occurs when a negatively connected vertex lies on a shortest path between a vertex and one of its positively connected neighbors. We show that CMMSA is NP-hard. We address this problem with two exact mathematical models designed for commercial solvers and with a tailored Basic Variable Neighborhood Search (BVNS) that combines a greedy constructive start, informed shaking strategies, fast objective evaluation, and a fairness-oriented tie-breaking rule. Our evaluation covers 1,208 instances including synthetic families, real social networks, and engineered graphs adapted from the Harwell-Boeing collection. Under standard time budgets, the proposed method outperforms commercial solvers and a state-of-the-art baseline adapted to this objective, delivering the best results in 266 of 269 benchmarks and reaching optimal or zero-conflict solutions in 153 cases. These findings establish CMMSA as a relevant min-max variant within cyclic graph layout problems and provide models and datasets that enable reproducible comparison and future research.
- Marcos Robles 1
- Sergio Cavero 1
- Eduardo G. Pardo 1,*
- Universidad Rey Juan Carlos — Calle Tulipán s/n, Móstoles, 28933, Madrid, Spain
*Corresponding author.
- Repository Structure
- Abstract
- Authors
- Datasets
- Code Execution
- Requirements
- Results
- License
- Funding
- Citation
- Acknowledgments
.
├── instances/ # Problem instances
├── results/ # Experimental results
├── code/ # Compiled artifacts
├── LICENSE # License file
└── README.md # This file
The repository contains 269 instances used in the experimental evaluation, categorized in different datasets inside the Instances folder. These include synthetic families, real social networks, and engineered graphs adapted from the Harwell-Boeing collection organizied in subsets accorcing to their size: small (45), medium (90), big (90) and huge (44).
Each instance is encoded as a plain text file representing a graph:
- The first line contains the number of vertices
nand edgesm. - Each subsequent line contains a triplet of integers
u v wrepresenting an edge between vertexuand vertexvwith a weightw, that is either 1 or -1. - Vertices are indexed from 1 to n.
Example:
vertices: 10 edges: 9
2 3 -1
4 9 -1
6 1 -1
6 2 1
6 8 -1
6 10 1
8 4 1
8 7 -1
10 5 -1
Note that the most recent instances have a slightly different header, for example:
# This is an adaptation of one of the original Harwell-Boeing instances
24 68
1 6 1
1 7 1
1 13 1
...
Execution of the program can be done via the command line. The instances that will be used for the execution must be in a folder called "Instances" or a subfolder, and the path must be given by args. Example: Execute default experiment for all the instances.
java -jar BVNS_CMMSA.jar experiment -i "../Instances/" -l "severe" -sExample: Execute default experiment for the small instances only.
java -jar BVNS_CMMSA.jar experiment -i "../Instances/small/" -l "severe" -sNote that the Instances folder is capitalized, this is important for the code to properly handle strings.
- Java 11 or higher
- Minimum 4GB RAM recommended for large instances
Experimental results are stored in a CSV file after execution. Each result file includes:
- Algorithm ID, which is the same for all rows in the given jar
- Filename
- CMinMax O.F.
- T. CPU (s)
- TimeToBest (s)
- CMinSA Objective Function
- Iterations
This project is licensed under the MIT License - see the LICENSE file for details.
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED.
Alternative licenses: If you require a different license for commercial or academic use, please contact the corresponding author.
This research was supported by:
- Grant Name/Number: [Funding Agency Name] - Project Title (Grant #XXXXX)
- Grant Name/Number: [Second Funding Source] - Project Title (Grant #YYYYY)
- Universidad Rey Juan Carlos - Internal Research Funding Program
The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.
If you use this work in your research, please cite our paper:
@article{Robles2024,
title={Exact and heuristic methods for the Min-Max Sitting Arrangement Problem in the Cycle},
author={Robles, Marcos and Cavero, Sergio and Pardo, Eduardo G.},
journal={Journal Name},
volume={XX},
number={X},
pages={XXX--XXX},
year={20XX},
publisher={Publisher Name},
doi={XXXXXXX}
}Robles, M., Cavero, S., & Pardo, E. G. (20XX). Exact and heuristic methods for the Min-Max Sitting Arrangement Problem in the Cycle. Journal Name, XX(X), XXX-XXX. https://doi.org/XXXXXXX
M. Robles, S. Cavero, and E. G. Pardo, "Exact and heuristic methods for the Min-Max Sitting Arrangement Problem in the Cycle," Journal Name, vol. XX, no. X, pp. XXX-XXX, 20XX, doi: XXXXXXX.
We would like to thank:
- The reviewers for their valuable feedback and suggestions
- GRAFO research group for providing computational resources
- Contributors who helped improve this work