Fixed-Parameter & Distributed Algorithms

from collections import defaultdict

# ── BOUNDED SEARCH-TREE: O(2^k * V) ──────────────────────────────────
def vertex_cover_fpt(adj, k):
    """
    FPT algorithm for k-Vertex Cover.
    adj: adjacency dict {u: set of neighbours}.
    k:   cover size budget.
    Returns a vertex cover of size <= k, or None if impossible.
    Time: O(2^k * V) — FPT in k.

    Key insight: for any edge (u,v), at least one endpoint must be in cover.
    Branch on which one: try u, or try v. Depth <= k, branching factor 2.
    """
    # Find any uncovered edge
    for u in adj:
        for v in adj[u]:
            if v > u:   # avoid duplicate edges
                # Must include u or v; try both
                for chosen in [u, v]:
                    # Tentatively add 'chosen' to cover
                    removed_edges = {}
                    new_adj = {x: set(adj[x]) for x in adj}  # deep copy
                    # Remove 'chosen' and all its incident edges
                    for neighbour in new_adj[chosen]:
                        new_adj[neighbour].discard(chosen)
                    del new_adj[chosen]

                    result = vertex_cover_fpt(new_adj, k - 1)
                    if result is not None:
                        return result | {chosen}
                return None   # neither worked

    return set()   # no edges left — empty cover suffices


# ── KERNEL: O(k^2) reduction ──────────────────────────────────────────
def kernel_vertex_cover(edges, n_vertices, k):
    """
    Reduce k-Vertex Cover to a kernel of size O(k^2).
    Returns (kernel_edges, kernel_k, forced_cover) or None if infeasible.
    """
    adj    = defaultdict(set)
    forced = set()     # vertices forced into cover (degree > k)

    for u, v in edges:
        adj[u].add(v)
        adj[v].add(u)

    remaining_k = k

    # Step 1: Force high-degree vertices
    changed = True
    while changed:
        changed = False
        for v in list(adj.keys()):
            if len(adj[v]) > remaining_k:
                forced.add(v)
                for u in list(adj[v]):
                    adj[u].discard(v)
                    if not adj[u]: del adj[u]
                del adj[v]
                remaining_k -= 1
                changed = True
                if remaining_k < 0:
                    return None   # infeasible

    # Step 2: Count remaining edges
    kernel_edges = [(u,v) for u in adj for v in adj[u] if v > u]
    if len(kernel_edges) > remaining_k * remaining_k:
        return None   # more edges than k^2 → impossible

    # Step 3: Remove isolated vertices (already done by adj cleanup)
    # kernel has <= 2k^2 vertices
    return kernel_edges, remaining_k, forced


def solve_vertex_cover(edges, n_vertices, k):
    """
    Full FPT pipeline: kernelize, then bounded search-tree on kernel.
    Overall: O(VE + 2^k * k^2).
    """
    result = kernel_vertex_cover(edges, n_vertices, k)
    if result is None:
        return None   # infeasible
    kernel_edges, k_remaining, forced = result

    # Build adj for kernel
    adj = defaultdict(set)
    for u, v in kernel_edges:
        adj[u].add(v); adj[v].add(u)

    kernel_solution = vertex_cover_fpt(adj, k_remaining)
    if kernel_solution is None:
        return None

    return forced | kernel_solution

from collections import defaultdict, deque

# ── SYNCHRONOUS BFS TREE (simulation) ────────────────────────────────
def sync_bfs_tree(graph, root):
    """
    Synchronous distributed BFS spanning tree.
    Simulates round-by-round execution.
    graph: dict {u: list of neighbours}.
    Returns (parent, rounds, message_count).

    Round r: all nodes with dist==r-1 send "search" to all neighbours.
    A node records first sender as parent.

    Messages: O(|E|) — each directed edge used at most once.
    Rounds: O(diameter).
    Termination: convergecast from leaves to root.
    """
    parent  = {root: None}   # root is its own parent (sentinel)
    dist    = {root: 0}
    round_n = 0
    messages_sent = 0

    # Queue of (sender, receiver) messages to deliver this round
    frontier = [root]

    while frontier:
        round_n += 1
        new_frontier = []
        for u in frontier:
            for v in graph[u]:
                messages_sent += 1               # message sent
                if v not in parent:              # first search arrival
                    parent[v] = u
                    dist[v]   = dist[u] + 1
                    new_frontier.append(v)
        frontier = new_frontier

    return parent, round_n, messages_sent


