CS330 HW05

Problem 1 §

V = [] # all vertices
E = [] # all edges
# A[1..m] holds the preference list
 
def graphCreation():
	# for every friend
	for k = 1..m:
		prevNode = None
		for i = 1..len(A[k]):
			node = A[k][i]
			if node not in V:
				V.append(node)
			# if this is the first node
			if prevNode != None:
				# add the edge
				E.append((node, prevNode))
			prevNode = node
 
post = [] # post-time
visited = [] # add visited verticies
clock = 0
 
# in-class algorithm
def DFS(u):
	visited[u] = True
	clock += 1
	for (u -> v) in E:
		if visited[v] == False:
			DFS(v)
	clock += 1
	post = (u, clock)
	
def AllDFS(V, E):
	for v in V:
		if visited[v] == False:
			DFS(v)
 
# in-class proof
def TopologicalSort():
	topological = Mergesort(post) # reverse merge sort of post-time
	# will be sorted by clock time:
	# e.g. [(v1, 0), (v4, 3), (v2, 7), ...]
	return [v for v, time in topological]
				

High-Level Algorithm §

This problem resembles the computation of a Topological Sorting on a Directed Acyclic Graph (DAG) that is created from the preference lists, which may contain contradictions.

1. We create a graph where each vertex represents a restaurant and each directed edge from vertex i to j signifies that restaurant i is preferred over restaurant j by some friend. We let $n$ be the number of vertices (restaurants), $m$ the number of edges (preferences), and $N$ the total length of all preference lists.
2. We perform a Depth-First Search (DFS) on this graph to detect a cycle. If there is a cycle (contradictions in the preference lists), we report that no such ordering of restaurants exists.
3. If there is no cycle, we carry out a Topological Sort on this graph which gives the required ordering of restaurants.

Proof of Correctness §

• Let’s represent the preference list of each friend as a directed path in the graph. The direction from $i$ to $j$ ($i\to j$) represents that restaurant $i$ is preferred over restaurant $j$. Therefore, if there is an ordering that satisfies all friends’ preferences, the directed graph has to be acyclic.
• We perform DFS on the graph, and if we find a back edge (which forms a cycle), it means the preferences are contradictory, and no solution exists. So, our DFS serves as a mechanism to validate if such an ordering can exist.
• If DFS completes without detecting a cycle, we then apply Topological Sorting on this graph. The use of DFS ensures that all vertices are explored and included in the final ordering.

Running Time §

• Creating the graph takes $O(N)$ time as we are examining each preference and creating an edge for it.
• Running a DFS on the constructed graph takes $O(n+m)$ time, where $n$ is the number of vertices, and $m$ is the number of edges, visited exactly once.
• The Topological sorting takes $O(n\log n)$ time as uses mergesort via post-time
• ⇒ Total running time of the algorithm is $O(N)+O(n+m)+O(n\log n)=O(n\log n+m+N)$.

Problem 2 §

V = [] # all verticies
E = [] # all edges, undirected graph
for c in Constraints:
	# unpack the constraint into the two verticies of a graph
	u, v = c
 
	# add both verticies
	if v not in V:
		V.append(v)
	if u not in V:
		V.append(u)
 
	# add the edge if it doesn't exist
	# note that this is an undirected graph
	if both (u, v) and (v, u) not in E:
		E.append((u, v))
 
 
 
visited = []
team = [-1] * len(V) # create a team array initialized with -1
# there is team 0 and team 1
bipartite = True # assume true until disproven
 
def partitionDFS(u):
	visited.append(u)
	for all neighbours v of u:
		# if same team, not bipartite
		if v in visited and team[v] == team[u]:
				bipartite = False
				return
		# if different team and not in visitied
		elif v not in visited:
			# assign v the opposite team as u
			team[v] = 1 - team[u]
			partitionDFS(v)
 
def AllDFS():
	for v in V:
		if v not in visited:
			team[v] = 0 # start coloring from team 0
			partitionDFS(v)
 

Idea §

This problem can be seen as a variant of Bipartite Graph Checking problem, where every edge represents the constraint that two players cannot be in the same team.

1. We construct a graph where each vertex corresponds to a player and each edge corresponds to the constraint between players. Let $n$ be the number of vertices (players) and $m$ be the number of edges (constraints).
2. We then perform a Depth-First Search (DFS) on this graph aiming to 2-color the graph where color should alternate between vertices. If during this process we encounter a vertex that has already been visited and has the same color as the current vertex, it means players with existing constraints are in the same team, thus, no valid partition can exist.
3. If the DFS completes without detecting such a situation, the created 2-color partitions are the required team allocations.

Proof of Correctness §

The underlying premise for this solution relies on the properties of Bipartite Graphs.

• If it’s possible to divide players into two distinct groups such that no two players from the same team have constraints between them, the graph is bipartite.
• During the 2-color DFS check, if we come across an already visited and colored node that has the same color as the current node, we conclude that the graph isn’t bipartite - thus, such a partition doesn’t exist. If DFS completes without such contradictions, it means the graph is bipartite and we’ve found a valid partition.

Running Time §

• Constructing the graph takes $O(m)$ time as every constraint creates an edge in the graph.
• Running DFS across all vertices and edges of our graph takes $O(n+m)$ time.
• ⇒ Total running time of the algorithm: $O(m)+O(n+m)=O(n+m)$.