Fast, multicolour optical sectioning over extended fields of view by combining
interferometric SIM with machine learning

Edward N. Ward,1 Rebecca M. McClelland,1 Jacob R. Lamb,1 Roger Rubio-
Sánchez,1,2 Charles N. Christensen,1 Bismoy Mazumder,1 Sofia Kapsiani,1 Luca
Mascheroni,1 Lorenzo Di Michele,1,2 Gabriele S. Kaminski Schierle,1 and
Clemens F. Kaminski1

1Department of Chemical Engineering and Biotechnology, University of
Cambridge, Cambridge, CB3 0AS, UK

2fabriCELL, Molecular Sciences Research Hub, Imperial College London, London,
W12 0BZ, UK

##  1 Abstract

Structured illumination can reject out-of-focus signal from a sample, enabling
high-speed and high-contrast imaging over large areas with widefield detection
optics. Currently, this optical-sectioning technique is limited by image
reconstruction artefacts and the need for sequential imaging of multiple
colour channels. We combine multicolour interferometric pattern generation
with machine-learning processing, permitting high-contrast, real-time
reconstruction of image data. The method is insensitive to background noise
and unevenly phase-stepped illumination patterns. We validate the method in
silico and demonstrate its application on diverse specimens, ranging from
fixed and live biological cells to synthetic biosystems, imaging at up to 37
Hz across a 44 $\times$ 44 $\mu m^{2}$ field of view.

##  2 Introduction

Widefield fluorescence microscopy permits the imaging of biological structures
with a high specificity, however, out-of-focus light limits image contrast.
Unless planar excitation profiles are used for illumination – such as in
lightsheet [1] or HiLo [2] microscopy – fluorescent probes located above and
below the focal plane contribute to the signal collected in the final image.

Scanning confocal microscopy circumvents this problem through the use of a
pinhole to physically reject out-of-focus signal. While this is effective at
increasing contrast, only a single point in the sample can be imaged at a time
and images must be built up sequentially, pixel-by-pixel, greatly increasing
acquisition time. Furthermore, high excitation powers are required to
compensate for the signal lost through the pinhole.

A different approach to achieve optical sectioning (OS) is through structured
illumination microscopy (SIM) [3]. Here, a fluorescent sample is illuminated
by patterned excitation light and the emitted fluorescence is imaged with
widefield detection. In super-resolution SIM, interference patterns are
produced by the interaction of the patterned excitation with the structures of
the sample and these interference patterns are used to extract high-resolution
information about the sample [4, 5]. OS-SIM makes use of the fact that the
modulation depth of the excitation pattern is highest in the in-focus plane
and decreases rapidly with distance from it. Hence, the in- and out-of-focus
structures can be distinguished by differences in stripe contrast. To achieve
this, the sample is typically illuminated with a sinusoidal stripe pattern,
and three sequential images are acquired as the pattern is shifted in phase
over the sample. Under these conditions, only the in-focus structures will
show a change in intensity between the phase shifted images and therefore
these can be extracted and the three raw images reconstructed into one
optically sectioned image. This method was pioneered by Neil et al. [3] who
used the squared difference (SD) between the three phases to reconstruct the
image:

$I_{R}^{2}=(I_{1}-I_{2})^{2}+(I_{2}-I_{3})^{2}+(I_{1}-I_{3})^{2},$ (1)

where $I_{R}$ is the reconstructed image and $I_{n}$ represents the n-th phase
image of the sample under striped illumination with the phase shifted by
$2(n-1)\pi$/3. Phase stepping in this way ensures a uniform average
illumination and prevents striping artefacts in the reconstructed image. While
simple to implement, this method is highly sensitive to noise, which becomes
amplified in the SD reconstruction. Additionally, even small movements of the
sample or deviations from the ideal phase step size introduce reconstruction
artefacts. While recent efforts have improved on this early method,
reconstructions remain prone to artefacts which require substantial filtering
and post-processing [6].

To address these issues, we propose a method for OS-SIM which combines
interferometric pattern generation with machine learning (ML): ML-OS-SIM. We
use two complimentary neural networks to reconstruct OS-SIM data: a fast
network for real-time reconstructions and a heavier network for post-
acquisition reconstructions. In combination with an interferometric SIM setup
[7], we achieve OS-SIM reconstructions in multiple colour channels
simultaneously. Using the fast-reconstruction network, we demonstrate on-the-
fly processing of OS-SIM data during acquisition, allowing users to
immediately and intuitively visualise reconstructions as they navigate the
sample. The software to achieve this is packaged in a user-friendly GUI which,
combined with the simplicity of the interferometric SIM design, makes the
method easy to implement on existing microscope setups.

##  3 Methods

###  3.1 Hardware implementation

For optimal reconstructions of OS-SIM data, the spatial frequency of the
striped illumination pattern must be half of the maximum spatial frequency
observable by the microscope [3]. As the resolution limit changes with
wavelength, the periodicity of the pattern must also be changed when switching
between colours. In SIM setups based on spatial light modulators, digital
micro-mirror devices or diffraction gratings, this means that only a single
colour can be imaged at a time, slowing down image acquisition and, crucially,
introducing a temporal offset between acquisitions of different colour
channels. To overcome these issues, we use an interferometric method to
generate the fringe patterns (Fig. S1) [7]. This method has the advantage that
the periodicity of the structured illumination fringes depends on the
wavelength of the excitation light, meaning the fringe spacing is optimised
for all wavelengths simultaneously. The setup makes use of a Michelson
interferometer and phase stepping is achieved by laterally sweeping the
pattern across the sample with a galvanometric mirror element. In our setup,
fluorescence signal from the sample is collected and split into three colours
using an image splitting device, permitting the simultaneous imaging of
multiple colour channels. A Python graphical user interface enables hardware
control and display of reconstructed images in real time (Fig. S3). All source
code is available in a GitHub repository [8].

###  3.2 Machine learning networks

Machine learning (ML) has become a powerful enabler for the pre-processing,
post-processing and reconstruction of super-resolution SIM data [9]. Compared
to classical methods, ML can increase reconstruction quality and does not
require the estimation of system parameters. ML has also been applied to the
reconstruction of OS-SIM data [10, 11], but the impact of sample motion and
uneven phase steps on reconstruction quality has not been addressed. Here, we
leverage recent advances in ML and optimise two distinct neural networks
specifically for the reconstruction of interferometrically generated OS-SIM
data. By using two networks, we are able to achieve real-time reconstructions
at the point of acquisition, and high-fidelity reconstructions post-
acquisition, yielding optimised results even for moving samples.

In the first instance, ML-OS-SIM reconstructions were performed using a
lightweight convolutional neural network (CNN) based on the residual channel
attention network (RCAN) architecture (Supplementary note 4B) [12]. This RCAN
model has a low memory footprint and can perform reconstructions on low-end
consumer graphics cards at rates compatible with live reconstructions during
imaging.

For high-fidelity image reconstruction post-acquisition, we use video super-
resolution (VSR) reconstruction, a video transformer network based on the
shifted-window architecture (Supplementary note 4A) [13, 14]. While more
computationally intensive, this network is specifically optimised to
reconstruct data from moving structures, mimicking dynamic biological samples
[15].

To mitigate the challenges posed by training on experimentally acquired OS-SIM
data, we simulated large datasets and employed transfer learning to train the
network. This approach offers several advantages: firstly, for supervised
learning, the ground truth is known, ensuring that the networks do not learn
to generate the artefacts produced by classical reconstruction algorithms.
Secondly, large and diverse training datasets can be generated, enabling the
models to learn the reconstruction process without overfitting to limited
experimental datasets. Thirdly, it is possible to train the network to be
robust to the specific challenges associated with reconstructing
interferometric OS-SIM data (Supplementary note 4C). This is particularly
important when the phase changes of the pattern differ from the ideal, evenly
spaced phases required for other reconstruction methods to work.

##  4 Results and Discussion

###  4.1 Machine learning reconstructions suppress noise and out-of-focus
light from volumetric data

Figure 1: Machine learning outperforms classical methods for the
reconstruction of optical sectioning structured illumination microscopy (OS-
SIM) data. A: Widefield image and reconstructions of OS-SIM data acquired of
immunostained $\beta$-tubulin in fixed Vero cells. Square difference (SD) [3]
and filtered SD [6] both show an improvement in contrast and background
rejection, however, both techniques are heavily impacted by noise. In the SD
reconstruction, the nose is amplified and the details of the sample are
obscured. The filtered SD reconstruction removes this noise but at the expense
of artefacts being introduced into the reconstruction. In comparison, ML-OS-
SIM reconstruction successfully removes both the background and noise. Scale
bars = 10 $\mu m$. B: Magnified 10 $\times$ 10 $\mu m^{2}$ region indicated on
A.