# ── LEADER ELECTION ON CLIQUE (with UIDs) ────────────────────────────
def leader_election_clique(uids):
    """
    Clique leader election with UIDs.
    1 round: all broadcast UIDs; max UID wins.
    n messages (each of n nodes sends 1 broadcast = n-1 point-to-point).
    Returns (leader_uid, rounds, messages).
    """
    n = len(uids)
    # Round 1: all nodes broadcast their UID
    received = {uid: set(uids) - {uid} for uid in uids}   # each receives all others
    messages = n * (n - 1)   # n-1 messages per node

    # Elect: max UID
    leader = max(uids)
    return leader, 1, messages


# ── LUBY'S DISTRIBUTED MIS (simulation) ──────────────────────────────
import random

def luby_mis(graph):
    """
    Luby's randomised distributed MIS algorithm.
    graph: dict {u: set of neighbours}.
    Returns (MIS set, expected rounds).
    O(log n) rounds expected. Each round: random ID, compare with neighbours.
    """
    active = set(graph.keys())
    mis    = set()
    rounds = 0
    n      = len(active)

    while active:
        rounds += 1
        ids    = {v: random.randint(1, n**5) for v in active}
        local_max = set()

        # Each node checks if it has the maximum ID among active neighbours
        for v in active:
            active_nbrs = {u for u in graph[v] if u in active}
            if all(ids[v] > ids[u] for u in active_nbrs):
                local_max.add(v)

        # Add local maxima to MIS; remove them and their neighbours
        to_remove = set()
        for v in local_max:
            mis.add(v)
            to_remove.add(v)
            to_remove |= {u for u in graph[v] if u in active}

        active -= to_remove

    return mis, rounds


# ── CONVERGECAST: aggregate from leaves to root ───────────────────────
def convergecast_count(parent, root):
    """
    Convergecast: each non-root sends its subtree count to parent.
    Used for termination detection and computing aggregate functions.
    Returns total node count (verifies = n).
    O(V) messages, O(diameter) rounds.
    """
    children = defaultdict(list)
    for v, p in parent.items():
        if p is not None:
            children[p].append(v)

    count = {}
    # Process in reverse BFS order (leaves first)
    queue = deque()
    in_degree = {v: len(children[v]) for v in parent}
    for v in parent:
        if not children[v]:   # leaf
            queue.append(v)
            count[v] = 1

    while queue:
        v = queue.popleft()
        p = parent[v]
        if p is not None:
            count[p] = count.get(p, 1) + count[v]
            in_degree[p] -= 1
            if in_degree[p] == 0:
                queue.append(p)

    return count.get(root, 1)

def ring_leader_naive(uids):
    """
    Naive ring leader election: each UID travels the full ring clockwise.
    Every node receives all n UIDs and elects the maximum.
    O(n^2) messages: each of n UIDs travels n hops.
    O(n) rounds.
    Returns (leader, rounds, messages).
    """
    n = len(uids)
    # Simulate: each UID travels around the ring
    # Message i is UID of node i, travels n hops
    messages = n * n    # n UIDs, each n hops
    rounds   = n        # after n rounds, each UID completes circuit
    leader   = max(uids)
    return leader, rounds, messages


def ring_leader_hirschberg_sinclair(uids):
    """
    Hirschberg-Sinclair: O(n log n) messages.
    Phase r: each surviving node probes distance 2^r in both directions.
    A node survives phase r if its UID is the max in a 2^(r+1)+1 neighbourhood.
    At most n/2^r nodes survive each phase => total messages O(n log n).
    Returns (leader, phases, messages_estimate).
    """
    n       = len(uids)
    active  = list(range(n))    # indices of active nodes
    messages = 0
    phase    = 0

    while len(active) > 1:
        probe_dist = 2 ** phase
        new_active = []
        for i, idx in enumerate(active):
            # Probe 2^phase hops clockwise and counterclockwise
            # Survives if uid[idx] is max in 2*probe_dist+1 window
            # (simplified simulation)
            window = [uids[active[(i + j) % len(active)]]
                      for j in range(-probe_dist, probe_dist + 1)]
            messages += 4 * probe_dist   # 2 probes * 2 directions
            if uids[idx] == max(window):
                new_active.append(idx)
        active  = new_active
        phase  += 1

    leader = uids[active[0]] if active else max(uids)
    return leader, phase, messages

# Comparison
import random
uids = [random.randint(1, 10000) for _ in range(1000)]
_, _, m_naive = ring_leader_naive(uids)
_, _, m_hs    = ring_leader_hirschberg_sinclair(uids)
print(f"n=1000: naive messages={m_naive:,}, HS messages≈{m_hs:,}")
# naive: 1,000,000  HS: ~40,000 (≈ 4n log n)