Independence set systems

Definition. $S=(X,\mathcal{F})$ is called independence system if

  1. $X$ is finite set (ground set)
  2. $\mathcal{F}$ is a collection of subset then $\forall A\in\mathcal{F}$ under inclusion which means $A\in\mathcal{F}\ A'\subseteq A \Rightarrow A'\in\mathcal{F}$

Theorem1. Let $S=(E,\mathcal{F})$ be independent system, then the following are equivalent

(A): $\forall w:E\to\mathbb{R}_{\ge0}$. GREEDY correctly solves the problem

(B): $\forall F,F'\in\mathcal{F}$ if $|F'|=|F|+1$ then $\exists\ e\in F'\setminus F$ s.t. $F\cup\{e\}\in\mathcal{F}$

(C) If $A\subseteq E$ and $F,F'$ are maximal independent subset of $A$ then $|F|=|F'|$

Proof. $A\Rightarrow B$ equivalently $\neg B\Rightarrow \neg A$ Suppose $\exists F,F'\in\mathcal{F}\ |F'|=|F|+1,\forall e\in F'\setminus F$ we have $F\cup\{e\}\notin\mathcal{F}$

Set $|F|=p$ and define $w:E\to\mathbb{R}_{\ge0}$

$$ w(e)= \begin{cases} p+1 & \text{if }e\in F'\setminus F\\ p+2 & \text{if }e\in F\\ 0 & \text{if }e\in E\setminus(F\cup F') \end{cases} $$

