The graph burning problem is an NP-hard combinatorial optimization problem that helps quantify the vulnerability of a graph to contagion. This paper introduces a simple farthest-first traversal-based approximation algorithm for this problem over general graphs. We refer to this proposal as the Burning Farthest-First (BFF) algorithm. BFF runs in O(n3) steps and has a tight approximation factor of 3-2/b(G), where b(G) is the size of an optimal solution. The main attribute of BFF is that it has a better approximation factor than the state-of-the-art approximation algorithms for general graphs, which report an approximation factor of 3. Despite being simple, BFF proved practical when tested over some benchmark datasets.

The graph burning problem is an NP-hard combinatorial optimization problem that helps quantify how vulnerable a graph is to contagion. This paper introduces three mathematical formulations of the problem: an integer linear program (ILP) and two constraint satisfaction problems (CSP1 and CSP2). Thanks to off-the-shelf optimization software, these formulations can be solved optimally over arbitrary graphs; this is relevant because the only algorithms designed to date for this problem are approximation algorithms and heuristics, which do not guarantee to find optimal solutions. We empirically compared the proposed formulations using random graphs and off-the-shelf optimization software. The results show that CSP1 and CSP2 tend to reach optimal solutions in less time than the ILP. Therefore, we executed them over some benchmark graphs of order at most 5908. The previously best-known solutions for some of these graphs were improved. We draw some empirical observations from the experimental results. For instance, we find the tendency: the larger the graph’s optimal solution, the more difficult it is to find it. Finally, the resulting set of optimal solutions might be helpful as a benchmark dataset for the performance evaluation of non-exact algorithms.

Multi-domain federations support shared network services. Many orchestrators manage the service’s lifecycle. For the shared VNF Forwarding Graph (VNF-FG) reconfiguration, orchestrators update the graph’s logical information, ensuring a consistent behavior for replicas. Only one work in the literature considers sharing the VNF-FG. However, it offers weak consistency guarantees, without considering the VNF-FG’s non-functional dependencies. In case of a conflict, while updating the VNF-FG, the orchestrators solve consensus. However, this adds latency, undermining the goal of Network Function Virtualization. This paper introduces the first coordination-free multi-domain orchestration algorithm for consistent shared VNF-FG reconfiguration. Unlike the current state of the art, the proposed algorithm skips the coordination phase, offers strong eventual consistency, and supports non-functional dependencies. We present two variants: the preventive, where transient inconsistent states are prevented; the corrective, where intermediary inconsistent states, during the updating process, are tolerated. We prove the correctness of our algorithm and evaluate it. The variants, unlike the state of the art, reconfigure consistently the shared VNF-FGs without solving consensus. They offer stronger guarantees compared to the literature, like allowing orchestrators to reject ongoing reconfigurations without a high impact on performance.

S-boxes are the core nonlinear components of ciphers, providing confusion and diffusion. As a result, cryptanalysts focus on analyzing these components to identify distinguishers and ultimately recover the secret key of the cipher. Although many constructions exist, the search for new S-boxes remains vital as advances in cryptanalysis expose new weaknesses. Evaluating their security is challenging, and the current literature often prioritizes technical depth over clarity for a broader audience. This raises questions that are not always clear, such as how the S-box and its construction affect a cipher’s resilience, how to assess the security of this nonlinear component, and what factors influence its robustness. In this paper, we address these concerns by providing a friendly introduction to the basic principles of S-box security evaluation, structured around four key aspects. First, the importance of the S-box in ensuring block cipher security is discussed. Second, the advantages and disadvantages of three classical S-box construction approaches are outlined. Third, the evaluation of S-boxes through the formal definition of their properties and their associated security implications is presented. Fourth, four S-box evaluation toolkits proposed in the literature are introduced. Finally, open research challenges in S-box design are highlighted.

The SCITEPRESS Digital Library offers online access to all papers presented at INSTICC conferences, as well as a few conferences organized by others.