Jun 2026· arXiv.org· Vol abs/2606.30298· 0 citations· 46 references
Computer Science
TL;DR
Four mixed-integer linear programming formulations are proposed, including a compact flow-based model and a representatives model, and corresponding solution methods are designed, and the polytopes associated with the linear relaxation of the proposed formulations are compared.
Abstract
A vertex coloring of a graph is convex if the vertices of each color induce a connected subgraph. In the convex recoloring problem (CR), the goal is to find a convex coloring while minimizing the weight of recolored vertices, i.e., vertices assigned a color different from their original one. This problem was originally motivated by the study of phylogenetic trees in bioinformatics and is NP-hard even on paths. Most existing research focuses on trees, with only limited results available for general graphs. We advance the state of the art by developing exact solution methods for CR on general graphs. In particular, we propose four mixed-integer linear programming formulations, including a compact flow-based model and a representatives model, and design corresponding solution methods. We compare the polytopes associated with the linear relaxation of the proposed formulations. Computational experiments on benchmark instances and on new synthetic instances show that a branch-and-cut algorithm based on the representatives formulation performs best overall.
Some equity constraints on the coloring classes of a classical coloring of the vertices of a graph give rise to the equitable coloring: the number of vertices colored with each color differs by at most one. The least number of colors for which a graph has such an equitable coloring is called the equitable chromatic number. In this paper a new integer programming model is introduced based on a stable set formulation for the decision version of the Equitable Coloring Problem. This new formulation is integrated into two Binary Search-like algorithms, the efficiency of which we have tested on thirty-two instances from literature. The numerical results show that this new approach was able to improve the known lower bounds of equitable chromatic number for two thirds of the tested instances and found the equitable coloring number for two instances.
History: Accepted by Andrea Lodi, Design & Analysis of Algorithms–Discrete.
Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1294 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2025.1294 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
E. F. Olariu, C. Frăsinaru· INFORMS journal on computing· 0 citations
A graph is outer k-planar if it admits a straight-line drawing in which all vertices lie on a circle and every edge is crossed by at most k other edges. We study the parameterized complexity of a broad collection of graph problems on outer k-planar graphs, with k as the parameter. Many graph problems are known to be XALP-hard when parameterized by treewidth or outerplanarity, and XNLP-hard when parameterized by pathwidth. We show that only a few such problems, including Binary CSP and Scattered Set, remain intractable on outer k-planar graphs, whereas a large class of the others become fixed-parameter tractable in this setting, assuming that an outer k-planar drawing of the input graph is given. These include List Coloring, Capacitated Dominating Set, Capacitated Vertex Cover, Target Outdegree Orientation, and Target Set Selection, among others. In addition to the algorithmic and complexity results, we establish several structural results. We show that outer k-planar graphs have mim-width at most k+2, that graphs of cut-width at most k are outer 2k-planar, and that graphs of feedback edge set number at most k are outer 6k-planar. We also show that many graph parameters are incomparable with outer k-planarity, thereby clarifying its position within the graph parameter hierarchy.
This paper addresses the minimum linear arrangement problem, a classical graph layout problem in which the objective is to minimize the sum of absolute differences between the labels assigned to adjacent vertices in undirected graphs. The paper introduces small boundary (SB(k)), a family of linear-time greedy heuristics that guide vertex labeling through a prioritization scheme based on the structure of labeled and k levels of unlabeled vertex neighborhoods. An extensive experimental evaluation on 26 large-scale real-world graphs demonstrates that the proposed heuristic with k=2 consistently outperforms 19 established low-cost graph-theoretic reordering algorithms, including the leading constructive method used within a high-performing metaheuristic algorithm for the problem. Additionally, the SB(2) heuristic outperforms this high-performing metaheuristic algorithm while requiring up to 800 times less computational effort. The paper further shows that integrating SB(2) as the initialization procedure within this metaheuristic yields improved solution quality, highlighting its effectiveness as both a standalone heuristic and a high-quality initializer. Overall, the proposed approach provides a fast, scalable, and practical solution for tackling MinLA on large-scale graphs.
S. de Oliveira, A. A. de Abreu· Journal of Heuristics· 0 citations
This paper generalises the existing PTAS for complete graphs from a fixed to an arbitrary number of intervals and disprove an existing conjecture, which states that every instance of BIA admits a solution satisfying at least three quarters of all edges.
∗. PeterBlohm, ∗. FlorianChen, A. Gionis et al.· 0 citations