We first validated the ML reconstruction technique on volumetric data from
fixed biological structures (Fig. 1). OS-SIM data from a fixed sample of Vero
cells were reconstructed into optically sectioned images using ML and compared
to the SD and filtered SD approaches [3, 6]. All OS-SIM methods exhibit a
reduction in the out-of-focus signal, however, the ML approach performs much
better in the presence of background noise. To quantify this improvement, the
ML reconstructions were tested on simulated biological samples (Figs. S3 and
S4). Successful reconstructions of OS-SIM data were possible at approximately
one fifth of the signal level where SD approaches fail.

###  4.2 ML-OS-SIM can image faster than point scanning confocal microscopy
with similar imaging performance

Figure 2: Machine-learning optical sectioning structured illumination
microscopy (ML-OS-SIM) produces optically sectioned volumes equivalent to
scanning confocal microscopy at faster imaging speeds. Images show
immunostained $\beta$-tubulin in fixed Vero cells imaged with A: deconvolved
scanning confocal microscopy and B: ML-OS-SIM. Both techniques enable the 3D
structure of the microtubule cytoskeleton to be resolved. Using ML-OS-SIM, the
complete equivalent volume could be imaged in ¡ 2 s compared to 2 min 36 s for
scanning confocal microscopy. Colourmap indicates the z position. Scale bars =
10 $\mu m$.

To demonstrate the speed improvement possible with interferometric ML-OS-SIM,
the system was compared to point scanning confocal microscopy (Fig. 2). The
camera exposure time was adjusted to produce reconstructions of a similar
quality to confocal images of the same sample. In both images, background
light is effectively removed and the 3D microtubule network of the cell can be
resolved free from artefacts. However, ML-OS-SIM imaging was considerably
faster: a 44 $\times$ 44 $\times$ 5 $\mu m^{3}$ volume could be imaged in ¡ 2
s, whereas scanning confocal imaging took 2 min 36 s. That is, ML-OS-SIM was
approximately 78 times faster. This speed advantage, in combination with the
lower illumination laser power required, results in less photodamage and
photobleaching to delicate samples (Supplementary note 1). An advantage of ML-
OS-SIM is that a single detector can be used in conjunction with detection-
splitting optics, whereas a confocal system would require an additional
detector for each channel.

###  4.3 ML-OS-SIM enables the volumetric imaging of structures in multiple
colours

Figure 3: Machine learning optical sectioning structured illumination
microscopy (ML-OS-SIM) enables video-rate mapping of the mitochondrial network
in live cells. Live COS-7 cells were labelled with MitoTracker Orange and SiR
Lysosome and excited simultaneously with the laser lines
$\lambda=561\,\mathrm{nm}$ and $\lambda=647\,\mathrm{nm}$. A: Projection of
volumetric data showing the mitochondrial network where the colourmap
indicates the z position. A single channel is shown. Scale bar = 10 $\mu m$.
B: Dynamic interaction of lysosomes (green) with mitochondria (purple). Image
sequence shows a projection of 3 adjacent slices from the data. Scale bars = 2
$\mu m$.

To demonstrate the capabilities of the technique for biological imaging, live
cells were imaged in multiple colours across a 5 $\mu m$ axial range (Fig. 3).
Figure 3A depicts a maximum intensity projection of the mitochondrial network
of a live cell imaged at a snapshot in time where the colourmap indicates the
depth within the cell. No movement or striping artefacts are discernible in
the image. Furthermore, the multicolour capability of the system allows
several structures to be visualised without a temporal delay between colour
channels. Figure 3B shows a two-channel time series of projections from the
volumetric data. Here, a lysosome (green) can be seen to push a mitochondrial
structure (purple) out of the way as it is transported through the cell.

###  4.4 Multicolour 3D imaging of DNA-nanotechnology biomimetic behaviours
with ML-OS-SIM

Figure 4:  Optical sectioning and multicolour interferometric structured
illumination enable fast, high-contrast 3D imaging of the lateral re-
organisation of membrane-bound DNA nanostructures in Giant Unilamellar
Vesicles (see Fig. S8) [16]. Images are 3D projections of volumetric data.
A,B: Representative vesicles before (A) and 12 h after (B) fueling a
biomimetic cargo transport pathway with nucleic-acid signals. A: In the
initial configuration, the DNA (blue) and liquid disordered phase (yellow)
overlap, indicating the preferential affinity of DNA nanostructures for
liquid-disordered phases. B: Cargo transport relocates the fluorescent
nanostructures to the liquid-ordered phase. ML-OS-SIM enableS samples to be
imaged in multiple colours simultaneously, preventing motion artefacts and
temporal offsets in the reconstructions. Scale bars = 5 $\mu m$.

In addition to biological samples, the contrast enhancement afforded by our
ML-OS-SIM strategy enables the visualisation of processes in synthetic cell
science. Recently, the synergy between lipid-membrane phase behaviour and the
tools of DNA nanotechnology has gained traction to engineer bio-inspired
responses in cell-like objects [17, 18]. Figure 4 shows ML-OS-SIM images of
DNA nanostructures tethered to phase-separated lipid membranes. The fast ML-
OS-SIM technique allows for the reconstruction of multicolour 3D views of DNA-
functionalised giant vesicles that can sustain biomimetic cargo transport
pathways across their membrane surface (Fig. 4) [16]. Chemical stimulus, in
the form of DNA oligonucleotides, triggers the lateral re-organisation of DNA
nanostructures, leading to the transport of fluorescently labelled DNA cargoes
(blue), away from the liquid-disordered phase (yellow) to liquid-ordered lipid
domains (Supplementary note 9). The responsive DNA nanostructures harness
established strand displacement mechanisms [19, 20] and the preferential
tendency of different hydrophobic anchors in membrane-bound DNA to enrich
distinct lipid domains [16]. The speed of ML-OS-SIM enables 3D imaging of the
structures, allowing for better visualisation and understanding of the re-
organisation process [16].

##  5 Conclusion

To date, OS-SIM has been limited by the unavailability of robust
reconstruction algorithms and the inability to image live samples in multiple
colours. Here, we demonstrate that these limitations can be overcome by
combining ML reconstruction methods with interferometric SIM. We demonstrate
fast, multicolour ML-OS-SIM at speeds of up to 37 Hz, across a 44 $\times$ 44
$\mu m^{2}$ field of view, with the option to view real-time reconstruction of
OS-SIM data. The widefield detection method employed in ML-OS-SIM means that
sectioning ability comparable to confocal microscopy can be achieved but at
imaging speeds two orders of magnitude faster, with reduced photodamage to the
sample. Additionally, we demonstrate that when combined with interferometric
pattern generation, this can achieve multi-label imaging with no temporal lag,
allowing for the interactions between structures to be visualised in 3D. These
capabilities are typically only afforded by lightsheet imaging modalities but
at the cost of greatly increased system complexity and non-conventional
imaging geometries. OS-SIM with ML reconstruction offers a simpler alternative
to lightsheet microscopy and is ideally suited to the imaging of dynamic
samples in multiple colours.

##  6 Acknowledgments

The authors would like to thank Lisa Hecker for her help constructing the
interferometric setup. C.F.K. acknowledges funding from the UK Engineering and
Physical Sciences Research Council (EP/L015889/1 and EP/H018301/1), the
Wellcome Trust (3-3249/Z/16/Z and 089703/Z/09/Z), the UK Medical Research
Council (MR/K015850/1 and MR/K02292X/1), and Infinitus Ltd. R.R.S.
acknowledges funding from the Biotechnology and Biological Sciences Research
Council through a BBSRC Discovery Fellowship (BB/X010228/1). R.R.S. and L.D.M.
acknowledge funding from the European Research Council (ERC) under the Horizon
2020 Research and Innovation Programme (ERC-STG No 851667 NANOCELL). L.D.M.
acknowledges funding from a Royal Society University Research Fellowship
(UF160152, URF$\backslash$R$\backslash$221009). G.S.K.S. acknowledges funding
from the Wellcome Trust (065807/Z/01/Z) (203249/Z/16/Z), the UK Medical
Research Council (MRC) (MR/K02292X/1), Alzheimer Research UK (ARUK) (ARUK-
PG013-14), Michael J Fox Foundation (16238 and 022159), and Infinitus China
Ltd. S.K. acknowledges funding from the UK Engineering and Physical Sciences
Research Council (EPSRC) grant EP/S023046/1 for the Centre for Doctoral
Training in Sensor Technologies for a Healthy and Sustainable Future. R.M.M.
and J.R.L. acknowledge funding from the UK Engineering and Physical Sciences
Research Council (EP/S022139/1).

