On Wed, Aug 28, 2002 at 09:43:47AM +0100, José Abílio Oliveira Matos wrote: > Could you send me the offending file, please. :-)
Sure Andre' -- Those who desire to give up Freedom in order to gain Security, will not have, nor do they deserve, either one. (T. Jefferson)
#LyX 1.3 created this file. For more info see http://www.lyx.org/ \lyxformat 220 \textclass slides \begin_preamble \def\head#1{{\large{#1}}} \pagestyle{empty} \end_preamble \options fleqn \language english \inputencoding auto \fontscheme default \graphics default \paperfontsize default \spacing single \papersize Default \paperpackage a4 \use_geometry 0 \use_amsmath 1 \use_natbib 0 \use_numerical_citations 0 \paperorientation portrait \secnumdepth 3 \tocdepth 3 \paragraph_separation skip \defskip medskip \quotes_language english \quotes_times 2 \papercolumns 1 \papersides 1 \paperpagestyle default \layout Slide \layout Standard \begin_inset ERT status Collapsed \layout Standard { \backslash Large \end_inset Computing graph invariants \begin_inset ERT status Collapsed \layout Standard } \end_inset \newline \layout Standard >From edge decomposition formulas \newline to composition algorithms \newline \layout Standard \begin_inset Graphics filename g250_500.eps lyxscale 70 display monochrome width 100text% \end_inset \layout Standard André Pönitz \newline Hochschule Mittweida \layout Slide \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash head{ \end_inset Edge decomposition formulas \begin_inset ERT status Collapsed \layout Standard } \end_inset \begin_inset Formula \begin{eqnarray*} R(G) & = & a(e)\, R(G_{e})+b(e)\, R(G_{-e})\\ R(\overline{K_{n}}) & = & r(n)\\ r(0) & = & 1 \end{eqnarray*} \end_inset \layout Standard All-terminal reliability: \begin_inset Formula \begin{eqnarray*} R(G) & = & p_{e}\, R(G_{e})+(1-p_{e})\, R(G_{-e})\\ R(\overline{K_{n}}) & = & 1_{n\leq 1} \end{eqnarray*} \end_inset Negami polynomial: \begin_inset Formula \begin{eqnarray*} N(G) & = & x\, N(G_{-e})+y\, N(G_{e})\\ N(\overline{K_{n}}) & = & t^{n} \end{eqnarray*} \end_inset Chromatic polynomial: \begin_inset Formula \begin{eqnarray*} \chi (G) & = & \chi (G_{-e})-\chi (G_{e})\\ \chi (\overline{K_{n}}) & = & \lambda^{ n} \end{eqnarray*} \end_inset \layout Slide \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash head{ \end_inset Trivial algorithm \begin_inset ERT status Collapsed \layout Standard } \end_inset \layout Standard Repeatedly apply decomposition formula \layout Standard \align center \begin_inset Graphics filename tree.eps lyxscale 50 scale 80 \end_inset \layout Standard \begin_inset Formula $ O(2^{|E|})$ \end_inset operations \layout Slide \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash head{ \end_inset \begin_inset ERT status Collapsed \layout Standard } \end_inset \layout Standard Known: \layout Itemize polynomial algorithms for \newline restricted tree-width \layout Standard New: \layout Itemize composition algorithms are simple \layout Itemize performance not too bad \layout Itemize easily constructed \layout Standard >From decomposition formula we get \newline a working \begin_inset Formula $ O(n\, (m+n)\, (\omega (n)+\log n))$ \end_inset \newline within a few minutes. \layout Standard An hour of tweaking can reduce that \newline by a factor of \begin_inset Formula $ n$ \end_inset . \layout Slide Algorithm (sketch) \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash head{ \end_inset The Algorithm \begin_inset ERT status Collapsed \layout Standard } \end_inset \layout Standard input \begin_inset Formula $ G$ \end_inset \begin_inset Formula $ \ldots $ \end_inset a graph \layout Standard input \begin_inset Formula $ T$ \end_inset \begin_inset Formula $ \ldots $ \end_inset a decomposition formula \layout Standard compute composition sequence \begin_inset Formula $ S$ \end_inset from \begin_inset Formula $ G$ \end_inset \layout Standard determine transfer function \begin_inset Formula $ f$ \end_inset from \begin_inset Formula $ T$ \end_inset \layout Standard set \begin_inset Formula $ Z_{0}=\{ z_{0}\} $ \end_inset \layout Standard for \begin_inset Formula $ s_{i}\in S$ \end_inset do \layout Standard \begin_inset Formula $ \qquad $ \end_inset set \begin_inset Formula $ Z_{i}:=f(s_{i},Z_{i-1})$ \end_inset \layout Standard output \begin_inset Formula $ \textrm{ project}\left(Z_{t}\right)$ \end_inset \layout Slide 1 \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash head{ \end_inset Composition Sequences \begin_inset ERT status Collapsed \layout Standard } \end_inset \layout Standard \begin_inset Formula $ G=(V,E)$ \end_inset finite, undirected graph \layout Standard \begin_inset Formula $ n=|V|$ \end_inset , \begin_inset Formula $ m=|E|$ \end_inset , \begin_inset Formula $ t=2\, n+m$ \end_inset , \layout Standard \begin_inset Formula $ S=(s_{i})_{i=1}^{t},$ \end_inset \begin_inset Formula $ s_{i}=(x_{i},c_{i})$ \end_inset : \layout Standard \begin_inset Formula $ \quad\quad\quad x_{i}\in V\cup E,$ \end_inset \begin_inset Formula $ c_{i}\in\{ A,K,D\} $ \end_inset \layout Standard \begin_inset ERT status Collapsed \layout Standard { \backslash arraycolsep3pt \end_inset \begin_inset Formula $ S$ \end_inset is \emph on composition sequence \emph default if: \begin_inset Formula \begin{eqnarray*} \forall v & \in & V\quad\exists v_{A},v_{D}:\\ & & 1\leq v_{A}<v_{D}\leq t\:\land\: \\ & & \quad s_{v_{A}}=(v,A)\land s_{v_{D}}=(v,D) \end{eqnarray*} \end_inset \begin_inset Formula \begin{eqnarray*} \forall e & = & (uv)\in E\quad\exists u_{A},v_{A},k,u_{D},v_{D}:\\ & & 1\leq u_{A},v_{A}<k<u_{D},v_{D}\leq t\: \\ & & \quad\land\: s_{v_{A}}=(v,A)\:\land\: s_{u_{A}}=(u,A)\: \\ & & \quad\land\: s_{k}=(e,K)\: \\ & & \quad\land\: s_{v_{D}}=(v,D)\:\land\: s_{u_{D}}=(u,D) \end{eqnarray*} \end_inset \layout Standard \begin_inset ERT status Collapsed \layout Standard } \end_inset \layout Slide \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash head{ \end_inset Active Node Sets \begin_inset ERT status Collapsed \layout Standard } \end_inset \layout Standard sequence \begin_inset Formula $ (A_{i})_{i=1}^{t}$ \end_inset \begin_inset Formula \begin{eqnarray*} A_{i} & = & \{ v\in V(G)\:\exists v_{A}\leq i<v_{D}:\\ & & \qquad s_{v_{A}}=(v,A)\land s_{v_{D}}=(v,D)\} \end{eqnarray*} \end_inset Width \emph on \emph default of a composition sequence: \begin_inset Formula \[ \textrm{wd}(S)=\max_{ i}\;\textrm{card}\: A_{i}\] \end_inset \layout Standard Known relation: \begin_inset Formula \[ \textrm{wd}(S)\geq\textrm{pw}(G)+1\qquad\forall S\in\mathcal{S}(G)\] \end_inset \layout Standard Inequality is tight. \layout Slide \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash head{ \end_inset Edge Decomposition Formulae \begin_inset ERT status Collapsed \layout Standard } \end_inset \layout Standard Triplet \begin_inset Formula $ T=(a,b,r)$ \end_inset , \begin_inset Formula $ a,b:E(G)\to\mathcal{W},$ \end_inset \begin_inset Formula $ r:\mathbb{Z}\mapsto\mathcal{W}$ \end_inset is \emph on edge decomposition formula for the invariant \emph default \begin_inset Formula $ R$ \end_inset if: \begin_inset Formula \begin{eqnarray*} R(G) & = & a(e)\, R(G_{e})+b(e)\, R(G_{-e})\\ R(\overline{K_{n}}) & = & r(n),\\ r(0) & = & 1 \end{eqnarray*} \end_inset \begin_inset Formula $ \overline{K_{n}}\ldots $ \end_inset edgeless graph on \begin_inset Formula $ n$ \end_inset nodes \layout Slide \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash head{ \end_inset Indices, values, states \begin_inset Formula $ \ldots $ \end_inset \begin_inset ERT status Collapsed \layout Standard } \end_inset \layout Standard \begin_inset Formula $ \mathbb{P}(V)\ldots $ \end_inset set partitions of subsets of \begin_inset Formula $ V$ \end_inset \layout Standard \begin_inset Formula $ [\pi ,d]:\pi\in\mathbb{\mathbb{P}}(V),d\in\mathbb{Z}\ldots $ \end_inset \emph on index \layout Standard \begin_inset Formula $ w\in\mathcal{W}\ldots $ \end_inset \emph on value \layout Standard \begin_inset Formula $ z=([\pi ,d],w)\ldots $ \end_inset \emph on state \layout Standard multiset \begin_inset Formula $ Z$ \end_inset of states \begin_inset Formula $ \ldots $ \end_inset \emph on stateset \layout Standard \begin_inset Formula $ Z_{0}=\{ ([\emptyset ,0],0)\}\ldots $ \end_inset \emph on initial stateset \layout Standard \begin_inset Formula $ \mathcal{Z}$ \end_inset \begin_inset Formula $ \ldots $ \end_inset set of all statesets \newline \layout Standard \begin_inset Formula $ \pi |v\ldots $ \end_inset partition consisting of \begin_inset Formula $ \pi $ \end_inset and an additional block containing only \begin_inset Formula $ v$ \end_inset \layout Standard \begin_inset Formula $ \pi_{ (uv)}\ldots $ \end_inset \begin_inset Formula $ \pi $ \end_inset with blocks containing \begin_inset Formula $ u$ \end_inset and \begin_inset Formula $ v$ \end_inset merged \layout Standard \begin_inset Formula $ \pi^{ u}$ \end_inset \begin_inset Formula $ \ldots $ \end_inset block of \begin_inset Formula $ \pi $ \end_inset containing \begin_inset Formula $ u$ \end_inset \layout Standard \begin_inset Formula $ \pi -v$ \end_inset \begin_inset Formula $ \ldots $ \end_inset the partition \begin_inset Formula $ \pi $ \end_inset with node \begin_inset Formula $ v$ \end_inset removed \layout Standard Finally, for an edge \layout Standard \begin_inset Formula $ [\pi ,d]_{(e)}$ \end_inset \begin_inset Formula $ \ldots $ \end_inset \begin_inset Formula $ e=(uv)$ \end_inset let \begin_inset Formula $ [\pi_{ (uv)},d^{'}]$ \end_inset where \begin_inset Formula $ d^{'}=d$ \end_inset if \begin_inset Formula $ \pi^{ u}=\pi^{ v}$ \end_inset and \begin_inset Formula $ d^{'}=d-1$ \end_inset otherwise. \layout Slide \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash head{ \end_inset Transfer function \begin_inset ERT status Collapsed \layout Standard } \end_inset \layout Standard \begin_inset Formula $ G$ \end_inset \begin_inset Formula $ \ldots $ \end_inset graph, \begin_inset Formula $ T$ \end_inset \begin_inset Formula $ \ldots $ \end_inset edge decomposition formula \layout Standard \begin_inset Formula $ f:\mathcal{S}(G)\times\mathcal{Z}\to\mathcal{Z}$ \end_inset : \begin_inset Formula \begin{align*} f((v,A),Z) & =\cup_{ ([\pi ,d],w)\in Z}\left\{ ([\pi |v,d+1],w)\right\} \\ f((e,K),Z) & =\cup_{ ([\pi ,d],w)\in Z}\\ & \left\{ ([\pi ,d]_{(e)},a(e)\, w),([\pi ,d],b(e)\, w)\right\} \\ f((v,D),Z) & =\cup_{ ([\pi ,d],w)\in Z}\left\{ ([\pi -v,d],w)\right\} \end{align*} \end_inset for all \begin_inset Formula $ Z\in\mathcal{Z}$ \end_inset and \begin_inset Formula \[ f\left(s_{t},\ldots f\left(s_{2},f\left(s_{1},Z_{0}\right)\right)\ldots\right )=f^{*}=\textrm{const}\] \end_inset \layout Standard for all comp. seqs. \begin_inset Formula $ S=(s_{i})\in\mathcal{S}(G)$ \end_inset of \begin_inset Formula $ G$ \end_inset . \layout Slide Algorithm \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash head{ \end_inset The Algorithm \begin_inset ERT status Collapsed \layout Standard } \end_inset \layout Standard \begin_inset Formula $ \qquad $ \end_inset input \begin_inset Formula $ G\ldots\textrm{a graph}$ \end_inset \layout Standard \begin_inset Formula $ \qquad $ \end_inset input \begin_inset Formula $ T\ldots\textrm{a decomposition formula}$ \end_inset \layout Standard \begin_inset Formula $ \qquad $ \end_inset compute some c.s. \begin_inset Formula $ S(G)=(s_{i})$ \end_inset \layout Standard \begin_inset Formula $ \qquad $ \end_inset set \begin_inset Formula $ Z_{0}=\{ ([\emptyset ,0],1)\} $ \end_inset \layout Standard \begin_inset Formula $ \qquad $ \end_inset for \begin_inset Formula $ i$ \end_inset from \begin_inset Formula $ 1$ \end_inset to \begin_inset Formula $ t$ \end_inset do \layout Standard \begin_inset Formula $ \qquad $ \end_inset \begin_inset Formula $ \qquad $ \end_inset set \begin_inset Formula $ Z_{i}=\textrm{collect}\left(f(s_{i},Z_{i-1})\right)$ \end_inset \layout Standard \begin_inset Formula $ \qquad $ \end_inset output \begin_inset Formula $ \sum_{ ((\pi ,d),w)\in Z_{t}}r(d)\, w$ \end_inset \layout Standard collection step is crucial for performance \layout Slide \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash head{ \end_inset Correctness of Algorithm \begin_inset ERT status Collapsed \layout Standard } \end_inset \layout Standard \begin_inset FormulaMacro \newcommand{\GX}{G\textsl{:}X} \end_inset \layout Standard apply decomposition formula repeatedly: \begin_inset Formula \[ R(G)=\sum_{ X\subset E}\lyxlock r\left(k(\GX )\right)\, p(X)\] \end_inset \begin_inset Formula $ k(\GX )\ldots $ \end_inset # of conn. comp. of \begin_inset Formula $ \GX =(V,X)$ \end_inset \layout Standard \begin_inset Formula $ p_{E}(X)\ldots $ \end_inset \begin_inset Formula $ \prod_{ e\in X}\lyxlock a(e)\times\prod_{ e\in E\setminus X}\lyxlock b(e)$ \end_inset \layout Standard define: \layout Standard \begin_inset Formula $ \textrm{ind}\lyxlock_{ A}\lyxlock X\, :=\, [A\cap\GX ,k(\GX )]$ \end_inset for \begin_inset Formula $ A\subset V$ \end_inset , \begin_inset Formula $ X\subset E$ \end_inset \layout Standard reorder sum: \layout Standard \begin_inset Formula \[ R(G)=\sum_{ [\pi ,d]}r(d)\sum_{ X\subset E:\textrm{ind}\lyxlock_{ A}\lyxlock X=[\pi ,d]}\lyxlock p_{E}(X)\] \end_inset \layout Standard \begin_inset Formula \[ \textrm{desc}\lyxlock_{ A}\lyxlock (G):=\left\{ \left([\pi ,d],\sum_{ X\subset E:\textrm{ind}\lyxlock_{ A}\lyxlock X=[\pi ,d]}\lyxlock p_{E}(X)\right)\right\} \] \end_inset \layout Standard \begin_inset Formula \[ R(G)=\sum_{ ([\pi ,d],w)\in\textrm{desc}\lyxlock_{ A}\lyxlock (G)}\lyxlock r(d)\, w\] \end_inset \layout Slide Lemma \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash head{ \end_inset \begin_inset ERT status Collapsed \layout Standard } \end_inset \layout Standard \begin_inset Formula $ G_{i}=(V_{i},E_{i})$ \end_inset , \begin_inset Formula $ A_{i}\ldots $ \end_inset \begin_inset Formula $ i^{\textrm{th}}$ \end_inset active node set: \layout Standard \series bold Lemma: \series default \begin_inset Formula $ Z_{i}=\textrm{desc}\lyxlock_{ A_{i}}(G_{i})$ \end_inset \layout Standard proof by induction: \layout Standard start clear \layout Standard assuming \begin_inset Formula $ Z_{i-1}=\textrm{desc}_{A_{i-1}}(G_{i-1})$ \end_inset \layout Standard distinguish three cases \begin_inset Formula $ c_{i}\in\{ A,K,D\} $ \end_inset \layout Standard build \begin_inset Formula $ Z_{i}$ \end_inset according to algo \layout Standard transform this to \begin_inset Formula $ \textrm{desc}_{A_{i}}(G_{i})$ \end_inset . \layout Slide \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash head{ \end_inset Complexity of Algorithm \begin_inset ERT status Collapsed \layout Standard } \end_inset \layout Standard \begin_inset Formula $ S\in\mathcal{S}(G)$ \end_inset of width \begin_inset Formula $ p$ \end_inset , \layout Standard \begin_inset Formula $ T=(a,b,r)$ \end_inset decomposition formula \layout Standard \begin_inset Formula $ O(\omega (n))$ \end_inset elementary operation on \begin_inset Formula $ \mathcal{W}$ \end_inset \layout Standard \begin_inset Formula $ O(n+m)$ \end_inset iterations in the outer loop \layout Standard \begin_inset Formula $ B(p)\, (n+1)=O(n)$ \end_inset different indices \layout Standard \begin_inset Formula $ O(n)$ \end_inset different states \layout Standard \begin_inset Formula $ O(\omega )$ \end_inset for transforming one state \layout Standard \begin_inset Formula $ O(n\,\log n)$ \end_inset to sort the stateset \layout Standard \begin_inset Formula $ O(n\,\omega )$ \end_inset to collapse states with identical index \layout Standard \begin_inset Formula $ O((n+m)\, n\, (\log n+\omega ))$ \end_inset total \layout Standard with \begin_inset Formula $ \omega =O(1)$ \end_inset and \begin_inset Formula $ n=O(m)$ \end_inset : \begin_inset Formula $ O(n^{2}\,\log n)$ \end_inset . \layout Slide Example Negami \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash head{ \end_inset Negami polynomial \begin_inset ERT status Collapsed \layout Standard } \end_inset \begin_inset Formula \begin{eqnarray*} N(G) & = & x\, R(G_{e})+y\, R(G_{-e})\\ N(\overline{K_{n}}) & = & t^{n} \end{eqnarray*} \end_inset \begin_inset Formula \[ \begin{array}{crrr} p & \#\textrm{total} & \#\textrm{max} & \textrm{time}\\ 6 & 125.898 & 4.770 & 0:05\\ 7 & 790.878 & 22.760 & 1:03\\ 8 & \quad\quad 4.078.059 & \quad 93.252 & \quad 17:04\end{array} \] \end_inset manually improved algorithm: \layout Standard \begin_inset Formula \[ \begin{array}{crrr} p & \#\textrm{total} & \#\textrm{max} & \textrm{time}\\ 6 & 10.087 & 264 & 0:04\\ 7 & 44.032 & 858 & 0:40\\ 8 & \quad\quad 179.910 & \quad 2.860 & \quad 5:30\end{array} \] \end_inset \layout Standard Negami leads to Tutte \layout Standard Tutte leads to chromatic polynomial etc. \layout Slide \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash head{ \end_inset All-terminal reliability \begin_inset ERT status Collapsed \layout Standard } \end_inset \begin_inset Formula \begin{eqnarray*} R(G) & = & p_{e}\, R(G_{e})+(1-p_{e})\, R(G_{-e})\\ R(\overline{K_{0}}) & = & R(\overline{K_{1}})\: =\: 1\\ R(\overline{K_{n}}) & = & 0\quad\textrm{ if }n>1 \end{eqnarray*} \end_inset \begin_inset Formula \[ \begin{array}{crrrr} p & \textrm{\# total} & \textrm{\# max} & \textrm{time} & \textrm{result}\\ 9 & 745.202 & 9.724 & 0:03 & 1.58e-5\\ 10 & 3.092.058 & 33.592 & 0:12 & 2.24e-6\\ 11 & 12.734.918 & 117.572 & 0:52 & 2.27e-7\\ 12 & 53.276.048 & 416.024 & 4:22 & 2.85e-8\\ 13 & 218.954.187 & 1.485.800 & 20:36 & 2.46e-9\\ 14 & \quad 917.861.182 & \quad 5.348.880 & \quad 95:50 & \quad 1.97e-10\end{array} \] \end_inset \layout Standard manual improvements possible \layout Standard approximations possible \layout Slide \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash head{ \end_inset Conclusion \begin_inset ERT status Collapsed \layout Standard } \end_inset \layout Standard - very easy to implement \layout Standard - decent starting point for manual optimization \newline if performance crucial \layout Standard - some special graph structures are handled \newline automatically (e.g.\SpecialChar ~ for planar graphs, only \newline non-crossing partitions are created) \layout Standard - easily generalizable to more complex \newline decomposition formulae, splitting formulae \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash iffalse \end_inset \layout Standard Let \begin_inset Formula $ G=(V,E)$ \end_inset a graph. If we apply \begin_inset LatexCommand \ref{eq:decomp} \end_inset repeatedly, we end up with a sum of the form \begin_inset Formula \begin{equation} R(G)=\sum_{ X\subset E}\lyxlock r\left(k(G:X)\right)\, p(X)\label{eq:fulldecomp}\end{equation} \end_inset with \begin_inset Formula $ k(G:X)$ \end_inset denoting the number of connected components of \begin_inset Formula $ G:X=(V,X)$ \end_inset and \begin_inset Formula $ p_{E}(X)$ \end_inset being some abbreviation for \begin_inset Formula $ \prod_{ e\in X}\lyxlock a(e)\times\prod_{ e\in E\setminus X}\lyxlock b(e)$ \end_inset . \layout Standard Let us fix some subset \begin_inset Formula $ A$ \end_inset of \begin_inset Formula $ V$ \end_inset . We call the index \begin_inset Formula $ [\pi ,d]$ \end_inset \emph on induced by \emph default \begin_inset Formula $ X$ \end_inset \emph on in \emph default \begin_inset Formula $ A$ \end_inset (written as \begin_inset Formula $ [\pi ,d]=\textrm{ind}\lyxlock_{ A}\lyxlock X$ \end_inset ) if there are \begin_inset Formula $ d$ \end_inset connected components in \begin_inset Formula $ G_{X}\lyxlock $ \end_inset and the blocks of \begin_inset Formula $ \pi $ \end_inset correspond to the intersection of \begin_inset Formula $ A$ \end_inset with \begin_inset Formula $ G_{X}\lyxlock $ \end_inset . By collecting terms of ( \begin_inset LatexCommand \ref{eq:fulldecomp} \end_inset ) into blocks with the same induced index we obtain: \layout Standard \begin_inset Formula \begin{equation} R(G)=\sum_{ [\pi ,d]}r(d)\sum_{ X\subset E:\textrm{ind}\lyxlock_{ A}\lyxlock X=[\pi ,d]}\lyxlock p_{E}(X)\label{eq:fulldecomp2}\end{equation} \end_inset \layout Standard By introducing \begin_inset Formula \begin{equation} \textrm{desc}\lyxlock_{ A}\lyxlock (G):=\left\{ \left([\pi ,d],\sum_{ X\subset E(G):\textrm{ind}\lyxlock_{ A}\lyxlock X=[\pi ,d]}\lyxlock p_{E(G)}(X)\right)\right\} \label{eq:desc}\end{equation} \end_inset \layout Standard ( \begin_inset LatexCommand \ref{eq:fulldecomp2} \end_inset ) can be written as: \begin_inset Formula \[ R(G)=\sum_{ ([\pi ,d],w)\in\textrm{desc}\lyxlock_{ A}\lyxlock (G)}\lyxlock r(d)\, w\] \end_inset \layout Standard With \begin_inset Formula $ G_{i}=(V_{i},E_{i})$ \end_inset being the subgraph of \begin_inset Formula $ G$ \end_inset which consists of all nodes activated and edges handled in the first \begin_inset Formula $ i$ \end_inset steps of \begin_inset Formula $ S$ \end_inset and \begin_inset Formula $ A_{i}$ \end_inset the \begin_inset Formula $ i^{\textrm{th}}$ \end_inset active node set we are prepared to state the following lemma: \layout Standard \series bold Lemma: \series default The stateset \begin_inset Formula $ Z_{i}$ \end_inset after step \begin_inset Formula $ i$ \end_inset equals \begin_inset Formula $ \textrm{desc}\lyxlock_{ A_{i}}(G_{i})$ \end_inset . \layout Standard Proof sketch: We will can show this lemma by induction. In the beginning we have \begin_inset Formula $ A_{0}=\emptyset $ \end_inset and and empty graph \begin_inset Formula $ G_{0}$ \end_inset with zero connected components. Consequently there is only a single index \begin_inset Formula $ [\emptyset ,0]$ \end_inset , and the products in ( \begin_inset LatexCommand \ref{eq:fulldecomp2} \end_inset ) both range over empty sets, so their value is \begin_inset Formula $ 1$ \end_inset . This coincides with the initial stateset \begin_inset Formula $ Z_{0}\lyxlock =\{ [\emptyset ,0],1\} $ \end_inset as used by the algorithm. \layout Standard Case \begin_inset Formula $ s_{i}=(v,A)$ \end_inset (activation step of node \begin_inset Formula $ v$ \end_inset ): Let \begin_inset Formula $ Z_{i-1}$ \end_inset be the state set before step \begin_inset Formula $ i$ \end_inset was executed. As the algorithm according to ( \begin_inset LatexCommand \ref{eq:fA} \end_inset ) transforms a single state \begin_inset Formula $ ([\pi ,d],w)$ \end_inset into \begin_inset Formula $ ([\pi |w,d+1],w)$ \end_inset we have \layout Standard \begin_inset Formula \begin{eqnarray*} Z_{i}\lyxlock & = & \left\{ \left([\pi |v,d+1],\sum_{ X\subset E_{i-1}:\textrm{ind}\lyxlock_{ A_{i-1}}\lyxlock X=[\pi ,d]}\lyxlock p_{E_{i-1}}(X)\right)\right\} \end{eqnarray*} \end_inset The freshly activated node \begin_inset Formula $ v$ \end_inset forms a new connected component of its own in \begin_inset Formula $ G_{i}$ \end_inset as no edge connecting it to any other node in \begin_inset Formula $ G_{i}$ \end_inset could have been handled earlier according to restriction ( \begin_inset LatexCommand \ref{eq:restriction2} \end_inset ). So for \begin_inset Formula $ X\subset E_{i-1}(=E_{i})$ \end_inset with \begin_inset Formula $ \textrm{ind}\lyxlock_{ A_{i-1}}\lyxlock X=[\pi ,d]$ \end_inset , we have \begin_inset Formula $ \textrm{ind}\lyxlock_{ A_{i}}\lyxlock X=[\pi |v,d+1]$ \end_inset and vice versa. Thus \begin_inset Formula \begin{eqnarray*} Z_{i}\lyxlock & = & \left\{ \left([\pi |v,d+1],\sum_{ X\subset E_{i}:\textrm{ind}\lyxlock_{ A_{i}}\lyxlock X=[\pi |v,d+1]}\lyxlock p_{E_{i}}(X)\right)\right\} \end{eqnarray*} \end_inset \layout Standard and by renaming \begin_inset Formula $ \pi |v\mapsto\pi $ \end_inset and \begin_inset Formula $ d+1\mapsto d$ \end_inset and using ( \begin_inset LatexCommand \ref{eq:desc} \end_inset ) we find \begin_inset Formula $ Z_{i}=\textrm{desc}\lyxlock_{ A_{i}}(G_{i})$ \end_inset . The final collection step won't change anything as there are no states with the same index in that set. \layout Standard Case \begin_inset Formula $ s_{i}=(e,E)$ \end_inset (edge step of edge \begin_inset Formula $ e=(uv)$ \end_inset ): Again, let \begin_inset Formula $ Z_{i-1}$ \end_inset be the state set before step \begin_inset Formula $ i$ \end_inset was executed. \layout Standard The algorithm transforms a single state \begin_inset Formula $ ([\pi ,d],w)$ \end_inset into a pair of states \begin_inset Formula $ ([\pi_{ (uv)},d-1_{\pi^{ u}\neq\pi^{ v}}],a(e)\, w)$ \end_inset and \begin_inset Formula $ ([\pi ,d],b(e)\, w)$ \end_inset according to ( \begin_inset LatexCommand \ref{eq:fE} \end_inset ) and consequently we have: \begin_inset Formula \begin{eqnarray*} Z_{i}\lyxlock & = & \left\{ \left([\pi_{ (uv)},d-1_{\pi^{ u}\neq\pi^{ v}}],a(e)\cdot\sum_{ X\subset E_{i-1}:\textrm{ind}\lyxlock_{ A_{i-1}}\lyxlock X=[\pi ,d]}\lyxlock p_{E_{i-1}}(X)\right)\right\} \\ & & \bigcup\left \{ \left([\pi ,d],b(e)\cdot\sum_{ X\subset E_{i-1}:\textrm{ind}\lyxlock_{ A_{i-1}}\lyxlock X=[\pi ,d]}\lyxlock p_{E_{i-1}}(X)\right)\right\} \end{eqnarray*} \end_inset \layout Standard It is easy to see that the following holds: \layout Standard \begin_inset Formula \begin{eqnarray} b(e)\cdot\!\!\!\!\!\sum_{\substack{ X\subset E_{i-1}:\\ \textrm{ind}\lyxlock_{ A_{i-1}}\lyxlock X=[\pi ,d]} }\lyxlock \!\!\!\!\! p_{E_{i-1}}(X) & =\!\!\!\!\! & \sum_{\substack{ X\subset E_{i}:e\notin X\\ \land\textrm{ind}\lyxlock_{ A_{i}}\lyxlock X=[\pi ,d]} }\lyxlock \!\!\!\!\! p_{E_{i}}(X)\label{eq:trans1} \end{eqnarray} \end_inset \layout Standard Furthermore, if \begin_inset Formula $ X\subset E_{i-1}$ \end_inset with \begin_inset Formula $ \textrm{ind}\lyxlock_{ A_{i-1}}\lyxlock X=[\pi ,d]$ \end_inset , we have \begin_inset Formula $ \textrm{ind}\lyxlock_{ A_{i}}\lyxlock X=[\pi ,d]$ \end_inset (since \begin_inset Formula $ A_{i-1}=A_{i}$ \end_inset ), \begin_inset Formula $ \textrm{ind}\lyxlock_{ A_{i}}\lyxlock (X\cup\{ e\} )=[\pi_{ (uv)},d^{'}]$ \end_inset (with \begin_inset Formula $ d^{'}=d-1_{\pi^{ u}\neq\pi^{ v}}$ \end_inset ) and \begin_inset Formula $ a(e)\, P_{E_{i-1}}(X)=P_{E_{i}}(X\cup\{ e\} )$ \end_inset . So \begin_inset Formula \begin{eqnarray} \left([\pi_{ (uv)},d^{'}],a(e)\cdot\!\!\!\!\!\!\!\sum_{\substack{ X\subset E_{i-1}:\\ \textrm{ind}\lyxlock_{ A_{i-1}}\lyxlock X=[\pi ,d]} }\lyxlock \!\!\!\!\!\!\! p_{E_{i-1}}(X)\right) & = & \left([\pi ,d],\!\!\!\!\!\!\!\sum_{\substack{ X\subset E_{i}:e\in X\\ \land\textrm{ind}\lyxlock_{ A_{i}}\lyxlock X=[\pi ,d]} }\lyxlock \!\!\!\!\!\!\! p_{E_{i}}(X)\right)\label{eq:trans2} \end{eqnarray} \end_inset \layout Standard holds. Using ( \begin_inset LatexCommand \ref{eq:trans1} \end_inset ) and ( \begin_inset LatexCommand \ref{eq:trans2} \end_inset ) we are done: \layout Standard \begin_inset Formula \begin{eqnarray*} Z_{i} & = & \left\{ \left([\pi ,d],\sum_{\substack{ X\subset E_{i}:e\in X\\ \land\textrm{ind}\lyxlock_{ A_{i}}\lyxlock X=[\pi ,d]} }\lyxlock p_{E_{i}}(X)\right)\right\} \bigcup\left \{ \left([\pi ,d],\sum_{\substack{ X\subset E_{i}:e\notin X\\ \land\textrm{ind}\lyxlock_{ A_{i}}\lyxlock X=[\pi ,d]} }\lyxlock p_{E_{i}}(X)\right)\right\} \\ & = & \left\{ \left([\pi ,d],\sum_{ X\subset E_{i}:\textrm{ind}\lyxlock_{ A_{i}}\lyxlock X=[\pi ,d]}\lyxlock p_{E_{i}}(X)\right)\right\} \, =\,\textrm{desc}\lyxlock_{ A_{i}}(G_{i}) \end{eqnarray*} \end_inset Case \begin_inset Formula $ s_{i}=(v,D)$ \end_inset (deactivation step of node \begin_inset Formula $ v$ \end_inset ): According to ( \begin_inset LatexCommand \ref{eq:fD} \end_inset ) we have \begin_inset Formula \begin{eqnarray} Z_{i}\lyxlock & = & \left\{ \left([\pi -v,d],\sum_{ X\subset E_{i-1}:\textrm{ind}\lyxlock_{ A_{i-1}}\lyxlock X=[\pi ,d]}\lyxlock p_{E_{i-1}}(X)\right)\right\} .\label{eq:deact} \end{eqnarray} \end_inset Given some \begin_inset Formula $ X\subset E_{i-1}:\textrm{ind}\lyxlock_{ A_{i-1}}\lyxlock X=[\pi ,d]$ \end_inset we have \begin_inset Formula $ \textrm{ind}\lyxlock_{ A_{i}}\lyxlock X=[\pi -v,d]$ \end_inset since \begin_inset Formula $ A_{i}=A_{i-1}\setminus\{ v\} $ \end_inset . Using \begin_inset Formula $ E_{i}=E_{i-1}$ \end_inset we obtain from ( \begin_inset LatexCommand \ref{eq:deact} \end_inset ) immediately \begin_inset Formula $ Z_{i}=\textrm{desc}_{A_{i}}G_{i}$ \end_inset . \begin_inset ERT status Collapsed \layout Standard \backslash fi \end_inset \the_end
