📌Algorithm 1

Algorithm 1: Selection of the Blue Cluster

Algorithm 1 is designed to identify a k-cluster within a block Directed Acyclic Graph (DAG) through a methodological and strategic approach. The algorithm is notable for using a greedy strategy to select the optimal cluster, yielding a set known as BLUE_k(G). This process is meticulously outlined as follows:

Initially, the algorithm addresses the Directed Acyclic Graph (DAG) G. It embarks on a recursive calculation to determine the past set of each tip within G. This recursive analysis facilitates the identification of a k-cluster corresponding to each tip. The algorithm employs a greedy strategy to select the cluster with the largest size among the resulting clusters.

Subsequent to this selection, the algorithm endeavours to augment the chosen set. It incorporates any block whose anticone—the set of blocks not reachable from the selected block—is deemed adequately small relative to the existing set. This decision-making process is inherently intuitive, wherein the DAG adopts the attributes of its most significant tip, denoted as B_max. Here, the significance of a block is quantified by the number of blue blocks in its historical lineage, formulated as score(B) = |BLUE_k(past(B))|.

To maintain the integrity of the k-cluster, blocks within the anticone of B_max are strategically colored. This process establishes a chain-selection rule, where B_max is positioned as the chain tip. Each block in the chain, identified by its highest-scoring predecessor, contributes to the formation of a sequential chain, Chn(G) = (genesis = Chn0(G), Chn1(G),..., Chn_h(G)).

This approach mirrors the analytical methods, pertaining to the Maximum k-cluster SubDAG problem, however, rather than directly seeking the maximal k-cluster, the objective shifts towards maximizing it by initiating the process with the tip demonstrating the highest cluster potential. This process involves incorporating blocks from its anticone, thereby serving as a practical approximation to the ideal solution for the Maximum k-cluster SubDAG problem.

In a practical application involving a blockDAG G, the algorithm is employed with a specified parameter k set to 3. The algorithm initiates by selecting the chain in a sequential manner, commencing from the tip with the highest score. This sequential selection process is meticulously conducted, ensuring the inclusion of each predecessor in turn, and resolving any ties through arbitrary decision-making. The introduction of a hypothetical "virtual" block, denoted as V, signifies a block with a past that encompasses the entire current DAG. This block is integrated into the chain to satisfy methodological criteria.

The process of constructing the BLUE_k(G) set begins with an initially empty set. As the algorithm progresses, blocks are methodically added to BLUE_k(G), influenced by their historical relevance or position within the anticone. This recursive procedure is pivotal in building the blue set, adhering to the defined k-cluster criteria and ensuring a comprehensive selection process.

Algorithm 1 - Selection of a Blue Set

Input: G – a block DAG, k – the propagation parameter.

Output: BLUE_k(G) – the dense-set of G.

Function CALC-BLUE(G, k):

Input: G – a block DAG, k – the propagation parameter

Output: BLUEk (G) – the dense-set of G function CALC-BLUE(G, k)

if B == genesis then return {genesis}

for B tips(G) do BLUEk (B)

←CALC-BLUE(past(B), k)

Bmax ← arg max {|BLUEk (B)| : B tips(G)} (and break ties arbitrarily)

BLUEk (G) ← BLUEk (Bmax) ∪ {Bmax}

for B anticone (Bmax) doin some topological ordering

if |anticone (B) ∩ BLUEk (G)| ≤ k then

add B to BLUEk (G)

return BLUEk (G)

Through this algorithm, the selection of the blue set is achieved with precision, embodying a blend of strategic decision-making and rigorous computational logic.