Exercise 3.2

算法设计与分析

Problem Discription

For maximum matching Hall's Theorem states: If there is no matching of size $|U|$, then some set $X \subseteq U$ has $|X|>|\Gamma(X)|$. The set $X$ is a "witness" for the fact that no matching has size $U$.

The max flow min cut theorem states: If there is no $s$-$t$-flow of value $k$, then there is an $s$-$t$-cut $(S, V \setminus S)$ with $c(S, V \setminus S)<k$. Here, the cut $(S, V \setminus S)$ is a "witness" for the non-existence of a flow of value $k$.

Prove "something like Hall's Theorem" for the feasible orientation problem. What could be a witness ofr the non-existence of a feasible orientation? In particular:

1. Give an example graph with degree constraints which has no feasible orientation. Your example should be non-obvious, i.e., it should not be completely clear that it has no feasible orientation. Try to find a concise argument why it does not have one!

2. Try to make a statement like this: "$G$ has no feasible orientation with respect to $c$ if and only if an object $X$ with a certain property $P$ exists". It should hold that we can easily verify whether $P$ holds for a given object $X$.

3. Prove the statement you made in Point 2.

Example

Statement

If there is no feasible orientation with respect to c if and only if an object $X \subseteq V$ with a certain property $P$ that

$$| \{ (u,v) \mid u \in X\ \mathrm{and}\ v \in X \} | > \sum_{X->\mathbb{N}_0}{c}$$
where $(u,v)$ is directed.

Proof

If there is an object $X \subseteq V$ with a certain property $P$ that

$$| \{ (u,v) \mid u \in X\ \mathrm{and}\ v \in X \} | > \sum_{X->\mathbb{N}_0}{c}$$
where $(u,v)$ is directed.
we can derive a bipartite graph as Excersice 3.1, which set $X' \subseteq U$ has $$|X'|>|\Gamma(X')|$$
where $X'=\{e_{uv}| u \in X\ \mathrm{and}\ v \in X \}$.
From Hall's Theorem, we can simply determine that there is no feasible orientation with respect to c.