TD05 - Complexity

Implementation in Python 3 of a program that returns true if and only if {$D$} is a dominant set of size less or equal to {$k$} as shown in the second additional exercise of TD 6. This is the algorithm for verifying a solution to the decision problem of the dominant set. The produced algorithm will be polynomial, which proves that the problem is in {$\mathcal{NP}$}.

Each function you need to complete is followed by tests to verify that the data produced when the function was called is correct.

The graphs are represented as dictionaries and you can use the following Python functions:

• nodes (graph): returns the list of vertices of graph.
• neighbors (graph, x): returns the list of neighboring vertices of x in the graph.

Exercise plan:

• Dominant set is {$\mathcal{NP}$} ;

Optional:

• Greedy algorithm ;

Copy/run this first cell. It helps to load data and utility functions to verify the produced solutions.

# TO RUN
import zlib, base64
exec(zlib.decompress(base64.b64decode(b'eJzNVk1u6zYQXtenmLoLSYhg2HkvL4kBL4qmCLpqF90ZgcGIlM1GJgWKiu0GPlB6jVysQ4oSKVsp3K4aIDI5Px9nhvPDXMktKCIo/vBtKZW2Oy70yG0F0zupXvZAKhD7lroluiykLvjzpDyYlWGXhQ74m9QBj0aU5VBIQldrRcpNvE7mMAL8G4/H9pcyVkImywPQqBZgpVgrAWd/o+6zXlmtBbyJ+dsRcqlAAEeEo2X7/XzUKhva1tKW4smTPRqSl9snxFw3KyuimK6VaM+DUeMT5VVZkINza+sWKRTkmRXV4u2YgpCUoVIhld0yuj7bdtLJvBeVH/OcZxsGXUSACag1L3hFhMZDAMPf3c/E6vwqoGS1hqr8eM94zpnC4FbOIChlraDAvZCsplVqeaXkNGAR9fGXZpVFy2RdsFqdKQLTAzyn2RjyExK4wGBjJnApKqgk2lxpmb18vCOPEqSZ4ynPjIAgXLW69vMbQdM/3nOC3gQnWxgl6zUKwy/ok2DG41eG5JIYyxSD54KIDDJEkMIJNNxsI3nFTUygiGSN+SvYpBd0+8FwVSapfBZxkzHtBfus4XnDcfHtp5NBWXKTSZGI4AqdVzFPJnVZMhUncBXNoytDa5RRMunUcc/+FdroOyssbGqhzLJJW7TPJyAsjEsetROOVDRqT+0Xyiduh64H+FjtwdYau4BpX80fPCFouqBxtNtwzaKkJ8aKi/C/vwQfjT+cwYeefqKnGPVq9vcRgyX2k0db7g3rcUIoXRmrqlWOzbTrApMXdqjiJOlSaD8cS8M6hKzl/uks0gFvebBh/V3VAx401piuEu9TOFzi9IlKCjvG1xuNnvYPTXx5+Ca2qg5bWygdz7hTp6/GIS/mYuEP7yMs49e0Tkxqe/oyRpTk6eQ8THdKNIv7+o1prMv9QH7NdGyRUhhjV8hexok10dKMkY8TI43GPXn/Slk1F52rOttohj1MrBTjYi0Liu36gJ0jfkyhYowurhP4AUgNJc89AupSRXZGyHV3U75pP/g5trJVxf9ki9nMDQq7u51OTyTRoAX+n1CD0dJkbm+8MEfacao3i9nkJrhAzKhg8gTX4hpfwOwaA5yLoZcYX5s7K6K14s819n90OmpyyFWPC8aqnVSrAB6FjWPhHLTojSY+KCbVRu6w1pqBa+sstlnpsskNZpyJOu7XndMwljxL5bTSvdOznVE3RXlSkYpwdPfnfcZKM5niyNY7UGmnkJl8QhPXmWAOTRPfu0o/swerpzUJzh4O+DriAod5/JB25XbJK2CDThUmxPYh4KcjraGFhAczpYO5DIT+QTKck264twd0YwDfUGPbi8f+4dQadQyqv5P347E2sg+no2VZm5oerxVjYtxreLY/+KvxL6c66XcoFjYDA4ZNedyTwIt8tddiLIDPmvry1Ws3T85Pnm6XFBXmlpWezkwUomk0x+9X/JqmnEJ045b4wItmlnnvmdd++cUv7/wyALoNgK4t0Mwzv51rHx1oT+5u2LCvVm7qmbNzueCUoyP3VL4MWn0/eHYI9M0CXQ9q3wy7f/sP7t8HcnencsPxvhnWvj/VHrAmjPexzYTrSzNh2On/ftGXXuml9/g/uLzr4fjd9/wNT8Bb+Btp0ELR')))

Dominant set is {$\mathcal{NP}$}

Complete the boolean function dom_verif(D, k, graph) that takes as parameters the candidate solution D that is a set of nodes, the size k and the graph G.

The algorithm has two steps. First, we check that the size of D is less or equal to k. Then, we check whether D dominates G.

def dom_verif(D, k, graph):
    ############### TODO : complete code #####################


    return True

Test your function by running the following cell:

my_graph=load_graph(graph01)

# Verify the size!
assert not dom_verif({'1','5','8'}, 2, my_graph)

# Verify the dominant
assert (        dom_verif({'1','5','8'}, 3, my_graph) 
        and     dom_verif({'1','5'}, 2, my_graph) 
        and not dom_verif({'1','8'}, 2, my_graph))

display_dominant({'1','5'}, my_graph)

[Optional] Greedy algorithm

Complete the code below to implement a greedy algorithm to find a dominant-set.

def greedy_dominant(graph):
    D = set()
    ############### TODO : complete code ##################### 


    return D

my_graph1=load_graph(graph01)
assert greedy_dominant(my_graph1) == {'1', '5'}

my_graph2=load_graph(graph02)
assert greedy_dominant(my_graph2) == {'5', '6', '1'}
display_dominant(greedy_dominant(my_graph2), my_graph2)