##  7 Code Availability

Code available from https://github.com/edward-n-ward/ML-OS-SIM.

## References

  * [1] J. Huisken, J. Swoger, D. Bene, J. Wittbrodt, and E. H. K. Stelzer, “Optical Sectioning Deep Inside Live Embryos by Selective Plane Illumination Microscopy,” _Science_ , vol. 305, no. 5686, pp. 1007–1009, 2004. [Online]. Available: www.sciencemag.org/cgi/content/full/305/5686/1007/
  * [2] M. Tokunaga, N. Imamoto, and K. Sakata-Sogawa, “Highly inclined thin illumination enables clear single-molecule imaging in cells,” _Nature Methods_ , vol. 5, no. 2, pp. 159–161, 2 2008. [Online]. Available: doi.org/10.1038/nmeth1171
  * [3] M. A. A. Neil, R. Juškaitis, and T. Wilson, “Method of obtaining optical sectioning by using structured light in a conventional microscope,” _Optics Letters_ , vol. 22, no. 24, pp. 1905–1907, 1997. [Online]. Available: https://doi.org/10.1364/ol.22.001905
  * [4] R. Heintzmann and C. G. Cremer, “Laterally modulated excitation microscopy: improvement of resolution by using a diffraction grating,” in _Optical Biopsies and Microscopic Techniques III_ , vol. 3568. SPIE, 1 1999, pp. 185–196.
  * [5] M. G. L. Gustafsson, “Surpassing the lateral resolution limit by a factor of two using structured illumination microscopy,” _Journal of Microscopy_ , vol. 198, pp. 82–87, 2000. [Online]. Available: https://doi.org/10.1046/j.1365-2818.2000.00710.x
  * [6] Z. Li, Q. Zhang, S.-W. Chou, Z. Newman, R. Turcotte, R. Natan, Q. Dai, E. Y. Isacoff, and N. Ji, “Fast widefield imaging of neuronal structure and function with optical sectioning in vivo,” _Sci. Adv_ , vol. 6, 2020. [Online]. Available: https://www.science.org
  * [7] E. N. Ward, L. Hecker, C. N. Christensen, J. R. Lamb, M. Lu, L. Mascheroni, C. W. Chung, A. Wang, C. J. Rowlands, G. S. Schierle, and C. F. Kaminski, “Machine learning assisted interferometric structured illumination microscopy for dynamic biological imaging,” _Nature Communications_ , vol. 13, no. 1, 12 2022. [Online]. Available: https://doi.org/10.1038/s41467-022-35307-0
  * [8] E. Ward, “https://github.com/edward-n-ward/ML-OS-SIM,” 2023. [Online]. Available: https://github.com/edward-n-ward/ML-OS-SIM
  * [9] X. Chen, S. Zhong, Y. Hou, R. Cao, W. Wang, D. Li, Q. Dai, D. Kim, and P. Xi, “Superresolution structured illumination microscopy reconstruction algorithms: a review,” _Light: Science & Applications_, vol. 12, no. 1, p. 172, 7 2023. [Online]. Available: doi.org/10.1038/s41377-023-01204-4
  * [10] X. Zhang, Y. Chen, K. Ning, C. Zhou, Y. Han, H. Gong, and J. Yuan, “Deep learning optical-sectioning method,” _Optics Express_ , vol. 26, no. 23, p. 30762, 11 2018. [Online]. Available: doi.org/10.1364/OE.26.030762
  * [11] C. Chai, C. Chen, X. Liu, and Z. Lei, “Deep learning based one-shot optically-sectioned structured illumination microscopy for surface measurement,” _Optics Express_ , vol. 29, no. 3, p. 4010, 2 2021. [Online]. Available: doi.org/10.1364/oe.415210
  * [12] Y. Zhang, K. Li, K. Li, L. Wang, B. Zhong, and Y. Fu, “Image Super-Resolution Using Very Deep Residual Channel Attention Networks,” _ArXiv_ , 7 2018. [Online]. Available: https://doi.org/10.48550/arXiv.1807.02758
  * [13] J. Liang, J. Cao, G. Sun, K. Zhang, L. Van Gool, and R. Timofte, “SwinIR: Image Restoration Using Swin Transformer,” _ArXiv_ , 8 2021. [Online]. Available: https://doi.org/10.48550/arXiv.2108.10257
  * [14] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, J. Uszkoreit, and N. Houlsby, “An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale,” _ArXiv_ , 10 2020. [Online]. Available: https://doi.org/10.48550/arXiv.2010.11929
  * [15] C. N. Christensen, M. Lu, E. N. Ward, P. Lio, and C. F. Kaminski, “Spatio-temporal Vision Transformer for Super-resolution Microscopy,” _ArXiv_ , 2 2022. [Online]. Available: http://arxiv.org/abs/2203.00030
  * [16] R. Rubio-Sánchez, S. E. Barker, M. Walczak, P. Cicuta, and L. D. Michele, “A Modular, Dynamic, DNA-Based Platform for Regulating Cargo Distribution and Transport between Lipid Domains,” _Nano Letters_ , vol. 21, no. 7, pp. 2800–2808, 4 2021. [Online]. Available: https://doi.org/10.1021/acs.nanolett.0c04867
  * [17] M. Langecker, V. Arnaut, J. List, and F. C. Simmel, “DNA Nanostructures Interacting with Lipid Bilayer Membranes,” _Accounts of Chemical Research_ , vol. 47, no. 6, pp. 1807–1815, 6 2014. [Online]. Available: doi.org/10.1021/ar500051r
  * [18] R. Rubio-Sánchez, G. Fabrini, P. Cicuta, and L. Di Michele, “Amphiphilic DNA nanostructures for bottom-up synthetic biology,” _Chemical Communications_ , vol. 57, no. 95, pp. 12 725–12 740, 2021. [Online]. Available: doi.org/10.1039/d1cc04311k
  * [19] D. Y. Zhang and E. Winfree, “Control of DNA Strand Displacement Kinetics Using Toehold Exchange,” _Journal of the American Chemical Society_ , vol. 131, no. 47, pp. 17 303–17 314, 12 2009.
  * [20] D. Y. Zhang and G. Seelig, “Dynamic DNA nanotechnology using strand-displacement reactions,” _Nature Chemistry_ , vol. 3, no. 2, pp. 103–113, 2 2011.


Counting Dominating Sets in Directed Path Graphs Min-Sheng LinEmail:
<EMAIL_ADDRESS>Department of Electrical Engineering National Taipei
University of Technology Taipei 106, Taiwan, ROC

###### Abstract

A dominating set of a graph is a set of vertices such that every vertex not in
the set has at least one neighbor in the set. The problem of counting
dominating sets is #P-complete for chordal graphs but solvable in polynomial
time for its subclass of interval graphs. The complexity status of the
corresponding problem is still undetermined for directed path graphs, which
are a well-known class of graphs that falls between chordal graphs and
interval graphs. This paper reveals that the problem of counting dominating
sets remains #P-complete for directed path graphs but a stricter constraint to
rooted directed path graphs admits a polynomial-time solution.

Keywords — Algorithms; Dominating sets; Counting problem; Directed path
graphs.

##  Introduction

