Conceptual clique sampling frameworks to design solution algorithms for the Edge Clique Cover Problem

Programa de Engenharia de Sistemas e Computaç˜ao, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil

^* Corresponding author: abiliolucena@cos.ufrj.br

Received: 14 June 2024
Accepted: 18 December 2024

Abstract

Given a graph G = (V, E), the Edge Clique Cover Problem (ECCP) asks for a minimum number of cliques so that every edge e ∈ E belongs to at least one of the subgraphs induced by the selected cliques. Rather than fine tuned ECCP algorithms, exact or heuristic, we investigate conceptual frameworks for designing them. In particular we focus on frameworks that are based on the formulation of ECCP as a Set Covering Problem (SCP). This formulation typically contains an exponential number of variables that are in a one-to-one relation with the distinct maximal cliques of G. Our frameworks firstly generate reduced SCP formulations that contain a conveniently small number of variables and then solve them to obtain feasible solutions to ECCP. Variables for these formulations are selected via two distinct clique sampling criteria. One of them relies on random considerations for selecting the cliques (variables) while the other is based on Linear Programming reduced costs. The latter one, in particular, is further refined here into a procedure that implements local search within a column generation environment and is straightforward to adapt to numerous other problems.