  Let G denote a graph and let K be a subset of vertices that are a set of
target vertices of G. The K-terminal reliability of G is defined as the
probability that all target vertices in K are connected, considering the
possible failures of non-target vertices of G. The problem of computing
K-terminal reliability is known to be #P-complete for polygon-circle graphs,
and can be solved in polynomial-time for t-polygon graphs, which are a subclass
of polygon-circle graphs. The class of circle graphs is a subclass of
polygon-circle graphs and a superclass of t-polygon graphs. Therefore, the
problem of computing K-terminal reliability for circle graphs is of particular
interest. This paper proves that the problem remains #P-complete even for
circle graphs. Additionally, this paper proposes a linear-time algorithm for
solving the problem for proper circular-arc graphs, which are a subclass of
circle graphs and a superclass of proper interval graphs.