For a graph $G$, a subset $S$ of vertices of $G$ is a dominating set (DS) if
every vertex of $G$ not in $S$ is adjacent to a vertex in $S$. This paper
concerns the problem of computing the number of DSs in a graph. The problem of
counting dominating sets (abbr. #DS problem) is known to be #P-complete for
planar graphs [5], chordal graphs, chordal bipartite graphs [7], and tree
convex bipartite graphs [8]. Valiant [12] defined the class of #P problems as
those that involve counting access computations for problems in NP, and the
class of #P-complete problems includes the hardest problems in #P. As is well
known, all algorithms that exactly solve these problems have exponential time
complexity, so efficient algorithms for solving this class of problems are
unlikely to be developed. However, some polynomial-time algorithms for solving
problem #DS in interval graphs, trapezoid graphs [7], and rooted path-tree
bipartite graphs [8] have been found.

One very important class of graphs is the class of intersection graphs. Let
$F$ be a finite family of non-empty sets. A graph $G$ is an intersection graph
for $F$ if an isomorphism exists between the vertices of $G$ and the sets of
$F$ such that two vertices are adjacent if and only if their corresponding
sets in $F$ have a non-empty intersection. Examples of such graph classes are
chordal graphs and interval graphs.

Chordal graphs are graphs in which every cycle with a length of at least four
has a chord. Gavril [4] proved that chordal graphs are the intersection graphs
of a family of subtrees in a clique tree. A tree $T$ is a clique tree for a
graph $G$ if each node in $T$ corresponds to a maximal clique in $G$. To avoid
confusion with the vertices of graph $G$, the vertices of tree $T$ are called
nodes or clique nodes. Let $T_{v}$ denote the set of all cliques of $G$ that
contain vertex $v$. $G$ is a chordal graph if and only if $T_{v}$ is a subtree
in a clique tree $T$ for every vertex $v$ of $G$. The concept of chordal
graphs suggests definitions of some subclasses of chordal graphs. Undirected
path graphs are the intersection graphs of a family of undirected subpaths in
a clique tree. Directed path graphs are the intersection graphs of a family of
directed subpaths in a directed clique tree. Rooted directed path graphs are
the intersection graphs of a family of directed subpaths in a rooted directed
clique tree. A tree is called a rooted directed tree if one node has been
designated as the root, and the edges have a natural orientation away from the
root. Interval graphs are rooted directed path graphs in which the clique tree
is itself a path. These graph classes are related by the following proper
inclusions; interval graphs $\subset$ rooted directed path graphs $\subset$
directed path graphs $\subset$ undirected path graphs $\subset$ chordal graphs
[10].

The #DS problem remains #P-complete even for chordal graphs, but a polynomial-
time algorithm exists for solving the problem for interval graphs [7]. It is
known that one can count minimal dominating sets in strongly chordal graphs in
polynomial time [1] and, thus, for rooted directed path graphs which form a
proper subclass of strongly chordal graphs [2]. However, there is still no
direct approach to count all dominating sets for rooted directed path graphs.
The status of the #DS problem for undirected path graphs, directed path
graphs, and rooted directed path graphs has been undetermined until now. This
paper reveals that the #DS problem remains #P-complete even when restricted to
directed path graphs and undirected path graphs but that a stricter
restriction to rooted directed path graphs admits a polynomial-time solution.
Figure 1 summarizes the situation. Accordingly, the borderline between
polynomial and #P-complete problems is fully determined for some subclasses of
chordal graphs in Fig. 1.

Some notation and terminology are introduced for later use. The sets of
vertices and edges of a graph $G$ are denoted as $V(G)$ and $E(G)$,
respectively. The neighborhood of a vertex $v$ in a graph $G$, denoted by
$N_{G}(v)$, is the set of vertices that are adjacent to $v$ in $G$. A vertex
$v$ is said to dominate vertex $u$ if either $v=u$ or $v$ is adjacent to $u$;
that is, if $v{\in}N_{G}(u)\cup{u}$. For subsets $S,U\subseteq V(G)$, $S$ is
said to dominate $U$ in $G$ if for every vertex $u{\in}U$, there exists a
vertex $v{\in}S$ such that $v$ dominates $u$. Thus, a subset $S\subseteq V(G)$
is a dominating set in $G$ if and only if $S$ dominates $V(G)$. Let $\\#DS(G)$
denote the number of dominating sets in $G$.

Figure 1:  Status of #DS problem for some subclasses of chordal graphs. A
$\rightarrow$ B means that A is a subclass of B. Symbol * indicates a main
contribution of this paper.

##  #P-Completeness of the #DS problem for Directed Path Graphs

The #DS problem for split graphs and chordal graphs has been proved to be
#P-complete by reduction from the problem of counting independent sets of
bipartite graphs [7]. A slight variation of that reduction suffices to prove
that the #DS problem remains #P-complete even when restricted to directed path
graphs.

######  Theorem 1.

The #DS problem for directed path graphs is #P-complete.

###### Proof.

The reduction proceeds from the problem of counting edge covers in a bipartite
graph, which was proved to be #P-complete by Provan and Ball [11]. An edge
cover is a subset of edges that covers all the vertices. Let $B$ be an
arbitrary bipartite graph with vertex bipartition $X={x_{1},x_{2},…,x_{n}}$
and $Y={y_{1},y_{2},…,y_{m}}$, and let $N=n+m$ denote the number of vertices
of $B$. In the following steps, $N+1$ corresponding clique trees $T^{r}$, for
$1{\leq}r{\leq}N+1$, are constructed from $B$, from which $N+1$ directed path
graphs $G^{r}$ are obtained. The idea behind this construction is similar to
the reduction that was used in [9] to show the #P-completeness of the problem
of counting maximal independent sets in directed path graphs. First,
corresponding to each vertex $x_{i}{\in}X$, construct $r$ copies of clique
node $K^{s}_{i}=\\{x^{s}_{i}\\}\cup\\{e_{ij}:(x_{i},y_{j}){\in}E(B)\\}$, for
$1{\leq}s{\leq}r$. Next, corresponding to each vertex $y_{j}{\in}Y$, construct
$r$ copies of clique node
$H^{s}_{j}=\\{y^{s}_{j}\\}\cup\\{e_{ij}:(x_{i},y_{j}){\in}E(B)\\}$, for
$1{\leq}s{\leq}r$. Finally, construct one large clique node
$Q=\\{e_{ij}:(x_{i},y_{j}){\in}E(B)\\}$. Let $T^{r}$ be the directed clique
tree such that $V(T^{r})=\\{Q\\}\cup\\{K^{s}_{i}:1{\leq}s{\leq}r\text{ and
}1{\leq}i{\leq}n\\}\cup\\{H^{s}_{j}:1{\leq}s{\leq}r\text{ and
}1{\leq}j{\leq}m\\}$ is the set of clique nodes of $T^{r}$;
$E(T^{r})=\\{K^{r}_{i}{\rightarrow}K^{r-1}_{i}:1{\leq}i{\leq}n\\}\cup\\{K^{r-1}_{i}{\rightarrow}K^{r-2}_{i}:1{\leq}i{\leq}n\\}\cup...\cup\\{K^{2}_{i}{\rightarrow}K^{1}_{i}:1{\leq}i{\leq}n\\}\cup\\{K^{1}_{i}{\rightarrow}Q:1{\leq}i{\leq}n\\}\cup\\{Q{\rightarrow}H^{1}_{j}:1{\leq}j{\leq}m\\}\cup\\{H^{1}_{j}{\rightarrow}H^{2}_{j}:1{\leq}j{\leq}m\\}\cup...\cup\\{H^{r-1}_{j}{\rightarrow}H^{r}_{j}:1{\leq}j{\leq}m\\}$
is the set of directed edges of $T^{r}$. Figure 2 presents an example of the
above construction.

Let $G^{r}$ be the graph whose maximal cliques are the set $V(T^{r})$. The
resulting graph $G^{r}$, corresponding to the clique tree $T^{r}$, will now be
shown to be a directed path graph. Let
$X^{r}=\\{x^{s}_{i}:1{\leq}s{\leq}r\text{ and }1{\leq}i{\leq}n\\}$ and
$Y^{r}=\\{y^{s}_{j}:1{\leq}s{\leq}r\text{ and }1{\leq}j{\leq}m\\}$. Thus,
$V(G^{r})=X^{r}\cup Y^{r}\cup Q$. For $v{\in}V(G^{r})$, let $P_{v}$ be the set
of all clique nodes of $T^{r}$ that contain vertex $v$. If $v=x^{s}_{i}$ (or
$v=y^{s}_{j}$) is a vertex of $X^{r}$ (or $Y^{r}$, respectively) then $P_{v}$
comprises the single clique node $K^{s}_{i}$ (or $H^{s}_{j}$, respectively)
and $P_{v}$ is a directed path of length zero in $T^{r}$. If $v=e_{ij}$ is a
vertex of $Q$, then $P_{v}$ comprises the directed path
$K^{r}_{i}{\rightarrow}K^{r-1}_{i}{\rightarrow}...{\rightarrow}K^{1}_{i}{\rightarrow}Q{\rightarrow}H^{1}_{j}{\rightarrow}H^{2}_{j}{\rightarrow}...{\rightarrow}H^{r}_{j}$
of length $2r$ in $T^{r}$. Therefore, for each vertex $v{\in}V(G^{r})$,
$P_{v}$ is a directed path in $T^{r}$. Therefore, $G^{r}$ is a directed path
graph with the corresponding clique tree $T^{r}$.

Now, the relationship between the number of DSs in $G^{r}$, for
$1{\leq}r{\leq}N+1$, and the number of edge covers in $B$ will be established.
Clearly, every $G^{r}$, for $1{\leq}r{\leq}N+1$, is also a split graph with a
clique $Q$ and an independent set $X^{r}\cup Y^{r}$. Using the same strategy
and techniques as were used in [7], the number of DSs in $G^{1}$ is
$\\#DS(G^{1})=\sum_{S\subseteq Q}2^{\left|N_{G^{1}}(S)\cap(X^{1}\cup
Y^{1})\right|}$. Let $z_{k}=\left|\\{S\subseteq
Q:\left|N_{G^{1}}(S)\cap(X^{1}\cup Y^{1})\right|=k\\}\right|$. Thus,

