### [UVa 1439 — Exclusive Access 2](https://vjudge.net/problem/UVA-1439)↵
↵
**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:↵
↵
$$↵
r_1 \to p_1 \to r_2 \to p_2 \to r_3 \to p_3 \dots \to r_N↵
$$↵
↵
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 Coloringand& 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:↵
↵
$$↵
C[u] < C[v]↵
$$↵
↵
Along any directed path↵
↵
$$↵
r_1 \to r_2 \to \dots \to r_m↵
$$↵
↵
the color values must satisfytrictly increase:↵
↵
$$↵
C[r_1] < C[r_2] < \dots < C[r_m]↵
$$↵
↵
Therefore, a directed path can never return to a previously visited vertex. HenceBecause 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 DAG.↵
↵
This eliminates deadlocks caused by cyclic wait chainsirected Acyclic Graph (DAG), ensuring a deadlock-free schedule.↵
↵
#### 2. Minimizingthe Chain Length↵
↵
By the **Gallai-Roy-Vitaver theorem, for an undirected graph $G$:↵
↵
$$↵
\min_{\text{orientations}}(\text{longest directed path})↵
= \chi(G) - 1↵
$$↵
↵
where $\chi(G)$ is the chromatic number of $G$.↵
↵
Therefore, if the graph can be colored using $k$ colors, we can orient every edge from the vertex with the smaller color to the vertex with the larger color.↵
↵
The resulting DAG has longest directed path of at most $k-1$ edges.**, the minimum number of colors $k = \chi(G)$ needed to properly color the undirected graph determines the length of the longest path:↵
↵
$$↵
\text{Maximal Path Length (in vertices)} = k↵
$$↵
↵
$$↵
\text{Maximal Alternating Wait Chain Length} = k - 2↵
$$↵
↵
Thus, the problem reduces to finding thecChromatic nNumber $k = \chi(G)$ of a graph with at most $$V \le 15$ vertices.↵
↵
problem: https://vjudge.net/problem/UVA-1439↵
↵
S, partitioning $V$ into $k$ independent sets, and directing edges from lower-colored vertices to higher-colored vertices ($u \to v$ if $C[u] < C[v]$).↵
↵
Now solving this is upto you, share better approaches. Keep practicing!!
↵
**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:↵
↵
$$↵
r_1 \to p_1 \to r_2 \to p_2 \to r_3 \to p_3 \dots \to r_N↵
$$↵
↵
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
↵
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:↵
↵
$$↵
C[u] < C[v]↵
$$↵
↵
Along any directed path↵
↵
$$↵
r_1 \to r_2 \to \dots \to r_m↵
$$↵
↵
the color values must s
↵
$$↵
C[r_1] < C[r_2] < \dots < C[r_m]↵
$$↵
↵
↵
This guarantees that the directed resource graph is a D
↵
This eliminates deadlocks caused by cyclic wait chains
↵
#### 2. Minimizing
↵
By the **Gallai-Roy-Vitaver theorem
↵
$$↵
\min_{\text{orientations}}(\text{longest directed path})↵
= \chi(G) - 1↵
$$↵
↵
where $\chi(G)$ is the chromatic number of $G$.↵
↵
Therefore, if the graph can be colored using $k$ colors, we can orient every edge from the vertex with the smaller color to the vertex with the larger color.↵
↵
The resulting DAG has longest directed path of at most $k-1$ edges.
↵
$$↵
\text{Maximal Path Length (in vertices)} = k↵
$$↵
↵
$$↵
\text{Maximal Alternating Wait Chain Length} = k - 2↵
$$↵
↵
Thus, the problem reduces to finding the
↵
problem: https://vjudge.net/problem/UVA-1439↵
↵
S
↵
Now solving this is upto you, share better approaches. Keep practicing!!
