Advanced Algorithms UE 10

by Maarten Behn
Group 5

Exercise 10.1 (5 Points)

Let $D=(V,A)$ be a directed graph and let $S\subseteq V$ be a subset of vertices.
For each $s\in S$ let $k_s$ be a natural number.
Show that $(A,\{F\subseteq A:|{\delta }_F^{-}(s)|\le k_s\forall s\in S\})$ is a matroid.

We have to show:

1. $\varnothing \in \mathcal{I}$
   The empty set $F=\varnothing$ has no arcs, so for all $s\in S$, we have $|{\delta }_F^{-}(s)|=0\le k_s$, since $k_s$ is a positive integer.
   $\Rightarrow \varnothing \in \mathcal{I}$

2. $\forall F\in \mathcal{L}$ and $F^{\prime }\subseteq F$, we have $F^{\prime }\in \mathcal{I}$
   since $|{\delta }_{F^{\prime }}^{-}(s)|\le |{\delta }_F^{-}(s)|\le k_s$
   $\Rightarrow F^{\prime }\in \mathcal{I}$

3. $\forall F_1,F_2\in \mathcal{L}$ with $|F_1|<|F_2|$, then there exists $a\in F_2\setminus F_1$ such that $F_1\cup \{a\}\in \mathcal{I}$.

Group the arcs in $A$ into disjoint classes based on the vertex they point to in $S$.

$$A_s:=\{a=(u,s)\in A\}$$

So $A_s$ is the set of all arcs in $A$ that enter vertex $s$. Then the family $\mathcal{L}$ consists of all subsets $F\subseteq A$ such that for each $s\in S$, $|F\cap A_s|\le k_s$.

This then is the definition of a partition matroid:

• The ground set $A$ is partitioned into disjoint subsets $A_s$, one for each $s\in S$.

• Each subset $A_s$ has a quota $k_s$, and we require that any independent set $F\subseteq A$ satisfies $|F\cap A_s|\le k_s$.

Exercise 10.2 (Intersection of matroids) (2+5 Points)

The intersection of two independent systems $(E,{\mathcal{F}}_1)$ and $(E,{\mathcal{F}}_2)$ is defined as $(E,{\mathcal{F}}_1\cap {\mathcal{F}}_2)$.
(a) Show that $(E,{\mathcal{F}}_1\cap {\mathcal{F}}_2)$ is again an independent system.

Let $\mathcal{F}={\mathcal{F}}_1\cap {\mathcal{F}}_2$

We have to show:

1. $\varnothing \in \mathcal{F}$
   since $\varnothing \in {\mathcal{F}}_1\wedge \varnothing \in {\mathcal{F}}_2\Rightarrow \varnothing \in {\mathcal{F}}_1\cap {\mathcal{F}}_2=\mathcal{F}$

2. $\forall A\in \mathcal{F}$ and $B\subseteq A$, we have $B\in \mathcal{F}$
   if $A\in \mathcal{F}\Rightarrow A\in {\mathcal{F}}_1\wedge A\in {\mathcal{F}}_2$
   since $\forall B\subseteq A$ holds $B\in {\mathcal{F}}_1\wedge B\in {\mathcal{F}}_2$
   $\Rightarrow B\in {\mathcal{F}}_1\cap {\mathcal{F}}_2=\mathcal{F}$

(b) Show that any independent system $(E,\mathcal{F})$ is the intersection of a finite number of matroids.

Let $(E,\mathcal{F})$ be an independent system with rank function

$$r(A)=\max \{|I|:I\subseteq A,I\in \mathcal{F}\}$$

for all $A\subseteq E$.

The rank of the system is than

$$k:=\underset{F\in \mathcal{F}}{\max }|F|.$$

There is a family ${\mathcal{L}}_j$ for each $j=1,\dots ,k$

$${\mathcal{I}}_j:=\{A\subseteq E:r(A)\ge j\}.$$

Each $(E,{\mathcal{I}}_j)$ is a matroid with rank function

$$r_j(A):=\min \{|A|,j\},$$

because

1. $\varnothing \in {\mathcal{I}}_j$ since $r(\varnothing )=0\ge 0$.
2. If $A\in {\mathcal{I}}_j$ and $B\subseteq A$, then

$$r(B)\ge r(A)-|A\setminus B|\ge j-|A\setminus B|,$$

so $B\in {\mathcal{I}}_j$.
3. For any $A,B\in {\mathcal{I}}_j$ with $|A|<|B|$, there exists $e\in B\setminus A$ such that $A\cup \{e\}\in {\mathcal{I}}_j$.
$r(A)\ge j\Rightarrow \exists A^{\prime }\subseteq A\text{with}|A^{\prime }|=j\wedge A^{\prime }\in \mathcal{F}$
$|A|<|B|\Rightarrow \exists e\in B\backslash A$
$A^{\prime }\subseteq A\wedge |A^{\prime }|=j\Rightarrow r(A\cup \{e\})\ge |A^{\prime }|=j$
$\Rightarrow A\cup \{e\}\in {\mathcal{I}}_j$