$\\#DS(G^{1})=\sum_{k=0}^{N}z_{k}\cdot 2^{k}.$ (1)

Equation (1) can be generalized as

$\\#DS(G^{r})=\sum_{k=0}^{N}z_{k}\cdot(2^{k})^{r}=\sum_{k=0}^{N}z_{k}\cdot(2^{r})^{k},\text{
for }1\leq r\leq N+1.$ (2)

Additionally, Equation (2) can be expressed in matrix form as

$\mathcal{M}\times\begin{pmatrix}z_{0}\\\ z_{1}\\\ z_{2}\\\ \vdots\\\
z_{N}\end{pmatrix}=\begin{pmatrix}\\#DS(G^{1})\\\ \\#DS(G^{2})\\\
\\#DS(G^{3})\\\ \vdots\\\ \\#DS(G^{N+1})\end{pmatrix},$ (3)

where

$\mathcal{M}=\begin{pmatrix}1&\alpha_{1}^{\;1}&\alpha_{1}^{\;2}&\cdots&\alpha_{1}^{\,N}\\\
1&\alpha_{2}^{\;1}&\alpha_{2}^{\;2}&\cdots&\alpha_{2}^{\,N}\\\
1&\alpha_{3}^{\;1}&\alpha_{3}^{\;2}&\cdots&\alpha_{3}^{\,N}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
1&\alpha_{N+1}^{\;1}&\alpha_{N+1}^{\;2}&\cdots&\alpha_{N+1}^{\,N}\end{pmatrix}\text{
and }\alpha_{r}=2^{r}\text{ for }1\leq r\leq N+1.$ (4)

$\mathcal{M}$ is a well-known Vandermonde matrix and all $\alpha_{r}$, for
$1{\leq}r{\leq}N+1$, are distinct. Therefore, the determinant of $\mathcal{M}$
is non-zero. By Cramer’s rule, given the values for
$\\#DS(G^{1}),\\#DS(G^{2}),...,\\#DS(G^{N+1})$, the values of $z_{0}$,
$z_{1}$, …, and $z_{N}$ can be obtained in time that is polynomial in $N$.
Notably, an edge cover of a graph is a set of edges such that every vertex of
the graph is incident to at least one edge of the set. Thus, the number of
edge covers in the bipartite graph $B$ is given by

$\\#EC(B)=\left|\\{S\subseteq
E(B):|\cup_{(x_{i},y_{j}){\in}S}\\{x_{i},y_{j}\\}|=\left|V(B)\right|\\}\right|.$
(5)

Since $E(B)=Q$ and $|V(B)|=N$, $\\#EC(B)$ can be computed simply as $z_{N}$.
The reduction is thus completed in polynomial time. ∎

Since directed path graphs form a subclass of undirected path graphs, the
following corollary immediately follows.

######  Corollary 1.

The #DS problem for undirected path graphs is #P-complete.

Figure 2: Bipartite graph $B$ and constructed clique trees
$T^{r},1{\leq}r{\leq}6$.

##  Polynomial-time Algorithm for Counting DSs in Rooted Directed Path Graphs

This section describes a polynomial-time algorithm for solving the #DS problem
for rooted directed path graphs. First, assume that a clique tree $T$ has been
constructed for the rooted directed path graph $G$. This construction takes
only linear time using an easy modification to the recognition algorithm in
[3]. For $v{\in}V(G)$, let $P_{v}$ be the set of all nodes (cliques) of $T$
that contain vertex $v$. Therefore, $P_{v}$ forms a subpath in $T$ that is
directed away from the root of $T$. To simplify the description of the
algorithm, the clique tree $T$ of a rooted directed path graph $G$ is
transformed into an equivalent binary tree $BT$ by the following two steps.
Step 1: each path $P_{v}$ in $T$ is extended by appending a leaf node to the
ending node of $P_{v}$. Step 2: each node with an out-degree of $d>2$ in $T$
are split into $d-1$ nodes with an out-degree of 2; refer to Fig. 3 for
details [6]. Figure 4 presents an example of the above steps.

Figure 3: Transformation of a node with out-degree $d$.

Figure 4: Example of transforming a clique tree $T$ of a rooted directed path
graph $G$ into an equivalent binary tree $BT$.

For any node $k$ in $BT$, let $V(k)$ denote the vertices in node $k$ and let
$G_{k}$ be the subgraph of $G$ that is induced by $V(k)$ and the vertices that
are contained in all descendants of node $k$ in $BT$. The following property
is easily derived.

######  Property 1.

Suppose that node $k$ is an internal node of $BT$ and it has two children $i$
and $j$. Then,

$V(k)\subseteq V(i)\uplus V(j)\text{ and }V(G_{k})=V(G_{i})\uplus V(G_{j}).$

Let $S(k)$ be the collection of subsets $S$ of $V(G_{k})$ such that $S$
dominates $V(G_{k})\setminus V(k)$ in $G_{k}$. The collection $S(k)$ is
partitioned into three disjoint subsets, $A(k),B(k)$, and $C(k)$, determined
by whether $S$ contains or dominates the vertices of $V(k)$. For any node $k$
in $BT$,

$\displaystyle A(k):=$ $\displaystyle\\{S{\in}S(k):S\text{ contains some
vertex of }V(k).\\},$ $\displaystyle B(k):=$
$\displaystyle\\{S{\in}S(k):S\text{ contains no vertex of }V(k)\text{ and some
vertices of }V(k)\text{ are not dominated by }S.\\},\text{ and }$
$\displaystyle C(k):=$ $\displaystyle\\{S{\in}S(k):S\text{ contains no vertex
of }V(k)\text{ and all vertices of }V(k)\text{ are dominated by }S.\\}.$

Notably, all $S{\in}A(k)$ or $S{\in}C(k)$ dominate all vertices of $V(G_{k})$
so the number of DSs in $G$ is $|A(r)|+|C(r)|$, where $r$ is the root node of
$BT$. Define a strict partial order $<$ on $V(G)$ such that for any two
vertices $u,v{\in}V(G)$, $u<v$ if and only if either the starting node of path
$P_{u}$ is a descendant of the starting node of path $P_{v}$ in $BT$, or
$P_{u}$ and $P_{v}$ have the same starting node and $u$ appears before $v$ in
an arbitrary predefined sequence of vertices of $V(G)$. According to the
strict partial order $<$, $A(k)$ and $B(k)$ are further partitioned into
subsets $A(k,v)$ and $B(k,v)$, respectively, for $v{\in}V(k)$, as follows. For
any node $k$ in $BT$,

$\displaystyle A(k,v):=$ $\displaystyle\\{S{\in}A(k):v\text{ is the maximum
vertex (in the order $<$) of }S\cap V(k).\\},\text{ and }$ $\displaystyle
B(k,v):=$ $\displaystyle\\{S{\in}B(k):v\text{ is the minimum vertex (in the
order $<$) of }V(k)\text{ that is not dominated by }S.\\}.$

The following notation will be used in the proof below. Consider two
collections of sets $\Omega_{1}$ and $\Omega_{2}$, and assume that for each
$X_{1}{\in}\Omega_{1}$ and each $X_{2}{\in}\Omega_{2}$, $X_{1}$ and $X_{2}$
are disjoint sets. Let $X_{1}\uplus X_{2}$ denote the disjoint union of sets
$X_{1}$ and $X_{2}$. The operation $\times$ is defined by
$\Omega_{1}\times\Omega_{2}=\\{X_{1}\uplus X_{2}:X_{1}{\in}\Omega_{1}\text{
and }X_{2}{\in}\Omega_{2}\\}$.

######  Lemma 1.

Suppose that node $k$ is a leaf node of $BT$ and $V(k)=\\{v\\}$. Then

$A(k,v)=\large\\{\\{v\\}\large\\},B(k,v)=\\{\emptyset\\},\text{ and
}C(k)=\emptyset.$ (6)

###### Proof.

The lemma follows immediately from the above definitions. ∎

######  Lemma 2.

Suppose that node $k$ is an internal node of $BT$ and it has two children $i$
and $j$. For each vertex $v{\in}V(k)$, without loss of generality, assume
$v{\in}V(i)$. Then

$A(k,v)=A(i,v)\times\left\\{\left(\biguplus_{u{\in}V(j)\And
u<v}{A(j,u)}\right)\uplus\left(\biguplus_{u{\in}V(j)\cap
V(k)}{B(j,u)}\right)\uplus C(j)\right\\}.$ (7)

###### Proof.

