Minium set of nodes that satisfy the given number of edges

Question

For example, we have the adjacency list like below. If the desired number of edges is 2, then the sets of nodes that suffice are (1,2), (1,3), (1,4), (2,3) and (3,4). If the desired number of edges is 3, then the sets of nodes that suffice are none. If the desired number of edges is 4, then the sets of nodes that suffice are (1, 2, 4) and (2, 3, 4).

# Sample adjacency list
adjacency_list = {
    1: [2, 3, 4],
    2: [1, 3],
    3: [1, 2, 4],
    4: [1, 3]
}

I am fairly new to graph theory and my search with Google or Chat GPT was not successful. I feel like this could be a DP problem but really don't know what's an efficient way to do it. Any advice would be appreciated.

Answer 1

IIUC, this is a Directed graph problem. If so and if you're tempted to use networkx, try this :

import networkx as nx
from itertools import chain, combinations

G = nx.DiGraph(adjacency_list)

def combs(lst):
    return chain(*map(lambda x: combinations(lst, x), range(1, len(lst)+1)))

def get_nodes(G, nb_edges):
    for c in combs(G.nodes):
        if G.subgraph(c).number_of_edges() == nb_edges:
            yield c

Test/Output :

op_vals = [2, 3, 4]

for v in op_vals:
    print(f"for {v} edges, {list(get_nodes(G, v))} suffice!")
    
# for 2 edges, [(1, 2), (1, 3), (1, 4), (2, 3), (3, 4)] suffice!
# for 3 edges, [] suffice!
# for 4 edges, [(1, 2, 4), (2, 3, 4)] suffice!

A visualization for the sets of nodes (yellow) required for 4 edges (blue) :