This was a 200-point challenge, and the description of the challenge was as follows:
We have a lot of friends because we’re super popular, but unfortunately we have to split our set of friends into two halves so they can go into war with each other. That’s just life, unfortunately.
We have a set of N friends, and M pairwise connections between friends. Each connection goes both ways, so if, for example, Aariss Weiron is friends with Bendelman, then Bendelman is also friends with Aariss Weiron. Each connection also has an associated weight, representing how close the two friends are, which is a positive integer value. No two pairs of friends with a connection have the same weight.
Our objective is to somehow divide our set of friends into two ‘equal’ halves. We also want to put friends who are pretty close to each other into the same set. We formally define the problem as follows:
We have a set of friends of even size, some with bi-directional pairwise connections. Each connection has a positive integer weight, and each connection has a distinct weight. Our objective is to divide our friends into two sets of equal size with this property: The largest connection-weight that crosses between the two sets should be as small as possible. Compute this connection-weight for each friend network given. A crossing connection is one such that the two friends it connects are in different sets. Each friend network is in the following format: The first line has two numbers:
N (guaranteed to be even) and M (number of connections). M lines follow this line. Each one represents a connection and has three tokens. The first two are the friends it connects, and the last one is the weight of the connection.
This problem has some similarity with a well-known problem called , in which case you are to minimize the sum of all weights in a cut dividing the graph in two. The optimization problem is NP-hard (later in this post, I will also show you code to approximate that problem). The difference with the problem ‘Space Friends’ is that we do not care about the sum, but only the maximum.
The general idea is as follows: Let be then maximum weight over all edges. Pick a number
such that
and start with the two nodes
connected with the highest weight
. Now, color all neighbors of the two nodes
having connection weight
. Repeat for all previously colored nodes, until the no more nodes are to be colored. We know that if we were to split this subgraph in any way, the weight of at least one edge would be at least
.
If the size of the graph is larger than half of the total number of nodes we increase
, otherwise we decrease it. For this procedure, we may speed it up using binary search. Once we have found a subgraph
with
nodes, we may stop. Any other edge connecting this subgraph must necessarily be smaller than
. We may now find the maximum weight by looking at the outgoing edges from
. This is the sought value.
Embodied in Python, the code may be as follows:
import networkx as nx import sets def get_set(node, graph, gset, w): # add node to set i.e., mark as visited gset.add(node) # visit all neighbors connected with weight >= w for neighbor in graph[node]: if neighbor not in gset and graph[node][neighbor]['weight'] >= w: get_set(neighbor, graph, gset, w) #create graph graph = nx.Graph() list_of_nodes, list_of_edges = [], [] max_weight, start_node, num_nodes = 0, -1, 0 networks = ['network1.txt','network2.txt','network3.txt','network4.txt'] # read in the nodes from the first network f = open(networks[0],'r') print "[ ] Reading data..." for line in f: if len(line.split()) > 2: # skip first line # parse the line, ssv node1 = int(line.split()[0]) node2 = int(line.split()[1]) weight = int(line.split()[2]) max_weight = max(max_weight,weight) if weight == max_weight: start_node = node1 # add edge list_of_edges.append((node1,node2,weight)) # make sure every node is added exactly once if node1 not in list_of_nodes: list_of_nodes.append(node1) if node2 not in list_of_nodes: list_of_nodes.append(node2) else: num_nodes = int(line.split()[0]) # add nodes graph.add_nodes_from(list_of_nodes) graph.add_weighted_edges_from(list_of_edges) graph.graph['edge_weight_attr'] = 'weight' # pivot in the middle pivot = max_weight/2 i = 1 print "[ ] Searching..." # binary search while True: # create new set right_set = set() right_set.add(start_node) i += 1 # visit graph get_set(start_node, graph, right_set, pivot) if len(right_set) == num_nodes/2: break if max_weight/2**i == 0: break if len(right_set) > num_nodes/2: pivot += max_weight/2**i if len(right_set) < num_nodes/2: pivot -= max_weight/2**i highest_outgoing_weight = 0 # get the max-weight outgoing edge for node in right_set: for neighbor in graph[node]: if neighbor not in right_set and highest_outgoing_weight < graph[node][neighbor]['weight']: highest_outgoing_weight = graph[node][neighbor]['weight'] print "[+] Found maximum weight:", highest_outgoing_weight
This gives us the flag sctf{43226;9474;40749;750}
. Cool 🙂
Now, let us consider the second (NP-hard) problem. Now, we cannot look at a single connection, but the sum of all connections. We use the METIS software for this purpose. The algorithm in METIS is non-deterministic, so we will run it many times to amplify the probability of finding a good cut.
import networkx as nx import matplotlib.pyplot as plt import numpy as np import metis ITERATIONS = 20 # how many successful iterations? #create graph graph = nx.Graph() list_of_nodes, list_of_edges = [], [] # read in the nodes from network1.txt f = open('network1.txt','r') for line in f: if len(line.split()) > 2: # skip first line # parse the line, ssv node1 = int(line.split()[0]) node2 = int(line.split()[1]) weight = int(line.split()[2]) # add edge list_of_edges.append((node1,node2,weight)) # make sure every node is added exactly once if node1 not in list_of_nodes: list_of_nodes.append(node1) if node2 not in list_of_nodes: list_of_nodes.append(node2) # add nodes graph.add_nodes_from(list_of_nodes) graph.add_weighted_edges_from(list_of_edges) graph.graph['edge_weight_attr'] = 'weight' seed = 3000 # deterministic seed best_cut = -1 iterations = 0 print "[ ] Running METIS... " while iterations < ITERATIONS: # find weight minimum bisection (edgecuts, parts) = metis.part_graph(metis.networkx_to_metis(graph), \ nparts=2, rtype='sep2sided', recursive=True, seed=seed) # make sure the cut divides the set perfectly if sum(parts) == len(parts)/2: iterations += 1 if edgecuts < best_cut or best_cut < 0: best_cut = edgecuts seed += 1 print "[+] Found two partitions with cut-value", best_cut