Consider a DS $S{\in}A(k,v)$. By Property 1, $S$ can be partitioned into two
disjoint subsets $S_{i}$ and $S_{j}$, i.e. $S=S_{i}\uplus S_{j}$, where
$S_{i}=S\cap V(G_{i})$ and $S_{j}=S\cap V(G_{j})$. Since $v{\in}V(i)\cap V(k)$
and $v$ is the maximum vertex of $S\cap V(k)$, $v$ is also the maximum vertex
of $S_{i}\cap V(i)$, and hence $S_{i}{\in}A(i,v)$. Now consider three possible
cases of $S_{j}$.

Case 1: $S_{j}{\in}A(j)$. Notably, not all $S_{j}{\in}A(j)$ coincide with
$S_{i}{\in}A(i,v)$. Let $u{\in}V(j)$ be the maximum vertex of $S_{j}\cap
V(j)$. If $u{\in}V(k)$, then $u<v$, because $v$ is the maximum vertex of
$S\cap V(k)$. If $u{\notin}V(k)$, then node $j$ must be the starting node of
path $P_{u}$, and hence $u<v$. Therefore,
$S_{j}{\in}\biguplus\nolimits_{u{\in}V(j)\And u<v}{A(j,u)}$.

Case 2: $S_{j}{\in}B(j)$. Again, not all $S_{j}{\in}B(j)$ coincide with
$S_{i}{\in}A(i,v)$. Let $u{\in}V(j)$ be the minimum vertex of $V(j)$ that is
not dominated by $S_{j}$. Suppose $u{\notin}V(k)$. Then, $u$ is not dominated
by $S$, contradicting the fact that $S{\in}S(k)$ dominates all vertices of
$V(G_{k})\setminus V(k)$, and hence $u{\in}V(k)$. Therefore,
$S_{j}{\in}\biguplus\nolimits_{u{\in}V(j)\cap V(k)}{B(j,u)}$.

Case 3: $S_{j}{\in}C(j)$. Clearly, all $S_{j}{\in}C(j)$ coincide with
$S_{i}{\in}A(i,v)$.

From Cases 1-3,
$S{\in}A(i,v)\times\left\\{\left(\biguplus\nolimits_{u{\in}V(j)\And
u<v}{A(j,u)}\right)\uplus\left(\biguplus\nolimits_{u{\in}V(j)\cap
V(k)}{B(j,u)}\right)\uplus C(j)\right\\}$, and hence $A(k,v)\subseteq
A(i,v)\times\left\\{\left(\biguplus\nolimits_{u{\in}V(j)\And
u<v}{A(j,u)}\right)\uplus\left(\bigcup\nolimits_{u{\in}V(j)\cap
V(k)}{B(j,u)}\right)\uplus C(j)\right\\}$.

Conversely, let $S_{i}^{\prime}{\in}A(i,v)$ with $v{\in}V(i)\cap V(k)$.
Consider the following three cases of $S_{j}^{\prime}$.

Case 1: $S_{j}^{\prime}{\in}A(j,u)$ with $u{\in}V(j)$ and $u<v$. Clearly,
$S_{i}^{\prime}\uplus S_{j}^{\prime}{\in}A(k)$ because $S_{i}^{\prime}\uplus
S_{j}^{\prime}$ dominates $V(G_{i})\uplus V(G_{j})=V(G_{k})$ and
$S_{i}^{\prime}\uplus S_{j}^{\prime}$ contains some vertex $v$ of $V(k)$. By
the definitions of $A(i,v)$ and $A(j,u)$, $v$ and $u$ are the maximum vertices
of $S_{i}^{\prime}\cap V(i)$ and $S_{j}^{\prime}\cap V(j)$, respectively.
Since $u<v$, $v$ is the maximum vertex of $(S_{i}^{\prime}\cap
V(i))\uplus(S_{j}^{\prime}\cap V(j))$. Notably, $(S_{i}^{\prime}\cap
V(i))\uplus(S_{j}^{\prime}\cap V(j))=(S_{i}^{\prime}\uplus
S_{j}^{\prime})\cap(V(i)\uplus V(j))$ and $V(k)\subseteq V(i)\uplus V(j)$ by
Property 1. Hence, $v$ is the maximum vertex of $(S_{i}^{\prime}\uplus
S_{j}^{\prime})\cap V(k)$. Thus, $S_{i}^{\prime}\uplus
S_{j}^{\prime}{\in}A(k,v)$ and $A(i,v)\times\biguplus\nolimits_{u{\in}V(j)\And
u<v}{A(j,u)}\subseteq A(k,v)$.

Case 2: $S_{j}^{\prime}{\in}B(j,u)$ with $u{\in}V(j)\cap V(k)$. By the
definition of $B(j,u)$, $u$ is the minimum vertex of $V(j)$ that is not
dominated by $S_{j}^{\prime}$. Thus, for each vertex $w{\in}V(j)$ that is not
dominated by $S_{j}^{\prime},w\geq u$, and since $u{\in}V(k),w{\in}V(k)$.
Thus, $w$ is dominated by the vertex $v{\in}S_{i}^{\prime}$ so
$S_{i}^{\prime}\uplus S_{j}^{\prime}$ dominates all vertices of $V(j)$.
Therefore, $S_{i}^{\prime}\uplus S_{j}^{\prime}$ dominates $V(G_{i})\uplus
V(G_{j})=V(G_{k})$. Furthermore, since $v$ is the maximum vertex of
$(S_{i}^{\prime}\uplus S_{j}^{\prime})\cap V(k),S_{i}^{\prime}\uplus
S_{j}^{\prime}{\in}A(k,v)$. Thus,
$A(i,v)\times\biguplus\nolimits_{u{\in}V(j)\cap V(k)}{B(j,u)}\subseteq
A(k,v)$.

Case 3: $S_{j}^{\prime}{\in}C(j)$. By the definition of $C(j),S_{j}^{\prime}$
dominates $V(G_{j})$ so $S_{i}^{\prime}\uplus S_{j}^{\prime}$ dominates
$V(G_{i})\uplus V(G_{j})=V(G_{k})$. In addition, $S_{j}^{\prime}$ contains no
vertex of $V(j)$ so contains no vertex $V(k)$. Thus, $v$ is the maximum vertex
of $(S_{i}^{\prime}\uplus S_{j}^{\prime})\cap V(k)$. Therefore,
$S_{i}^{\prime}\uplus S_{j}^{\prime}{\in}A(k,v)$ and $A(i,v)\times
C(j)\subseteq A(k,v)$.

From the above Cases 1-3,
$A(i,v)\times\left\\{\left(\biguplus\nolimits_{u{\in}V(j)\And
u<v}{A(j,u)}\right)\uplus\left(\biguplus\nolimits_{u{\in}V(j)\cap
V(k)}{B(j,u)}\right)\uplus C(j)\right\\}\subseteq A(k,v)$ and the lemma
follows. ∎

######  Lemma 3.

Suppose that node $k$ is an internal node of $BT$ and it has two children $i$
and $j$. For each vertex $v{\in}V(k)$, without loss of generality, assume
$v{\in}V(i)$. Then

$B(k,v)=B(i,v)\times\left\\{\left(\biguplus_{u{\in}V(j)\setminus
V(k)}{A(j,u)}\right)\uplus\left(\biguplus_{u>v\And u{\in}V(j)\cap
V(k)}{B(j,u)}\right)\uplus C(j)\right\\}.$ (8)

###### Proof.

Consider a DS $S{\in}B(k,v)$. Let $S_{i}=S\cap V(G_{i})$ and $S_{j}=S\cap
V(G_{j})$. Let $w{\in}V(i)$ be not dominated by $S_{i}$, and hence not
dominated by $S$. Suppose $w<v$. Since $v$ is the minimum vertex of $V(k)$
that is not dominated by $S$, $w{\notin}V(k)$. Thus, there exists some vertex
$w{\in}V(G_{k})\setminus V(k)$ that is not dominated by $S$, contradicting the
fact that $S{\in}S(k)$, and hence $w\geq v$. Thus, $v$ is also the minimum
vertex of $V(i)$ that is not dominated by $S_{i}$. Hence, $S_{i}{\in}B(i,v)$.
Now consider three possible cases of $S_{j}$.

Case 1: $S_{j}{\in}A(j)$. Since $S{\in}B(k,v)$, $S_{j}$ contains no vertex of
$V(k)$. Thus, $S_{j}{\in}\biguplus\nolimits_{u{\in}V(j)\setminus
V(k)}{A(j,u)}$.