by the rules of GREEDY, it will first choose the $p$ elements in $F$ and it is feasible since the subset of $F$ is independent Then it will reject all element in $F'\setminus F$ since $F\cup\{e\}\notin\mathcal{F}$ and then accept or reject the elements in $E\setminus(F\cup F')$ So final $w(X^*)\le p(p+2)=p^2+2p$ But $w(F')\ge(p+1)^2=p^2+2p+1>p^2+2p$ so $\neg A$

$C\Rightarrow A$ equivalently $\neg A\Rightarrow \neg C$

Suppose for some $w:E\to\mathbb{R}_{\ge0}$ GREEDY fails to find optimal solution So GREEDY finds $X^*=\{e_1\cdots e_m\}$ but $\exists$ some independent set $X=\{e_1'\cdots e_k'\}$ s.t. $w(X)>w(X^*)$

Assume wlog $w(e_1)\ge w(e_2)\ge \cdots \ge w(e_m)$ and $w(e_1')\ge \cdots \ge w(e_k')$ and $X^*$ is maximal wlog we set $X$ is maximal then by $C$ $(m=k)$ $\{e_1'\}$ is independent since it is the subset of independent set $X$ So by GREEDY the first step we have $w(e_1)\ge w(e_1')$ then suppose that $w(e_i)\ge w(e_i')\ i=1\cdots r-1\ ,w(e_r)<w(e_r')$ def: define $A:=\{e\in E:w(e)\ge w(e_r')\}$ , if $\exists e\in A$ s.t. $\{e_1\cdots e_{r-1},e\}$ is also independent then $w(e)\ge w(e_r')>w(e_r)$ and GREEDY will choose $e$ ,but it choose $e_r$ so $\{e_1\cdots e_{r-1}\}$ is the maximal independent subset of $A$ and $\{e_1'\cdots e_r'\}$ is also an independent subset of $A$ which have more elements which contradicts $C$ so $w(e_i)\ge w(e_i')\ i=1\cdots m$ and is contradicted with $w(X)>w(X^*)$ So $\neg C$

$B\Rightarrow C$

Suppose $B$ holds $\forall A\subseteq E$ $F,F'$ maximal independent subsets of $A$ by contradiction suppose $|F|\neq|F'|$ wlog $|F|<|F'|$. Let $F''$ be any subset of $F'$ s.t. $|F''|=|F|+1$ $F''\in\mathcal{F}$ since it is the subset of $F'$ so by $B$ $\exists e\in F''\setminus F$ s.t. $F\cup\{e\}\in\mathcal{F}$ since $e\in F''\subseteq F'\subseteq A$ so $F\cup\{e\}\subseteq A$ which is contradict with $F$ is maximal independent subsets of $A$ so $B\Rightarrow C$

cardinality: For maximum weight span-forest problem, GREEDY will always correct

Proof. We said that a independence systems are called matroids if GREEDY will always be correct, so now, we have that using GREEDY algorithm will always be correct in the maximum weight forest problem Let $(G=(V,E))$ be a graph, $V$ is the set of nodes $E$ is the set of edge

Theorem2. If $G$ is a tree then $n=m-1$ $m=|V|$ $n=|E|$

Proof. If $(m=1)$ then $G$ has no edge so $(n=0)$ If $(m>1)$ then if $\exists \delta=0$ which means not connect, if $\forall v\in V\ \delta(v)\ge2$ then any state can move from node to node for any node, which will cause cycle, which means not acyclic. So $\exists \delta(v)=1$ Let $d'(v)=1$ with edge $e$ connect, let $G'=(V\setminus\{v\},E\setminus\{e\})$ then $m'=m-1\ \ n'=n-1$ So assume $n'=m'-1 \Rightarrow n=n'+1=m'=m-1$ begin with $(m=1)\ (n=0)$ So $n=m-1$

Lemma1. If a graph $G$ is acyclic then every subgraph of $G$ is acyclic

Proof. there is no cycle in $(G=(V,E))$ so no cycle in $V'\subseteq V\ E'\subseteq E$

Definition. a graph $H$ is a component of $G$ if $H\subseteq G$, $H$ is connected and $H\subseteq H'$, $H'\subseteq G$, $H'$ connect $\Rightarrow H=H'$

Theorem3. If $G$ is acyclic graph then $n=m-p(G)$

Proof. Let $(p=p(G))$ means the number of component of $G$, for each component $n_i=m_i-1$ since they are acyclic and connected so $n=\sum_{i=1}^p n_i=\sum_{i=1}^p (m_i-1)=m-p$

Definition. A subgraph $T$ of graph $G$ is a spanning tree of $G$ if $T$ is a tree and $(V(T)=V(G))$

Definition. Graph $F$ is called a maximal acyclic subgraph (MAS) of $G$ if $F$ is an acyclic subgraph of $G$ but not a proper subgraph of any acyclic subgraph of $G$

Theorem4. Let $G$ be a connected graph with $m$ nodes Then every MAS of $G$ is a spanning tree of $G$ and hence has $m-1$ arcs.

Proof. We need prove $F$ be a MAS of $G$ which is acyclic connected spanning spanning: if $V(F)\neq V(G)$ then for any node $v$ in $V(G)\setminus V(F)$, add $v$ to the $F$ without any arc, then $F$ becomes a proper subgraph of $F+v$ and $F+v$ is also acyclic which is contradiction

connected: if $F$ is not connected, then at least $\exists$ a component $F_1$, which is $F_1\neq F$ since $F_1$ is not connected, then let $F_2=F/F_1$ take $u\in V(F_1)$ $v\in V(F_2)$, since $G$ is connected, so $\exists$ a path from $u$ to $v$ so must $\exists\ u'v'$ s.t. $u'\in V(F_1)\ v'\in V(F_2)\ u'v'\in E(G)$ Let $F'=(V(F),E(F))\cup\{u'v'\}$, it is acyclic subgraph which contain $F$ as a proper subgraph which is a contradiction.

Corollary1. Let $G$ be a graph with $m$ node and $p$ component. Then maximal acyclic subgraph of $G$ is a spanning forest and has $m-p$ arcs.

Proof. Let $F$ be a MAS of $G$, then each component of $F$ is a MAS of that component which by theorem4. is a spanning tree and has $m_i-1$ arcs, so together MAS of $G$ is a spanning forest and has $m-p$ arcs.

So for theorem1. (c) $\forall A\subseteq E$, $F,F'$ are MAS then $|F|=|F'|=m-p$ So maximum weighted spanning tree problem is a matroids and GREEDY algorithm will always be correct.