UVa 1439 — Exclusive Access 2

Tags: Graph Theory, Graph Coloring, DAG, Bitmask DP, Inclusion-Exclusion, Backtracking

Problem Overview

We are given a set of resources and processes, and we need to create a deadlock-free schedule. Each process requires two distinct resources.

A sequence of resource acquisitions forms an alternating wait chain of the form:

These chains are transitive: process $$$p_1$$$ and $$$p_2$$$ belong to the same chain if $$$p_1$$$ uses resources $$$r_1$$$ and $$$r_2$$$, while $$$p_2$$$ uses $$$r_2$$$ and $$$r_3$$$.

Initially, the resource graph is undirected: each process represents an undirected edge $$${r_a, r_b}$$$. Directing the edge as either $$$r_a \to r_b$$$ or $$$r_b \to r_a$$$ determines the order in which a process acquires its resources.

The main challenge is to eliminate deadlocks by ensuring that no chain loops back on itself—that is, $$$r_1 \ne r_N$$$.

Among all valid deadlock-free orientations, we want to minimize the length of the maximal alternating wait chain.

Main Idea: Graph Coloring & DAG Construction

How do we eliminate cycles and guarantee $$$r_1 \ne r_N$$$?

We can translate this problem into Graph Coloring.

1. Guaranteeing a DAG

Assign a positive integer color $$$C[u]$$$ to each resource vertex $$$u$$$.

For every directed edge $$$u \to v$$$, we enforce the condition:

Along any directed path

the color values must strictly increase:

Because a sequence of strictly increasing integers cannot contain repeated values, $$$r_1 = r_N$$$ is mathematically impossible.

This guarantees that the directed resource graph is a Directed Acyclic Graph (DAG), ensuring a deadlock-free schedule.

2. Minimizing Chain Length

By the Gallai-Roy-Vitaver theorem, the minimum number of colors $$$k = \chi(G)$$$ needed to properly color the undirected graph determines the length of the longest path:

Thus, the problem reduces to finding the Chromatic Number $$$k = \chi(G)$$$ of a graph with $$$V \le 15$$$ vertices, partitioning $$$V$$$ into $$$k$$$ independent sets, and directing edges from lower-colored vertices to higher-colored vertices ($$$u \to v$$$ if $$$C[u] \lt C[v]$$$).

Now solving this is upto you, share better approaches. Keep practicing!!