Case 2: $S_{j}{\in}B(j)$. Let $u{\in}V(j)$ where $u$ is not dominated by $S$,
and therefore also not dominated by $S_{j}$. Suppose $u{\notin}V(k)$. Thus,
there exists a vertex $u{\in}V(G_{k})\setminus V(k)$ that is not dominated by
$S$, contradicting the fact that $S{\in}S(k)$, and hence $u{\in}V(k)$.
Additionally, since $v$ is the minimum vertex of $V(k)$ that is not dominated
by $S$, $u>v$. Thus, $S_{j}{\in}\biguplus\nolimits_{u>v\And u{\in}V(j)\cap
V(k)}{B(j,u)}$.

Case 3: $S_{j}{\in}C(j)$. Clearly, all $S_{j}{\in}C(j)$ coincide with
$S_{i}{\in}B(i,v)$.

Therefore, from Cases 1-3,
$S{\in}B(i,v)\times\left\\{\left(\biguplus\nolimits_{u{\in}V(j)\setminus
V(k)}{A(j,u)}\right)\uplus\left(\biguplus\nolimits_{u<v\And u{\in}V(j)\cap
V(k)}{B(j,u)}\right)\uplus C(j)\right\\}$ and $B(k,v)\subseteq
B(i,v)\times\left\\{\left(\biguplus\nolimits_{u{\in}V(j)\setminus
V(k)}{A(j,u)}\right)\uplus\left(\biguplus\nolimits_{u>v\And u{\in}V(j)\cap
V(k)}{B(j,u)}\right)\uplus C(j)\right\\}$.

Conversely, let $S_{i}^{\prime}{\in}B(i,v)$ with $v{\in}V(i)\cap V(k)$.
Consider the following three cases of $S_{j}^{\prime}$.

Case 1: $S_{j}^{\prime}{\in}A(j,u)$ with $u{\in}V(j)\setminus V(k)$. Clearly,
$S_{i}^{\prime}$ contains no vertex of $V(i)$ so it contains no vertex of
$V(k)$. Since $u$ is the maximum vertex of $S_{j}^{\prime}\cap V(j)$ and
$u{\notin}V(k)$, $S_{j}^{\prime}$ contains no vertex of $V(k)$. Thus,
$S_{i}^{\prime}\uplus S_{j}^{\prime}$ contains no vertex of $V(k)$, Thus,
$S_{i}^{\prime}\uplus S_{j}^{\prime}{\in}B(k)$. Additionally, $v$ is the
minimum vertex of $V(i$) that is not dominated by $S_{i}^{\prime}$. Hence, $v$
is the minimum vertex of $V(i)\cap V(k)$ that is not dominated by
$S_{i}^{\prime}$. Since $S_{j}^{\prime}$ contains $u{\in}V(j)$, all vertices
of $V(j)\cap V(k)$ are dominated by $S_{j}^{\prime}$. Thus, $v$ is the minimum
vertex of $V(k)=(V(i)\cap V(k))\uplus(V(j)\cap V(k))$ that is not dominated by
$S_{i}^{\prime}\uplus S_{j}^{\prime}$. Hence, $S_{i}^{\prime}\uplus
S_{j}^{\prime}{\in}B(k,v)$ and
$B(i,v)\times\biguplus\nolimits_{u{\in}V(j)\setminus V(k)}{A(j,u)}\subseteq
B(k,v)$.

Case 2: $S_{j}^{\prime}{\in}B(j,u)$ with $u>v$ and $u{\in}V(j)\cap V(k)$.
Clearly, $S_{i}^{\prime}\uplus S_{j}^{\prime}$ contains no vertex of $V(k)$
and $v$ is the minimum vertex of $V(k)$ that is not dominated by
$S_{i}^{\prime}\uplus S_{j}^{\prime}$. Thus, $S_{i}^{\prime}\uplus
S_{j}^{\prime}{\in}B(k,v)$ and $B(i,v)\times\biguplus\nolimits_{u>v\And
u{\in}V(j)\cap V(k)}{B(j,u)}\subseteq B(k,v)$.

Case 3: $S_{j}^{\prime}{\in}C(j)$. By the definition of $C(j)$, $S_{j}$
dominates all vertices of $V(j)$ so it also dominates all vertices of
$V(j)\cap V(k)$. In addition, $S_{j}$ contains no vertex of $V(j)$, and
therefore contains no vertex $V(k)$. Thus, $S_{i}^{\prime}\uplus
S_{j}^{\prime}$ contains no vertex of $V(k)$ and $v$ is the minimum vertex of
$V(k)$ that is not dominated by $S_{i}^{\prime}\uplus S_{j}^{\prime}$.
Therefore, $S_{i}^{\prime}\uplus S_{j}^{\prime}{\in}B(k,v)$ and $B(i,v)\times
C(j)\subseteq B(k,v)$.

From the above Cases 1-3,
$B(i,v)\times\left\\{\left(\biguplus\nolimits_{u{\in}V(j)\setminus
V(k)}{A(j,u)}\right)\uplus\left(\biguplus\nolimits_{u>v\And u{\in}V(j)\cap
V(k)}{B(j,u)}\right)\uplus C(j)\right\\}\subseteq B(k,v)$ and the lemma
follows. ∎

######  Lemma 4.

Suppose that node $k$ is an internal node of $BT$ and it has two children $i$
and $j$. Then

$C(k)=\left\\{\left(\biguplus_{u{\in}V(i)\setminus V(k)}{A(i,u)}\right)\uplus
C(i)\right\\}\times\left\\{\left(\biguplus_{u{\in}V(j)\setminus
V(k)}{A(j,u)}\right)\uplus C(j)\right\\}.$ (9)

###### Proof.

Consider a DS $S{\in}C(k)$. Let $S_{i}=S\cap V(G_{i})$ and $S_{j}=S\cap
V(Gj)$. Consider three possible cases of $S_{i}$.

Case 1: $S_{i}{\in}A(i)$. By the definition of $C(k)$, $S$ contains no vertex
of $V(k)$ so $S_{i}{\in}\biguplus\nolimits_{u{\in}V(i)\setminus
V(k)}{A(i,u)}$.

Case 2: $S_{i}{\in}B(i)$. Let $w{\in}V(i)$ be a vertex that is not dominated
by $S_{i}$, and hence $w$ is not dominated by $S$. Since $S$ dominates all
vertices of $V(k),w{\notin}V(k)$, contradicting the fact that $S{\in}S(k)$
dominates all vertices of $V(G_{k})\setminus V(k)$. Therefore,
$S_{i}{\notin}B(i)$.

Case 3: $S_{i}{\in}C(i)$. Clearly, all $S_{i}{\in}C(i)$ coincide with
$S{\in}C(k)$.

From the above Cases 1-3,
$S_{i}{\in}\left(\biguplus\nolimits_{u{\in}V(i){\setminus}V(k)}{A(i,u)}\right)\uplus
C(i)$. Similarly,
$S_{j}{\in}\left(\biguplus\nolimits_{u{\in}V(j){\setminus}V(k)}{A(j,u)}\right)\uplus
C(j)$. Thus,
$C(k)\subseteq\left\\{\left(\biguplus\nolimits_{u{\in}V(i){\setminus}V(k)}{A(i,u)}\right)\uplus
C(i)\right\\}\times\left\\{\left(\biguplus\nolimits_{u{\in}V(j){\setminus}V(k)}{A(j,u)}\right)\uplus
C(j)\right\\}$.

Conversely, consider the following four cases.

Case 1: $S_{i}^{\prime}{\in}A(i,v)$ with $v{\in}V(i){\setminus}V(k)$ and
$S_{j}^{\prime}{\in}A(j,u)$ with $u{\in}V(j){\setminus}V(k)$. Since
$v{\in}V(i){\setminus}V(k)$ and $v$ is the maximum vertex of
$S_{i}^{\prime}\cap V(i),S_{i}^{\prime}$ contains no vertex of $V(k)$. Since
$S_{i}^{\prime}$ dominates all vertex of $V(i)$, $S_{i}^{\prime}$ dominates
all vertices of $V(i)\cap V(k)$. Similarly, $S_{j}^{\prime}$ contains no
vertex of $V(k)$ and dominates all vertices of $V(j)\cap V(k)$. Thus,
$S_{i}^{\prime}\uplus S_{j}^{\prime}$ contains no vertex of $V(k)$ and
dominates all vertices of $(V(i)\cap V(k))\uplus(V(j)\cap V(k))=V(k)$. Hence,
$S_{i}^{\prime}\uplus S_{j}^{\prime}{\in}C(k)$ and
$\left(\biguplus\nolimits_{v{\in}V(i){\setminus}V(k)}{A(i,v)}\right)\times\left(\biguplus\nolimits_{u{\in}V(j){\setminus}V(k)}{A(j,u)}\right)\subseteq
C(k)$.

