\documentstyle[jair,twoside,11pt,theapa]{article}
\jairheading{12}{2000}{219-234}{5/99}{5/00}
\ShortHeadings{Randomized Algorithms for the Loop Cutset Problem}
{Becker, Bar-Yehuda, \& Geiger}
\firstpageno{219}
%\documentstyle[jair,epsf,psfig,theapa]{article}
%\documentstyle[proceed,epsf,psfig]{article}
%\documentstyle[proceed,psfig]{article}
%\topmargin 0.25in

\newtheorem{theorem}{Theorem}
\newenvironment{definition}{\vspace{1ex}\noindent\bf
Definition \begin{em}}{\end{em}}
\newtheorem{fact}{Fact}
\newtheorem{assumption}{Assumption}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\vin}{v_{\mbox{\tiny in}}}
\newcommand{\vout}{v_{\mbox{\tiny out}}}
\newcommand{\invi}{I^{\mbox{\tiny -1}}}
\newcommand{\Erdos}{Erd\H{o}s}
\newcommand{\Posa}{P\'osa}
\newcommand{\Lovasz}{Lov\'asz}
\newcommand{\Realfield}{{\mathrm I\!R}}
\newcommand{\degree}{{\Delta}}
\newcommand{\weight}{{w}}
\newcommand{\constweight}{{1}}
\newcommand{\deff}{\stackrel{\Delta}{=}}
\newcommand{\mod}{{\rm mod}}
\newcommand{\Eq}[1]{(\ref{#1})}
\newcommand{\qed}{\hspace*{\fill}%
\vbox{\hrule\hbox{\vrule\squarebox{.667em}\vrule}\hrule}\smallskip}
\def\squarebox#1{\hbox to #1{\hfill\vbox to #1{\vfill}}}
\newcommand{\clauseend}{\hspace*{\fill}\mbox{$\bullet$}}

\newcommand{\Max}{\mbox{\it Max}}
\input epsf %% at top of file
\input{eepic.sty}
%\input{eps.sty}
%\renewcommand{\baselinestretch}{0.93}

\begin{document}

\title{Randomized Algorithms for the Loop Cutset Problem}

\author{{\normalsize\bf Ann Becker} {\hfill\small\sc  anyuta@cs.technion.ac.il}\\
{\normalsize\bf Reuven Bar-Yehuda} {\hfill\small\sc reuven@cs.technion.ac.il} \\
% didn't work \name Dan Geiger \email dang@cs.technion.ac.il\\
{\normalsize\bf Dan Geiger} {\hfill\small\sc dang@cs.technion.ac.il}\\
        \addr Computer Science Department \\
        Technion, Haifa, 32000, Israel}

% For research notes, remove the comment character in the line below.
% \researchnote

\maketitle

\begin{abstract}

We show how to find a minimum weight loop cutset in a 
Bayesian network with high probability. Finding such a loop cutset is
the first step in the method of conditioning for inference.
Our randomized algorithm for finding a loop cutset
outputs a minimum 
loop cutset after $O(c \, 6^{k} k n)$ steps
with probability at least $1- (1-\frac{1}{6^k})^{c6^k}$,
where $c > 1$ is a constant specified by the user,
$k $ is the minimal size of a minimum weight loop cutset,
and $n$ is the number of vertices.
We also show empirically that a variant of this algorithm
often finds a loop cutset that is closer to
the minimum weight loop cutset than the ones found
by the best deterministic algorithms known.
\end{abstract}



\section{Introduction}
\label{introduction}

The method of conditioning is a
well known inference method for the computation
of posterior probabilities in general Bayesian networks
\cite{pearl86,pearl88,suermondt90,PS91}
as well as for finding MAP values and 
solving constraint satisfaction problems
\cite{De99}.
This method has two conceptual phases. 
First to find an optimal or close to optimal loop cutset
and then to perform 
a likelihood computation for each instance of the variables
in the loop cutset.
This method is routinely used by geneticists
via several genetic linkage programs \cite{ott91,La97,becker98}.
A variant of this method was developed by 
Lange and Elston (1975).  %\cite{lange75}.

Finding a minimum weight loop cutset
is NP-complete and thus heuristic methods
have often been applied to find a reasonable loop cutset 
\cite{suermondt90}.
Most methods in the past had no guarantee of performance and
performed very badly when presented with an appropriate example. 
Becker and Geiger (1994, 1996) %\cite{becker94,becker96}
offered an algorithm that finds a loop cutset for which
the logarithm of the state space is guaranteed
to be at most a constant factor off the optimal value.
An adaptation of these approximation algorithms has been included
in version 4.0 of {\sc FASTLINK}, a popular software
for analyzing large pedigrees with small number of genetic markers
\cite{becker98}.  Similar algorithms
in the context of undirected graphs are described by
Bafna, Berman, and Fujito (1995) 
and Fujito (1996).  % \cite{bafna95,fujito96}

While approximation algorithms for the loop cutset problem
are quite useful, it is still worthwhile to invest in finding a minimum 
loop cutset rather than an approximation because the cost of finding
such a loop cutset is amortized over the many 
iterations of the conditioning method. 
In fact, one may invest an effort of complexity exponential
in the size of the loop cutset
in finding a minimum weight loop cutset because
the second phase of the conditioning algorithm, which is repeated 
for many iterations, uses a procedure of such complexity.
The same considerations apply also to constraint satisfaction problems
as well as other problems in which the method
of conditioning is useful \cite{dechter90,De99}.

In this paper we describe several randomized algorithms 
that compute a loop cutset.
As done by Bar-Yehuda, Geiger, Naor, and Roth (1994),
% \cite{baryehuda94}
our solution is based on
a reduction to the weighted feedback vertex
set problem. 
A {\em feedback vertex set (FVS)} $F$ is a set of vertices of an undirected
graph $G =(V,E)$ such that by removing $F$ from $G$, along with 
all the edges incident with $F$, a set of trees is obtained. 
The {\em Weighted Feedback Vertex Set (WFVS) problem} is to find 
a feedback vertex set $F$ of 
a vertex-weighted graph with a weight function $w: V \rightarrow \Realfield^+$, 
such that $\sum_{v \in F}  w(v)$ is minimized. When $w(v) \equiv 1$, 
this problem is called the FVS problem. The decision version 
associated with the FVS problem is known to be 
NP-Complete~\cite[pp.~191--192]{garey79}. 

Our randomized algorithm for finding a WFVS, 
called {\sc RepeatedWGuessI}, outputs a minimum 
weight FVS after $O(c\, 6^{k} k n)$ steps
with probability at least $1- (1-\frac{1}{6^k})^{c6^k}$,
where $c > 1$ is a constant specified by the user,
$k $ is the minimal size of a minimum weight FVS, 
and $n$ is the number of vertices.
For unweighted graphs we present an algorithm that finds a minimum 
FVS of a graph $G$ after $O(c\, 4^k k n)$ steps
with probability at least $1- (1-\frac{1}{4^k})^{c4^k}$.
In comparison, several deterministic algorithms for finding a minimum 
FVS are described in the literature. 
One has a complexity $O((2k+1)^k n^2)$ \cite{downey95a}
and others have a complexity $O((17k^4)! n)$ 
\cite{bodlaender90,downey95b}.

A final variant of our randomized algorithms, called WRA,
has the best performance because it utilizes information
from previous runs.  This algorithm is harder to analyze and
its investigation is mostly experimental.
We show empirically that the actual run time of WRA
is comparable to a Modified Greedy Algorithm  (MGA), 
described by Becker and Geiger (1996), %\cite{becker96}, 
which is the best available deterministic algorithm for finding
close to optimal loop cutsets, and yet, the output of WRA 
is often closer to the minimum weight loop cutest
than the output of MGA.

The rest of the paper is organized as follows.
In Section~\ref{directedcyclecover}
we outline the method of conditioning,
explain the related loop cutset problem
and describe the reduction from the loop cutset
problem to the WFVS Problem.
In Section~\ref{sec-WFVS} we present three randomized algorithms
for the WFVS problem and their analysis. 
In Section~\ref{sec-experiments} we compare experimentally
WRA and MGA with respect to output quality and run time. 


\section{Background: The Loop Cutset Problem}
\label{directedcyclecover}

A short overview of the method of conditioning
and definitions related to Bayesian networks
are given below.  See the book by Pearl (1988)
%\cite{pearl88} 
for more details.
We then define the loop cutset problem.

Let $P(u_1, \ldots, u_n)$ be a probability distribution 
where each variable $u_i$ has a finite set of possible values
called the {\em domain of $u_i$}.
A directed graph $D$ with no directed cycles
is called a {\em Bayesian network of $P$} if there is a 1--1
mapping between $\{u_1,\ldots, u_n\}$
and vertices in $D$, such that $u_i$ is associated with vertex $i$ 
and $P$ can be written as follows:
\begin{equation}
P(u_1, \ldots, u_n)= \prod_{i=1}^n P(u_i \mid u_{i_1}, \ldots, u_{i_{j(i)}})
\label{product}
\end{equation}
where $i_1, \ldots, i_{j(i)}$ are the source vertices
of the incoming edges to vertex $i$ in $D$.

Suppose now that some variables $\{v_1, \ldots, v_l\}$
among $\{u_1, \ldots, u_n\}$ are assigned specific values
$\{ {\mathbf v}_1, \ldots, {\mathbf v}_l \}$ respectively. 
The {\em updating problem}
is to compute the probability 
$P(u_i \mid v_1 = {\mathbf v}_1, \ldots, v_l = {\mathbf v}_l)$
for $i=1,\ldots,n$.

A {\em trail} in a Bayesian network is a subgraph
whose underlying graph is a simple path. 
A vertex $b$ is called a
{\em sink} with respect to a trail $t$ if there exist two
consecutive edges $a \rightarrow b$ and $b \leftarrow c$
on $t$. A trail $t$ is 
{\em active by a set of vertices $Z$} if (1)
every sink with respect to $t$
either is in $Z$ or has a descendant in $Z$ and (2) every other vertex
along $t$ is outside $Z$. Otherwise, the trail is said to be 
{\em blocked (d-separated)} by $Z$.

Verma and Pearl proved that if
$D$ is a Bayesian network of $P(u_1, \ldots, u_n)$
and all trails between a vertex in
$\{r_1, \ldots, r_l\}$ and a vertex in
$\{s_1, \ldots, s_k\}$ 
are blocked by $\{t_1, \ldots, t_m\}$, then 
the corresponding sets of variables $\{u_{r_1}, \ldots, u_{r_l}\}$
and $\{u_{s_1}, \ldots, u_{s_k}\}$ are independent
conditioned on $\{u_{t_1}, \ldots, u_{t_m}\}$~\cite{verma88}.
Furthermore, Geiger and Pearl proved that this result
cannot be enhanced~\cite{geiger90uai}.
Both results were presented and extended 
by Geiger, Verma, and Pearl (1990).  %in \cite{geiger90network}.

Using the close relationship between blocked trails and
conditional independence, Kim and Pearl developed 
an algorithm {\sc update-tree} that solves the updating problem on
Bayesian networks in which every two vertices are connected 
with at most one trail \cite{kim83}.
Pearl then solved the updating problem on any Bayesian network
as follows \cite{pearl86}. 
First, a set of vertices $S$ is selected such that
any two vertices in the network are connected by at most one 
{\em active} trail in $S \cup Z$, where $Z$ is any subset of
vertices. Then, {\sc update-tree} is applied once for each 
combination of value assignments to the variables corresponding to
$S$, and, finally, the results are combined. 
This algorithm is called the method of {\em conditioning} 
and its complexity grows exponentially with the size of $S$.
The set $S$ is called a {\em loop cutset}.
Note that
when the domain size of the variables varies,
then {\sc update-tree} is called a number of times equal to
the product of the domain sizes of the variables
whose corresponding vertices participate in the loop cutset. 
If we take the logarithm of the domain size (number of values)
as the weight of a vertex, 
then finding a loop cutset such that the sum of its vertices
weights is minimum optimizes Pearl's updating algorithm
in the case where the domain sizes may vary.

We now give an alternative definition for a loop cutset $S$ and
then provide a probabilistic algorithm for finding it.
This definition is borrowed from a paper by
Bar-Yehuda et al.\ (1994).  % \cite{baryehuda94}.
The underlying graph $G$ of a directed graph $D$ is
the undirected graph formed by ignoring the
directions of the edges in $D$. 
A {\em cycle\/} in $G$ is a path whose two terminal 
vertices coincide. 
A {\em loop} in $D$
is a subgraph of $D$ whose underlying graph is a cycle. 
A vertex $v$ is a {\em sink} with respect to a loop $\Gamma$ if 
the two edges adjacent to $v$ in $\Gamma$ are directed into $v$.
Every loop must contain at least one vertex that is not a
sink with respect to that loop.
Each vertex that is not a sink with respect to a loop $\Gamma$
is called an {\em allowed vertex with respect to $\Gamma$}.
A {\em loop cutset} of a directed graph $D$
is a set of vertices that contains at least one
allowed vertex with respect to each loop in $D$.
The weight of a set of vertices $X$
is denoted by $w(X)$ and is equal to $\sum_{v \in X} w(v)$
where $w(x) = \log(|x|)$ and
$|x|$ is the size of the domain associated with vertex $x$.
A {\em minimum weight loop cutset}
of a weighted directed graph $D$ is
a loop cutset $F^*$ of $D$ for which $w(F^*)$
is minimum over all loop cutsets of $G$. 
The {\em Loop Cutset
Problem\/} is defined as finding 
a minimum weight loop cutset of a given weighted directed graph $D$.

The approach we take is to reduce the 
loop cutset problem to the weighted feedback vertex set
problem, as done by Bar-Yehuda et al.\ (1994). %\cite{baryehuda94}
We now define the weighted feedback vertex set problem
and then the reduction.

Let $G=(V,E)$ be an undirected graph, and let
$\weight : V \rightarrow \Realfield^+$ 
be a weight function on the vertices of $G$.
A {\em feedback vertex set\/} of $G$
is a subset of vertices $F \subseteq V$
such that each cycle in $G$ passes through at least one vertex in $F$.
In other words, a feedback vertex set $F$ is a set of vertices of $G$
such that
by removing $F$ from $G$, along with all the edges incident
with $F$, we obtain a set of trees (i.e., a forest). 
The weight of a set of vertices $X$
is denoted (as before) by $w(X)$ and is equal to $\sum_{v \in X} w(v)$.
A {\em minimum feedback vertex set}
of a weighted graph $G$ with a weight function $\weight$ is 
a feedback vertex set $F^*$ of $G$ for which $w(F^*)$
is minimum over all feedback vertex sets of $G$. 
The {\em Weighted Feedback Vertex Set (WFVS) 
Problem\/} is defined as finding 
a minimum feedback vertex set of a given weighted graph $G$
having a weight function $\weight$.

The reduction is as follows.
Given a weighted directed graph $(D,w)$ (e.g., a Bayesian
network), we define the {\em splitting\/} 
weighted undirected graph $D_s$ with a weight function
$w_s$ as follows.
Split each vertex $v$ in $D$ into two 
vertices $\vin$ and $\vout$ in $D_s$ such that
all incoming edges to $v$ in $D$ become undirected 
incident edges with $\vin$ in $D_s$, and
all outgoing edges from $v$ in $D$ become undirected incident 
edges with $\vout$ in $D_s$.
In addition, connect $\vin$ and $\vout$ in $D_s$ 
by an undirected edge. Now set 
$w_s(\vin)= \infty$ and $w_s(\vout) = w(v)$.
For a set of vertices $X$ in $D_s$, we define 
$\psi(X)$ as the set obtained by replacing each 
vertex $\vin$ or $\vout$ in $X$ by the respective vertex $v$
in $D$ from which these vertices originated.
Note that if $X$ is a cycle in $D_s$, then
$\psi(X)$ is a loop in $D$, and if $Y$ is a loop in $D$,
then $\psi^{-1}(Y) = \bigcup_{v \in Y} \psi^{-1}(v)$
is a cycle in $D_s$ where
\[
\psi^{-1}(v) =  \left\{ 
\begin{array}{ll} 
\vin & \mbox{$v$ is a sink on $Y$}\\
\vout & \mbox{$v$ is a source on $Y$}\\
\{\vin, \vout\} & \mbox{otherwise}
\end{array}
\right.
\]
(A vertex $v$ is a {\em source} with respect to a loop $Y$ if 
the two edges adjacent to $v$ in $Y$ originate from $v$).
This mapping between loops in $D$ and cycles in $D_s$ is
one-to-one and onto.


Our algorithm can now be easily stated. 


\vspace{2ex}

\noindent
{\bf ALGORITHM LoopCutset }
\begin{tabbing}
xx \= xxxx \= xxx \= xxxxx \= xxxxxx \= \kill
{\bf Input: } {\em A Bayesian network $D$} \\
{\bf Output: } {\em A loop cutset of $D$} \\
\> 1. Construct the splitting graph \( D_{s} \) \\
\> \> with weight function \( w_{s} \) \\
\> 2. Find a feedback vertex set $F$ for \( (D_{s},w_{s}) \)\\
\> \> using the Weighted Randomized Algorithm (WRA) \\
\> 3. Output \( \psi(F) \). \\
\end{tabbing}

It is immediately seen that if {\sc WRA}  (developed in later sections)
outputs a feedback vertex
set $F$ of $D_s$ whose weight is minimum with high probability,
then $\psi(F)$ is a loop cutset of $D$ with minimum weight 
with the same probability.
This observation holds due to the one-to-one and 
onto correspondence between loops in $D$ and cycles in $D_s$
and because WRA never chooses a vertex that has an infinite weight.

\section{Algorithms for the WFVS Problem}
\label{sec-WFVS}

Recall that 
a feedback vertex set of $G$
is a subset of vertices $F \subseteq V$
such that each cycle in $G$ passes through at least one vertex in $F$.
In Section~\ref{sec-random} we address the problem
of finding a FVS with a minimum number of vertices and in 
Sections~\ref{sec-weighted-random} and~\ref{sec-WRA} we address
the problem of finding a FVS with a minimum weight.
Throughout, we allow $G$ to have parallel edges.
If two vertices $u$ and $v$ have parallel edges 
between them, then every FVS of $G$
includes either $u$, $v$, or both.


\subsection{The Basic Algorithms}
\label{sec-random}

In this section we present a randomized algorithm for the FVS problem.
First we introduce some additional terminology and notation.
Let $G=(V,E)$ be an undirected graph.
The degree of a vertex $v$ in $G$, denoted by $d(v)$,
is the number of vertices adjacent to $v$.
A {\em self-loop} is an edge with two endpoints at the same vertex.
A {\em leaf} is a vertex with degree less or equal 1,
a {\em linkpoint} is a vertex with degree 2 and a 
{\em branchpoint} is a vertex with degree strictly higher than 2.
The cardinality of a set $X$ is denoted by $|X|$.

A graph is called {\em rich} if every vertex is a branchpoint
and it has no self-loops.  
Given a graph $G$, by repeatedly removing all leaves,
and bypassing with an edge every linkpoint,
a graph $G'$ is obtained such
that the size of a minimum FVS in $G'$ and in $G$ are 
equal and every minimum FVS of $G'$ 
is a minimum FVS of $G$.
Since every vertex involved in a self-loop belongs 
to every FVS, we can transform $G'$ to
a rich graph $G^r$ by adding the vertices involved in self loops
to the output of the algorithm.

Our algorithm is based on the observation that if we pick
an edge at random from a rich graph there is a
probability of at least $1/2$ that at least one endpoint 
of the edge belongs to any given FVS $F$.
A precise formulation of this claim is given
by Lemma~\ref{edge_lemma} whose proof is given implicitly 
by Voss (1968, Lemma 4).   %in \cite[Lemma 4]{voss68}.

\begin{lemma}
\label{edge_lemma}
Let $G=(V,E)$ be a rich graph, $F$ be a feedback vertex set of $G$
and $X= V \setminus F$. Let $E_X$ denote the set of edges in $E$ 
whose endpoints are all vertices in $X$ and $E_{F,X}$ denote the set of edges
in $G$ that connect vertices in $F$ with vertices in $X$. 
Then, $|E_X| \leq |E_{F,X}|$.
\end{lemma}

\noindent
{\bf Proof. }
The graph obtained by deleting 
a feedback vertex set $F$ of 
a graph $G(V,E)$ is a forest 
with vertices $X= V \setminus F$.
Hence, $|E_X| < |X|$. 
However, each vertex in $X$ is a branchpoint 
in $G$, and so,
\[
3 \, |X| \; \le \;
\sum_{v \in X} d(v) \; = \;
|E_{F,X}| \; + \; 2 \, |E_X|.
\]
Thus, $|E_X| \leq |E_{F,X}|$.
$\Box$

Lemma~\ref{edge_lemma} implies that when picking an edge at random
from a rich graph, it is at least as likely to pick an edge in $E_{F,X}$ 
than an edge in $E_X$. Consequently, selecting a vertex at random from
a randomly selected edge has a probability of at least $1/4$ to belong 
to a minimum FVS.  This idea yields a simple algorithm
to find a FVS.


%spacing

$ $

$ $

$ $

$ $

%spacing

\noindent
{\bf ALGORITHM SingleGuess(G,j)}
\begin{tabbing}
my \= futu \= ref \= irmpo \= larfox \= \kill
%{\bf Input: } {\em An undirected graph $G_0$} \\
%\> \> \> {\em and an integer $j>0$.}\\
{\bf Input: } {\em An undirected graph $G_0$}
{\em and an integer $j>0$.}\\
%{\bf Output: } {\em A feedback vertex set $F$ of size $\leq j$, } \\
%\> \> \> {\em or "Fail" otherwise.} \\
{\bf Output: } {\em A feedback vertex set $F$ of size $\leq j$, }
{\em or "Fail" otherwise.} \\
\> {\bf For } $i=1,\ldots, j$ \\
\>\> 1. Reduce $G_{i-1}$ to a rich graph $G_i$ \\ 
\>\>\> while placing self loop vertices in $F$. \\
\>\> 2. {\bf If} $G_i$ is the empty graph  {\bf Return $F$} \\
\>\> 3. Pick an edge $e=(u,v)$ at random from $E_i$ \\
\>\> 4. Pick a vertex $v_i$ at random from $(u,v)$ \\
\>\> 5. \( F \leftarrow F \cup \{ v_i \} \) \\
\>\> 6. \( V \leftarrow V \setminus \{ v_i \} \) \\
\>{\bf Return} "Fail" \\
\end{tabbing}


Due to Lemma~\ref{edge_lemma},
when {\sc SingleGuess($G,j$)} terminates with
a FVS of size $j$, there is a probability of at 
least $1/4^j$ that the output is a minimum FVS.

Note that steps 3 and 4 in {\sc SingleGuess}
determine a vertex $v$ by first selecting
an arbitrary edge and then selecting an arbitrary endpoint
of this edge.  
An equivalent way of achieving the same selection rule
is to choose a vertex with probability proportional to its degree:
\[
p(v) = \frac{d(v)}{\sum_{u \in V} d(u)} = \frac{d(v)}{2 \cdot |E|}
\]
To see the equivalence of these two selection
methods, define 
$\Gamma(v)$ to be a set of edges whose one endpoint is $v$,
and note that for graphs without self-loops,
\[
p(v) = \sum_{e \in \Gamma(v)} p(v | e) \cdot p(e)
= \frac{1}{2} \sum_{e \in \Gamma(v)} p(e) 
= \frac{d(v)}{2 \cdot |E|}
\]
This equivalent phrasing of the selection criterion 
is easier to extend to the weighted case and will be used
in the following sections.

An algorithm for finding a minimum FVS with high
probability, which we call {\sc RepeatedGuess}, 
can now be described as follows: 
Start with $j=1$.
Repeat {\sc SingleGuess} $c \, 4^j$ times where $c > 1$ is a 
parameter defined by the user. 
If in one of the iterations 
a FVS of size $\leq j$ is found, then output this FVS, 
otherwise, increase $j$ by one and continue.

\vspace{2ex}
\noindent
{\bf ALGORITHM RepeatedGuess(G,c)}
\begin{tabbing}
my \= futu \= ref \= irmpo \= larfox \= \kill
{\bf Input: } {\em An undirected graph $G$} \\
\> \> \> {\em and a constant $c > 1$.}\\
{\bf Output: } {\em A feedback vertex set $F$.}\\
\>{\bf For} $j=1,\ldots,|V|$ \\
\>\> {\bf Repeat} $c \, 4^j$ {\bf times}\\
\>\>\> 1. $F \leftarrow$ {\sc SingleGuess($G,j$)}\\
\>\>\> 2. {\bf If} $F$ is not "Fail" {\bf then Return $F$} \\
\>\>{\bf End} \{Repeat\} \\
\>{\bf End} \{For\}
\end{tabbing}


The main claims about these algorithms
are given by the following theorem.

\begin{theorem}  
\label{thm}
Let $G$ be an undirected graph and 
$c \ge 1$ be a constant. Then,
{\sc SingleGuess($G,k$)} outputs
a FVS whose expected size is 
no more than $4k$, and
{\sc RepeatedGuess($G,c$)} outputs,
after $O(c \, 4^{k} k n)$ steps,
a minimum FVS 
with probability at least $1- (1-\frac{1}{4^k})^{c4^k}$,
where $k$ is the size of a minimum FVS
and $n$ is the number of vertices.
\end{theorem}

The claims about the probability of success 
and number of steps follow immediately from the fact
that the probability of success of {\sc SingleGuess($G,j$)} 
is at least $(1/4)^j$ and that, in case of success,
$O(c \, 4^{j})$ iterations are performed
each taking $O(j n)$ steps.
The result follows from the fact that $\sum_{j=1}^k j 4^j$ is of
order $O(k 4^k)$.
The proof about the expected size of a single guess
is presented in the next section.

Theorem~\ref{thm} shows that each guess
produces a FVS which, on the average,
is not too far from the minimum, and that
after enough iterations, the algorithm 
converges to the minimum with high probability.
In the weighted case, discussed next,
we managed to achieve each of these two guarantees 
in separate algorithms, but we were unable to achieve both
guarantees in a single algorithm.


\subsection{The Weighted Algorithms}
\label{sec-weighted-random}

We now turn to the weighted FVS problem (WFVS) 
of size $k$ which is to find a feedback vertex set $F$ 
of a vertex-weighted graph $(G,w)$, $w: V \rightarrow \Realfield^+$, of 
size less or equal $k$ such that $w(F)$ is minimized.

Note that for the weighted FVS problem
we cannot replace each linkpoint $v$
with an edge because if $v$ has weight lighter than
its branchpoint neighbors then $v$ can participate in a minimum 
weight FVS of size $k$.

A graph is called {\em branchy\/} if it has no endpoints,
no self loops, and, in addition, 
each linkpoint is connected only to branchpoints \cite{baryehuda94}.
Given a graph $G$, by repeatedly removing all leaves,
and bypassing with an edge every linkpoint that has a neighbor 
with equal or lighter weight, a graph $G'$ is obtained such
that the weight of a minimum 
weight FVS (of size $k$) in $G'$ and in $G$ are 
equal and every minimum WFVS of $G'$ 
is a minimum WFVS of $G$.
Since every vertex with a self-loop belongs 
to every FVS, we can transform $G'$ to
a branchy graph without self-loops
by adding the vertices involved in self loops
to the output of the algorithm.

To address the WFVS problem we offer two
slight modifications to 
the algorithm {\sc SingleGuess} presented in the previous section.
The first algorithm, which we call {\sc SingleWGuessI},
is identical to {\sc SingleGuess} except that
in each iteration we make a reduction to a
branchy graph instead of a reduction to a rich graph.
It chooses a vertex with probability 
proportional to the degree 
using $p(v)=d(v)/ \sum_{u \in V} d(u)$.
Note that this probability does not take the weight 
of a vertex into account.
A second algorithm, which we call {\sc SingleWGuessII},
chooses a vertex with probability 
proportional to the ratio of its degree over its weight,
\begin{equation}
\label{prob_eq}
p(v)=\frac{d(v)}{w(v)} / \sum_{u \in V}\frac{d(u)}{w(u)}.
\end{equation}

$ $

$ $



\vspace{2ex}
\noindent
{\bf ALGORITHM SingleWGuessI(G,j)}
\begin{tabbing}
my \= fu \= re \= irmp \= larfox \= \kill
{\bf Input: } {\em An undirected weighted graph $G_0$} \\
\> \> \> {\em and an integer $j>0$.}\\
{\bf Output: } {\em A feedback vertex set $F$ of size $\leq j$, } \\
\> \> \> {\em or "Fail" otherwise.} \\
\> {\bf For } $i=1,\ldots, j$ \\
\>\> 1. Reduce $G_{i-1}$ to a branchy graph $G_i(V_i,E_i)$ \\ 
\>\>\> while placing self loop vertices in $F$. \\
\>\> 2. {\bf If} $G_i$ is the empty graph  {\bf Return $F$} \\
\>\> 3. Pick a vertex $v_i \in V_i$ at random with \\
\>\>\> probability $p_i(v)=d_i(v)/\sum_{u \in V_i} d_i(u)$\\
\>\> 4. \( F \leftarrow F \cup \{ v_i \} \) \\
\>\> 5. \( V \leftarrow V \setminus \{ v_i \} \) \\
\>{\bf Return} "Fail" \\
\end{tabbing}



The second algorithm uses Eq.\ 2  %~\ref{prob_eq}
for computing $p(v)$ in Line 3.
These two algorithms have remarkably different 
guarantees of performance. Version I guarantees
that choosing a vertex that belongs to any given
FVS is larger than $1/6$, however, the expected weight
of a FVS produced by version I cannot be bounded
by a constant times the weight of a minimum WFVS.
Version II guarantees that the expected weight of 
its output is bounded by 6 times the weight of a minimum
WFVS, however, the probability of converging to a minimum
after any fixed number of iterations can be arbitrarily small.
We first demonstrate via an example the negative claims.
The positive claims are phrased more precisely in 
Theorem~\ref{weighted-thm} and proven thereafter.

Consider the graph shown in Figure~\ref{counter-example} 
with three vertices $a$,$b$ and $c$, and 
corresponding weights $w(a)=6$, $w(b)=3 \epsilon$ 
and $w(c)=3 m$, with three parallel edges between 
$a$ and $b$, and three parallel edges between $a$ 
and $c$. The minimum WFVS $F^*$ with size 1 consists of 
vertex $a$. According to Version II,
the probability of choosing vertex $a$ 
is (Eq.~\ref{prob_eq}):
\[
p(a) = \frac{\epsilon}{(1+1/m) \cdot \epsilon +1}
\]
So if $\epsilon$ is arbitrarily small and $m$ is sufficiently 
large, then the probability of choosing vertex $a$ 
is arbitrarily small. 
Thus, the probability of choosing a vertex from 
some $F^*$ by the criterion $d(v)/w(v)$, as done by
Version II, can be arbitrarily small. 
If, on the other hand, Version I is used, then
the probability of choosing $a,b$, or $c$ is
$1/2,1/4,1/4$, respectively. Thus,
the expected weight of the first vertex to be chosen 
is $3/4 \cdot (\epsilon + m +4)$, while the weight of 
a minimum WFVS is 6. Consequently, if $m$ is sufficiently large,
the expected weight of a WFVS found by Version I
can be arbitrarily larger than a minimum WFVS. 

\begin{figure}
\input{pic.txt}
\caption{The minimum WFVS $F^* = \{a\}$. }
\label{counter-example}
\end{center}
\end{figure}


The algorithm for repeated guesses, which we call 
{\sc RepeatedWGuessI($G,c,j$)} 
is as follows:
repeat {\sc SingleWGuessI($G,j)$} $c \, 6^j$ times, where $j$ 
is the minimal number of vertices of a minimum weight FVS we seek. 
If no FVS is found of size $\leq j$, 
the algorithm outputs that the size of a minimum 
WFVS is larger than $j$ with high probability, otherwise, 
it outputs the lightest FVS of size less or equal $j$ 
among those explored.
The following theorem summarizes the main claims.

\begin{theorem}  
\label{weighted-thm}
Let $G$ be a weighted undirected graph 
and $c \ge 1$ be a constant.\\
a) The algorithm {\sc RepeatedWGuessI($G,c,k$)} outputs
after $O(c \, 6^{k} k n)$ steps
a minimum WFVS with probability at least
$1- (1-\frac{1}{6^k})^{c6^k}$,
where $k$ is the minimal size of a minimum weight FVS of $G$
and $n$ is the number of vertices. \\
b) The algorithm {\sc SingleWGuessII($G$,$k$)} 
outputs a feedback vertex 
set whose expected weight is no more than 
six times the weight of a minimum weight FVS.
\end{theorem}


The proof of each part requires a preliminary lemma.

\begin{lemma}
\label{weighted_edge_lemma}
Let $G=(V,E)$ be a branchy graph, $F$ be a feedback vertex set of $G$
and $X = V \setminus F$. 
Let $E_X$ denote the set of edges in $E$ whose endpoints
are all vertices in $X$ and $E_{F,X}$ denote the set of edges
in $G$ that connect vertices in $F$ with vertices in $X$. 
Then, $|E_X| \leq 2 \cdot |E_{F,X}|$.
\end{lemma}

\noindent
{\bf Proof. }
Let $X^b$ be the set of branchpoints in $X$.
We replace every linkpoint in $X$ by an edge between its neighbors,
and denote the resulting set of edges between vertices
in $X^b$ by $E^b_{X^b}$ and between vertices in $X^b$ and $F$ 
by $E^b_{F,X^b}$.
The proof of Lemma~\ref{edge_lemma} shows
that 
\[
|E^b _{X^b }| \leq |E^b _{F,X^b }|. 
\]
Since every linkpoint in $X$ has both neighbors in the
set $X^b \cup F$, the following holds:
\[  |E_X| \leq 2  \cdot |E^b _{X^b }| \mbox{ and }
|E_{F,X}| = |E^b _{F,X^b }|.
\]
Hence, $|E_X| \leq 2 \cdot |E_{F,X}|$.
$\Box$

An immediate consequence of 
Lemma~\ref{weighted_edge_lemma} is that the probability of 
randomly choosing an
edge that has at least one endpoint that belongs to a FVS
is greater or equal $1/3$. Thus, selecting a vertex at random from
a randomly selected edge has a probability of at least $1/6$ 
to belong to a FVS. 
Consequently, if the algorithm terminates 
after $c \, 6^{k}$ iterations,
with a WFVS of size $k$, 
there is a probability of at 
least $1- (1-\frac{1}{6^k})^{c6^k}$
that the output is a minimum WFVS
of size at most $k$.
This proves part (a) of Theorem~\ref{weighted-thm}.
Note that since $k$ is not known in advance,
we use {\sc RepeatedWGuessI($G, c, j$)} with increasing
values of $j$ until a FVS is found, say when j=J.
When such a set is found it is still possible
that there exists a WFVS with more than $J$ vertices 
that has a smaller weight than the one found.
This happens when $k > J$.
However, among the WFVSs of size at most $J$, the algorithm
finds one with minimum weight with high probability.

%Note that the claim of part (a) is quite weak because
%it does not show how close is the weight of
%the FVS found by RepeatedWGuessI(G, c) to the weight of the
%minimum-weight FVS of size $k$, and even if the algorithm finds
%the minimum-weight FVS of size $k$, there could be a
%WFVS with more than $k$ vertices that has a smaller weight than
%a minimum-weight FVS of size $k$.

The second part requires the following lemma.

\begin{lemma}
Let $G$ be a branchy graph and $F$ be a FVS of $G$. Then,
\label{branchy-degree}
%\label{eqL0}
\[
\sum_{v \in V} d(v) \leq 6 \sum_{v \in F} d(v).
\]
\end{lemma}

\noindent
{\bf Proof.} Denote by $d_Y(v)$ the number of edges 
between a vertex $v$ and a set of vertices $Y$. 
Then,
\begin{eqnarray*}
\label{eqL1}
\lefteqn{
\!\!\!\! \!\!\!\!\!\!\!\! 
\sum_{v \in V} d(v) = 
\sum_{v \in X} d(v) + \sum_{v \in F} d(v) = }
\nonumber\\
& & 
\!\!\!\! \!\!
\sum_{v \in X} d_X(v) + 
\sum_{v \in X} d_F(v) + 
\sum_{v \in F} d(v).
\end{eqnarray*}
Due to Lemma~\ref{weighted_edge_lemma},
\begin{equation}
\label{eqL2}
\sum_{v \in X} d_X(v) = 2 |E_X| \leq 4 |E_{F,X}| = 
4 \sum_{v \in X} d_F(v).
\end{equation}
Consequently,
\begin{eqnarray*}
\label{eqL3}
\lefteqn{
\sum_{v \in V} d(v) \leq
4 \sum_{v \in X} d_F(v) +
}
\\
& & 
\sum_{v \in X} d_F(v) 
+ \sum_{v \in F} d(v) 
\leq 6 \sum_{v \in F} d(v)
\end{eqnarray*}
as claimed.  $\Box$

We can now prove part (b) of Theorem~\ref{weighted-thm}
analyzing %the performance of 
{\sc SingleWGuessII(G,$k$)}.
Recall that $V_i$ is the set of 
vertices in graph $G_i$ in iteration $i$, 
$d_i(v)$ is the degree of vertex 
$v$ in $G_i$, and $v_i$ is the 
vertex chosen in iteration $i$.
Furthermore, recall that
$p_i(v)$ is the probability to choose vertex $v$ 
in iteration $i$.  

The expected weight
$E_i(w(v))=\sum_{v \in V_i} w(v) \cdot p_i(v)$
of a chosen vertex in iteration $i$ is denoted with $a_i$. 
Thus, due to the linearity of the expectation
operator, $E(w(F)) =  \sum_{i=1}^k a_i$, assuming $|F|=k$.
We define a normalization constant for 
iteration $i$ as follows:
\[
%\label{eqE2}
\gamma_i= \left[\sum_{u \in V_i}\frac{d_i(u)}{w(u)}\right]^{-1}
\]
Then, $p_i(v) = \gamma_i \cdot \frac{d_i(v)}{w(v)}$ and
\[
%\label{eqE3}
a_i =\sum_{v \in V_i} w(v) \cdot \frac{d_i(v)}{w(v)} 
\cdot \gamma_i =\gamma_i \cdot \sum_{v \in V_i} d_i(v)
\]
Let $F^*$ be a minimum FVS of $G$ and $F^*_i$ be minimum 
weight FVS of the graph $G_i$.
The expected weight $E_i(w(v) | v \in F^*_i))$
of a vertex chosen from $F^*_i$ in iteration $i$ 
is denoted with $b_i$.
We have,
\[
%\label{eqE4}
b_i = \sum_{v \in F^*_i} w(v) \cdot p_i(v) 
=
\gamma_i \cdot \sum_{v \in F^*_i} d_i(v)
\]
By Lemma~5, $a_i/b_i  \leq 6$ for every $i$.

Recall that by definition $F^*_2$ is the minimum FVS in 
the branchy graph $G_2$ obtained from $G_1 \setminus \{v_1\}$.
We get,
\[
E(w(F^*)) \geq E_1(w(v) | v \in F^*_1)) + E(w(F^*_2))
\]
because the right hand side is the expected weight
of the output $F$ assuming the algorithm finds 
a minimum FVS on $G_2$ and just needs to select
one additional vertex, while the left hand side
is the unrestricted expectation.
By repeating this argument we get,
\[
E(w(F^*)) \geq b_1 + E(w(F^*_2)) \geq \cdots \geq \sum_{i=1}^k b_i
\]
Using $ \sum_i a_i  /  \sum_i b_i \leq \max_i a_i / b_i \leq  6$,
we obtain
\[
\label{eqE9}
E(w(F)) \leq 6 \cdot E(w(F^*)).
\]
Hence,
$E(w(F)) \leq 6 \cdot w(F^*)$ as claimed.
$\Box$

The proof that
{\sc SingleGuess($G,k$)} outputs a FVS whose expected size is 
no more than $4k$ (Theorem~\ref{thm}) where $k$
is the size of a minimum FVS is analogous to
the proof of Theorem~\ref{weighted-thm} in the following
sense. 
We assign a weight 1 to all vertices and replace
the reference to Lemma~\ref{branchy-degree}
by a reference to the following claim:
If $F$ is a FVS of a rich graph $G$, then
$\sum_{v \in V} d(v) \leq 4 \sum_{v \in F} d(v)$.
The proof of this claim is identical to the proof 
of Lemma~\ref{branchy-degree}
except that instead of using Lemma~\ref{weighted_edge_lemma} 
we use Lemma~\ref{edge_lemma}.  

\subsection{The Practical Algorithm}
\label{sec-WRA}

In previous sections we presented several algorithms
for finding minimum FVS with high probability.
The description of these algorithms was geared towards analysis,
rather than as a prescription to a programmer.
In particular, the number of iterations
used within {\sc RepeatedWGuessI($G,c,k$)} is not
changed as the algorithm is run with $j < k$.
This feature allowed us to regard each call
to {\sc SingleWGuessI($G,j$)} made by
{\sc RepeatedWGuessI} as an independent process.
Furthermore, there is a small probability for
a very long run even when the size of the minimum 
FVS is small.

We now slightly modify {\sc RepeatedWGuessI}
to obtain an algorithm, termed WRA, which
does not suffer from these deficiencies.
The new algorithm works as follows.
Repeat {\sc SingleWGuessI($G,|V|$)} for
$min(\Max, c \, 6^{w(F)})$ iterations,
where $w(F)$ is the weight of the
lightest WFVS found so far 
and $\Max$ is some specified constant 
determining the maximum number of iterations
of {\sc SingleWGuessI}. 

\vspace{1ex}
\noindent
{\bf ALGORITHM WRA($G,c,\Max$)}
\begin{tabbing}
my \= futu \= ref \= irmpo \= larfox \= \kill
%{\bf Input: } {\em An undirected weighted graph $G(V,E)$ }\\
%\>\>\>{\em  and constants $\Max$ and $c>1$ }\\
{\bf Input: } {\em An undirected weighted graph $G(V,E)$ }
{\em  and constants $\Max$ and $c>1$ }\\
{\bf Output: } {\em A feedback vertex set $F$ }\\
\> $F \leftarrow${\sc SingleWGuessI ($G,|V|$)}\\
\> $M \leftarrow min (\Max, c \, 6^{w(F)}) $;  $i \leftarrow 1;$ \\
%\> $i \leftarrow 1;$ \\
\> {\bf While} $i \leq M$ {\bf do}\\
\>\> 1. $F' \leftarrow${\sc SingleWGuessI($G,|V|$)}\\
\>\> 2. {\bf If} $w(F')\leq w(F)$ {\bf then} \\
\>\>\> $F \leftarrow F';$ $M \leftarrow min (\Max, c \, 6^{w(F)})$\\
%\>\>\> $M \leftarrow min (\Max, c \, 6^{w(F)})$\\
\>\>3. $i \leftarrow i+1;$\\
\>{\bf End} \{While\} \\
\> Return $F$ \\
\end{tabbing}


\begin{theorem}
If $\Max \geq c 6^k$, where $k$ is the minimal size of a minimum WFVS
of an undirected weighted graph $G$, 
then WRA($G,c,\Max$) outputs a minimum WFVS of $G$ with probability
at least $1- (1-\frac{1}{6^k})^{c6^k}$.
\end{theorem}

The proof is an immediate 
corollary of Theorem~\ref{weighted-thm}.

The choice of $\Max$ and $c$ depend on the application.
A decision-theoretic approach for selecting such values
for any-time algorithms
is discussed by Breese and Horvitz (1990).  %\cite{breese90}.


\section{Experimental Results}
\label{sec-experiments} 

The experiments compared the outputs
of WRA vis-\`{a}-vis a greedy algorithm GA
and a modified greedy algorithm MGA \cite{becker96} 
based on randomly generated graphs and on some real graphs
contributed by the Hugin group (www.hugin.com).

The random graphs are divided into three sets.
Graphs with 15 vertices and 25 edges where
the number of values associated with each vertex is
randomly chosen between 2 and 6, 2 and 8, and 
between 2 and 10.
Graphs with 25 vertices and 55 edges where
the number of values associated with each vertex is
randomly chosen between 2 and 6, 2 and 8, and 
between 2 and 10.
Graphs with 55 vertices and 125 edges where
the number of values associated with each vertex is
randomly chosen between 2 and 10.
Each instance of the three classes is based on
100 random graphs generated as described by 
Suermondt and Cooper (1990).  %\cite{suermondt90}.
The total number of random graphs we used is 700.


\begin{figure}
\begin{center}
\begin{tabular}{|c|c|c||c||c|c|c|}\hline
$|V|$& $|E|$& values & size & MGA & WRA & Eq. \\ \hline
15 & 25  & 2--6  & 3--6  & 12 & 81 & 7 \\ \hline
15 & 25  & 2--8  & 3--6  & 7 & 89 & 4 \\ \hline
15 & 25  & 2--10 & 3--6  & 6 & 90 & 4 \\ \hline
25 & 55 & 2--6  & 7--12  &3 & 95 & 2 \\ \hline
25 & 55 & 2--8  & 7--12  &3 & 97 & 0 \\ \hline
25 & 55 & 2--10 & 7--12  &0 & 100 & 0 \\ \hline
55 &125 & 2--10 & 17--22 &0 & 100 & 0 \\ \hline
&   &     &       & 31 & 652 & 17 \\ \hline
\end{tabular}
\end{center}
\caption{Number of graphs in which MGA or WRA yield
a smaller loop cutset. The last column records the number of graphs 
for which the two algorithms produced
loop cutsets of the same weight.
Each line in the table is based on 100 graphs.}
\end{figure}

The results are summarized in the table of Figure~2.
WRA is run with $\Max=300$ and $c=1$.
The two algorithms, MGA and WRA, output loop cutsets of 
the same size in only 17 graphs and when the
algorithms disagree, then in 95\% of these graphs
WRA performed better than MGA. 

The actual run time of $WRA(G,1,300)$ is about 300 times 
slower than GA (or MGA) on $G$. On the largest random graph we used,
it took 4.5 minutes. Most of the time is spend in the 
last improvement of WRA.  Considerable run time can be saved
by letting $\Max=5$.
For all 700 graphs, WRA(G,1,5) has already obtained 
a better loop cutset than MGA.
The largest improvement, with $\Max=300$, was from 
a weight of 58.0 ($log_2$ scale)
to a weight of 35.9.  The improvements in this case
were obtained in
iterations 1, 2, 36, 83, 189 with respective weights
of 46.7, 38.8, 37.5, 37.3, 35.9 and respective sizes
of 22, 18, 17, 18, and 17 nodes.
On the average, after 300 iterations, the improvement
for the larger 100 graphs was from a weight of 52 to 39
and from size 22 to 20.
The improvement for the smaller 600 graphs 
was from a weight of 15 to 12.2 and from size 9 to 6.7.


The second experiment compared between GA, MGA and WRA
on four real Bayesian networks
showing that WRA outperformed both GA and MGA
after a single call to {\sc SingleWGuessI}.
The weight of the output continued to decrease logarithmically
with the number of iterations. 
We report the results with $\Max=1000$ and $c=1$.
Run time was between 3 minutes for Water and 15 
minutes for Munin1 on a Pentium 133 with 32M RAM.


\begin{figure}
{\small
\begin{center}
\begin{tabular}{|c||c|c|c||c|c|c|}\hline
Name & $|V|$& $|E|$& $|F^*|$ & GA & MGA & WRA \\ \hline
Water  & 32 & 123  & 16   & 40.7 & 42.7 & 29.5 \\ \hline
Mildew & 35 & 80   & 14  & 48.1 & 40.5 & 39.3 \\ \hline
Barley & 48 & 126  & 20  & 72.1 & 76.3 & 57.3 \\ \hline
Munin1 & 189 & 366 & 59  & 159.4 & 167.5 & 122.6 \\ \hline
%Minun2   & 441 & 806 & 11  & 111.1 & 111.1 \\ \hline
%Minun3 & 411 & 809  & 11  & 111.1 & 111.1\\ \hline
%Minun4   & 441 & 806 & 11  & 111.1 & 111.1 \\ \hline
%Pigs   & 441 & 806 & 11  & 111.1 & 111.1 \\ \hline
%Diabetes & 411 & 809  & 11  & 111.1 & 111.1\\ \hline
%link & 411 & 809  & 11  & 111.1 & 111.1\\ \hline
\end{tabular}
\end{center}
}
\caption{Log size (base 2) of the loop cutsets found by GA, MGA, and WRA.}
\label{real_fig}
\end{figure}


\section{Discussion}


Our randomized algorithm, WRA, has been incorporated
into the popular genetic software {\sc FASTLINK} 4.1 
by Alejandro Sch\"{a}ffer who develops and maintains 
this software at the National Institute of Health.
WRA replaced previous approximation
algorithms for finding FVS because with a small
$\Max$ value it already matched or improved 
{\sc FASTLINK} 4.0 on most datasets examined. 
The datasets used for comparison 
are described by Becker et al.\ (1998).  %\cite{becker98}.
The main characteristics of these datasets is 
that they were all collected
by geneticists, they have a small number of
loops, and a large number of values
at each node (tens to hundreds depending on
the genetic analysis).
For such networks the method of conditioning
is widely used by geneticists.


The leading inference algorithm, however, for Bayesian networks 
is the clique-tree algorithm
\cite{lauritzen88} which has been further developed in
several papers
\cite{JLO90,JOA90}. 
For the networks
presented in Table~\ref{real_fig} conditioning is not a
feasible method while the clique tree algorithm can and is
being used to compute posterior probabilities in these networks.
Furthermore, it has been shown that the weight of the 
largest clique is bounded by the weight of the loop cutset union
the largest parent set of a vertex in a Bayesian network
implying that the clique tree algorithm is always superior 
in time performance over the conditioning algorithm \cite{SAS94}.
The two methods, however, can be combined to strike a balance 
between time and space requirements as done
within the bucket elimination framework \cite{De99}.


The algorithmic ideas behind 
the randomized algorithms presented herein can also be applied 
for constructing good clique trees and initial 
experiments confirm that an improvement over 
deterministic algorithms is often obtained. 
The idea is that instead of greedily selecting
the smallest clique when constructing a clique tree, 
one would randomly select 
the next clique according to the relative weights
of the candidate cliques.
It remains to develop the theory behind random choices of clique trees
before a solid assessment can be presented.
Currently, there is no algorithm for finding a clique tree such
that its size is guaranteed to be close to optimal
with high probability.


Horvitz et al. (1989) show 
that the method of conditioning
can be useful for approximate inference. 
In particular, they show how 
to rank the instances of a loop cutset according to 
their prior probabilities assuming all variables
in the cutset are marginally independent.
The conditioning algorithm can then be run 
according to this ranking 
and the answer to a query be given as an interval
that shrinks towards the exact solution as more instances of the
loop cutset are considered \cite{HSC89,Ho90}.
Applying this idea without making independence
assumptions is described by Darwiche (1994).  %\cite{Da94}.
So if the maximal clique is too large to store
one can still perform 
approximate inferences using the conditioning algorithm.


\section*{Acknowledgment}
We thank Seffi Naor for fruitful discussions.
Part of this work was done while the third author 
was on sabbatical at Microsoft Research.
A variant of this work has been presented
at the fifteenth conference
on uncertainty in artificial intelligence, July 1999, Sweden.

\bibliography{fvs-jair}
\bibliographystyle{theapa}

\end{document}