construct $\mathcal{F}$ with

$$\mathcal{F}=\bigcap _{j=1}^k{\mathcal{I}}_j,$$

since $A\in \mathcal{F}$ if and only if $r(A)=|A|\le k$ and $A\in {\mathcal{I}}_j$ for all $j\le |A|$.

Thus, every independent system is the intersection of finitely many matroids.

Exercise 10.3 (3+5 Points)

There are $n$ tasks to be completed in $n$ days.
Each task $j$ has a deadline $d_j\le n$ by which it must be completed, and requires one day to process.

(a) We call a subset $X$ of tasks feasible if there exists a schedule that can complete all tasks in X by their respective deadlines.
Furthermore, we define
$X(t):=\{j\in X|d_j\le t\}$
for all $t\in N$.
Show that $X\subseteq [n]=\{1,...,n\}$ is feasible if and only if for all $t\in N$ it holds that $|X(t)|\le t$.

(⇒) Suppose $X$ is feasible. Show that $\forall t\in \mathbb{N}$, $|X(t)|\le t$.

Since $X$ is feasible, there exists a schedule that completes all tasks in $X$ on or before their deadlines.
Consider any time $t\in \mathbb{N}$. Let $X(t)$ be the set of tasks in $X$ that have deadline at most $t$.
Since each task takes exactly one day, and all tasks in $X(t)$ must be completed by day $t$, we need at least $|X(t)|$ time slots within the first $t$ days.
But there are only $t$ days up to day $t$, so we must have:

$$|X(t)|\le t$$

(⇐) Suppose that $\forall t\in \mathbb{N}$, $|X(t)|\le t$. Show that $X$ is feasible.

We use a greedy algorithm: schedule the tasks in $X$ in order of non-decreasing deadlines.

1. Sort tasks in $X$ as $j_1,j_2,\dots ,j_k$ such that $d_{j_1}\le d_{j_2}\le \cdots \le d_{j_k}$.
2. Schedule them one per day, assigning task $j_i$ to day $i$.

We now check that this schedule meets all deadlines.

Task $j_i$ is scheduled on day $i$.
Its deadline is $d_{j_i}$.
Since tasks are ordered by deadline, for any $i$ we know that $|X(d_{j_i})|\ge i$ (because at least $i$ tasks in $X$ have deadline $\le d_{j_i}$).
By the assumption $|X(d_{j_i})|\le d_{j_i}$, we get:

$$i\le |X(d_{j_i})|\le d_{j_i}$$

Therefore, task $j_i$ is scheduled on day $i\le d_{j_i}$, so it meets its deadline.

(b) Show that $([n],\mathcal{I})$, where $\mathcal{I}$ contains all feasible subsets of $[n]$, is a matroid.

We have to show that:

1. $\varnothing \in \mathcal{I}$
   There is a $X=\varnothing$ which is feasible, because there are no tasks that need to be scheduled.

2. If $X\in \mathcal{I}$ and $Y\subseteq X$, then $Y\in \mathcal{I}$.
   We want to show that $Y$ is feasible. From part (a), it is enough to show that for all $t$:

$$|Y(t)|\le t$$

But since $Y\subseteq X$, we have $Y(t)\subseteq X(t)$ for all $t$, and hence:

$$|Y(t)|\le |X(t)|\le t$$

Thus, $Y$ is feasible, so $Y\in \mathcal{I}$.

3. If $X,Y\in \mathcal{I}$ and $|X|<|Y|$, then there exists $j\in Y\setminus X$ such that $X\cup \{j\}\in \mathcal{I}$.

Since $Y$ is feasible, there exists a schedule for $Y$ that finishes all its tasks on time.
Suppose we try to add each $j\in Y\setminus X$ to $X$.
If for all such $j$ we had $X\cup \{j\}\notin \mathcal{I}$, then for each such $j$, there exists some $t$ such that:

$$|(X\cup \{j\})(t)|>t$$

But $|(X\cup \{j\})(t)|=|X(t)|+1_{\{d_j\le t\}}$, so this inequality can only happen if $|X(t)|=t$ and $d_j\le t$.
But the total number of such $j$‘s is limited by how many $t$‘s have $|X(t)|=t$, and $|X|<|Y|$ implies that not all $j\in Y\setminus X$ can be blocked this way.

Thus, at least one $j\in Y\setminus X$ can be added without violating feasibility.