Case 2: $S_{i}^{\prime}{\in}A(i,v)$ with $v{\in}V(i){\setminus}V(k)$ and
$S_{j}^{\prime}{\in}C(j)$. By an argument similar to that in Case 1,
$S_{i}^{\prime}$ contains no vertex of $V(k)$ and all vertices of $V(i)\cap
V(k)$ are dominated by $S_{i}^{\prime}$. By the definition of $C(j)$,
$S_{j}^{\prime}$ contains no vertex of $V(j)$ and dominates all vertices of
$V(j)$. Hence, $S_{j}^{\prime}$ contains no vertex of $V(k)$ and dominates all
vertices of $V(j)\cap V(k)$. Therefore, $S_{i}^{\prime}\uplus S_{j}^{\prime}$
contains no vertex of $V(k)$ and dominates all vertices of $V(k)$. Hence,
$S_{i}^{\prime}\uplus S_{j}^{\prime}{\in}C(k)$ and
$\left(\biguplus\nolimits_{v{\in}V(i){\setminus}V(k)}{A(i,v)}\right)\times
C(j)\subseteq C(k)$.

Case 3: $S_{i}^{\prime}{\in}C(i)$ and $S_{j}^{\prime}{\in}A(j,u)$ with
$u{\in}V(j){\setminus}V(k)$. By an argument similar to that in Case 2,
$S_{i}^{\prime}\uplus S_{j}^{\prime}$ contains no vertex of $V(k)$ and
dominates all vertices of $V(k)$. Hence, $S_{i}^{\prime}\uplus
S_{j}^{\prime}{\in}C(k)$ and
$C(i)\times\left(\biguplus\nolimits_{u{\in}V(j){\setminus}V(k)}{A(j,u)}\right)\subseteq
C(k)$.

Case 4: $S_{i}^{\prime}{\in}C(i)$ and $S_{j}^{\prime}{\in}C(j)$. By an
argument similar to that in Case 2, $S_{i}^{\prime}$ contains no vertex of
$V(k)$ and dominates all vertices of $V(i)\cap V(k)$. Similarly,
$S_{j}^{\prime}$ contains no vertex of $V(k)$ and dominates all vertices of
$V(j)\cap V(k)$. Thus, $S_{i}^{\prime}\uplus S_{j}^{\prime}{\in}C(k)$ and
$C(i)\times C(j)\subseteq C(k)$.

From the above Cases 1-4,
$\left\\{\left(\biguplus\nolimits_{v{\in}V(i){\setminus}V(k)}{A(i,v)}\right)\uplus
C(i)\right\\}\times\left\\{\left(\biguplus\nolimits_{u{\in}V(j){\setminus}V(k)}{A(j,u)}\right)\uplus
C(j)\right\\}\subseteq C(k)$ and the lemma follows. ∎

Let $\Omega_{1}$ and $\Omega_{2}$ be two collections of sets. By the
definitions of operations $\times$ and $\uplus$,
$|\Omega_{1}\times\Omega_{2}|=|\Omega_{1}|\cdot|\Omega_{2}|$ and
$|\Omega_{1}\uplus\Omega_{2}|=|\Omega_{1}|+|\Omega_{2}|$. Thus, based on
Lemmas 1-4, the following algorithm can be used to count DSs in a rooted
directed path graph.

Input: A rooted directed path graph $G$.

Output: The number of DSs in $G$.

Construct a rooted directed clique tree $T$;

Transform $T$ into an equivalent binary tree $BT$ with root node $r$;

foreach  _node $k{\in}BT$ encountered in the post-order traversal of $BT$_ do

if  _node $k$ is a leaf node with $V(k)=\\{v\\}$_ then

$|A(k,v)|{\leftarrow}1;|B(k,v)|{\leftarrow}1;|C(k)|{\leftarrow}0$;

else

// node $k$ is an internal node of $BT$ with two children

foreach  _vertex $v{\in}V(k)$_ do

node $i\leftarrow$ the child of node $k$ that contains $v$;

node $j\leftarrow$ the child of node $k$ that does not contains $v$;

$|A(k,v)|{\leftarrow}|A(i,v)|\cdot\left(\sum\nolimits_{u{\in}V(j)\And
u<v}{|A(j,u)|}+\sum\nolimits_{u{\in}V(j)\cap V(k)}{|B(j,u)|}+|C(j)|\right)$;

$|B(k,v)|{\leftarrow}|B(i,v)|\cdot\left(\sum\nolimits_{u{\in}V(j){\setminus}V(k)}{|A(j,u)}|+\sum\nolimits_{u>v\And
u{\in}V(j)\cap V(k)}{|B(j,u)|}+|C(j)|\right)$;

$|C(k)|{\leftarrow}\left(\sum\nolimits_{u{\in}V(i)\setminus
V(k)}{|A(i,u)}|+|C(i)|\right)\cdot\left(\sum\nolimits_{u{\in}V(j)\setminus
V(k)}{|A(j,u)}|+|C(j)|\right)$;

end foreach

end foreach

return _ $\sum\nolimits_{v{\in}V(r)}{|A(r,v)|}+|C(r)|$_;

Algorithm 1 Counting DSs in a rooted directed path graph

######  Theorem 2.

For a rooted directed path graph with $n$ vertices, the #DS problem is
solvable in $O(n^{3})$ time.

###### Proof.

The correctness of Algorithm 1 follows from Lemmas 1-4. The time complexity of
Algorithm 1 is analyzed as follows. Given a rooted directed path graph $G$
with $n$ vertices, the clique tree $T$ can be constructed in linear time by
making a simple modification to the recognition algorithm of Dietz et al. [3].
Since $T$ has no more than $n$ nodes, $T$ can be transformed into an
equivalent binary tree $BT$ in $O(n^{2})$ time. All nodes, except leaf nodes,
in $BT$ have an out-degree of 2 and the number of leaf nodes is $n$. Hence,
the total number of nodes in $BT$ is $2n-1$. Thus, Algorithm 1 takes
$O(n^{3})$ time to compute all $|A(k,v)|,|B(k,v)|$, and $|C(k)|$.
Consequently, the number of DSs in a rooted directed path graph with $n$
vertices can be computed in $O(n^{3})$ time. ∎

##  Conclusions

This paper is the first to determine the complexity of the #DS problem for two
subclasses of chordal graphs - directed path graphs and rooted directed path
graphs. The #DS problem is proved to remain #P-complete when restricted to
directed path graphs but a further restriction to rooted directed path graphs
admits a solution in polynomial time.

## References

  * [1] B. Bergougnoux, F. Capelli, and M. M. Kanté.  Counting minimal transversals of $\beta$-acyclic hypergraphs.  Journal of Computer and System Sciences, 101:21–30, 2019.
  * [2] A. Brandstädt, C. Hundt, F. Mancini, and P. Wagner.  Rooted directed path graphs are leaf powers.  Discrete Mathematics, 310(4):897–910, 2010.
  * [3] P. F. Dietz, M. Furst, and J. E. Hopcroft.  A linear time algorithm for the generalized consecutive retrieval problem.  Technical report, Cornell University, 1979.
  * [4] F. Gavril.  The intersection graphs of subtrees in trees are exactly the chordal graphs.  Journal of Combinatorial Theory, Series B, 16(1):47–56, 1974.
  * [5] H. B. Hunt III, M. V. Marathe, V. Radhakrishnan, and R. E. Stearns.  The complexity of planar counting problems.  SIAM Journal on Computing, 27(4):1142–1167, 1998.
  * [6] K. Jansen, P. Scheffler, and G. Woeginger.  The disjoint cliques problem.  RAIRO-Operations Research, 31(1):45–66, 1997.
  * [7] S. Kijima, Y. Okamoto, and T. Uno.  Dominating set counting in graph classes.  In International Computing and Combinatorics Conference, pages 13–24. Springer, 2011.
  * [8] M.-S. Lin.  Counting dominating sets in some subclasses of bipartite graphs.  Theoretical Computer Science, 923:337–347, 2022.
  * [9] M.-S. Lin and S.-H. Su.  Counting maximal independent sets in directed path graphs.  Information Processing Letters, 114(10):568–572, 2014.
  * [10] C. L. Monma and V. K. Wei.  Intersection graphs of paths in a tree.  Journal of Combinatorial Theory, Series B, 41(2):141–181, 1986\.
  * [11] J. S. Provan and M. O. Ball.  The complexity of counting cuts and of computing the probability that a graph is connected.  SIAM Journal on Computing, 12(4):777–788, 1983.
  * [12] L. G. Valiant.  The complexity of enumeration and reliability problems.  SIAM Journal on Computing, 8(3):410–421, 1979.