In recent work, we have exploited the Antiblocking Duality (as
introduced by Fulkerson in the 1970s) between the maximum
cut and (fractional) cut-covering problems to develop approximation
algorithms.
Even more recently, we strengthened and extended this theory as well
as the underlying algorithms to a wide class of generalized cuts and
generalized fractional covers.
Problems like Boolean 2-Constraint Satisfaction are included in this
wide class.
These algorithms all obtain fractional covers by repeated sampling
from a distribution obtained via semidefinite programming (SDP),
following the framework of the seminal work of Goemans and Williamson.
We now explore the practical performance of this family of algorithms,
experimentally studying the behavior of the approximation ratio with
respect to the samples taken and the quality of the SDP solution, as
well as other aspects of theoretical and practical interest.

We study the colorful components framework, historically motivated by comparative genomics in bioinformatics. From a graph-theoretic perspective, we aim to partition a vertex-colored graph into colorful components, namely, connected subgraphs whose vertices have different colors from others in the same component. We address this problem with three different objectives, according to which we: (i) minimize the number of removed edges (MOP problem); (ii) minimize the number of colorful components (MCC problem); or (iii) maximize the number of edges in the transitive closure of the output graph (MEC problem).

In social networks, where nodes represent individuals and edges represent connections (e.g., friendships, interactions), all three problems can be used to determine the most influential connections linking distinct (colorful) and cohesive (connected) communities. By guaranteeing the colorfulness of the communities through the removal of specific edges, as in the MOP problem, a social network aims to mitigate the risk of echo chambers, where users predominantly interact with similar individuals. Maximizing the number of edges in the transitive closure in the MEC problem means promoting the propagation of information through the community, ensuring that a node can be reached by others through a sequence of edge. Instead, by minimizing the number of colorful components, the MCC problem helps prevent the isolation of users within small disconnected groups.
When considering cyberspace networks of devices with various types of connections (e.g., permissions, data flow), identifying a subset of edges to remove while ensuring that the network remains in connected colorful components helps optimize the network's resilience to cyber threats.

We formulate MOP, MEC, and MCC problems as integer nonlinear problems. We linearize these formulations and enhance them with valid inequalities. Furthermore, we provide bounds on the maximum number of colorful components at optimality and exploit them to reduce the size of the models. The formulations are computationally evaluated to demonstrate the efficiency of the proposed approaches.