×

Counting independent sets in tree convex bipartite graphs. (English) Zbl 1352.05146

Summary: The problems of counting independent sets, maximal independent sets, and independent perfect dominating sets are \(\# \mathrm{P}\)-complete for bipartite graphs, but can be solved in polynomial time for convex bipartite graphs, which are a subclass of bipartite graphs This paper studies these problems for tree convex bipartite graphs, which are a class of graphs between bipartite graphs and convex bipartite graphs. A bipartite graph \(G\) with bipartition \((X\, Y)\) is called tree convex, if a tree \(T\) defined on \(X\) exists, such that for every vertex \(y\) in \(Y\), the neighbors of \(y\) form a subtree of \(T\) If the associated tree \(T\) is simply a path, then \(G\) is just a convex bipartite graph. This paper first proves that the problems of counting independent sets, maximal independent sets, and independent perfect dominating sets remain \(\# \mathrm{P}\)-complete for tree convex bipartite graphs even when the associated tree \(T\) is only a comb or a star. This paper then presents polynomial-time algorithms to solve these problems for tree convex bipartite graphs when the associated tree \(T\) is restricted to a triad, which consists of three paths with one common endpoint.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C30 Enumeration in graph theory
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chain-Chin, Y.; Lee, R. C., The weighted perfect domination problem and its variants, Discrete Appl. Math., 66, 2, 147-160 (1996) · Zbl 0848.05042
[2] Chen, H.; Lei, Z.; Liu, T.; Tang, Z.; Wang, C.; Xu, K., Complexity of domination, hamiltonicity and treewidth for tree convex bipartite graphs, J. Comb. Optim., 1-16 (2015)
[3] Glover, F., Maximum matching in a convex bipartite graph, Naval Res. Logist. Q., 14, 3, 313-316 (1967) · Zbl 0183.24501
[4] Hunt, H. B.; Marathe, M. V.; Radhakrishnan, V.; Stearns, R. E., The complexity of planar counting problems, SIAM J. Comput., 27, 4, 1142-1167 (1998) · Zbl 0911.68060
[5] Jiang, W.; Liu, T.; Ren, T.; Xu, K., Two hardness results on feedback vertex sets, (Frontiers in Algorithmic and Algorithmic Aspects in Information and Management (2011), Springer: Springer Berlin, Heidelberg), 233-243 · Zbl 1329.68125
[6] Jiang, W.; Liu, T.; Wang, C.; Xu, K., Feedback vertex sets on restricted bipartite graphs, Theoret. Comput. Sci., 507, 41-51 (2013) · Zbl 1302.05191
[7] Lin, M. S., Fast and simple algorithms to count the number of vertex covers in an interval graph, Inform. Process. Lett., 102, 4, 143-146 (2007) · Zbl 1185.05137
[8] Lin, M. S.; Su, S. H., Counting independent sets in a tolerance graph, Discrete Appl. Math., 181, 174-184 (2015) · Zbl 1304.05106
[9] Okamoto, Y.; Uno, T.; Uehara, R., Counting the number of independent sets in chordal graphs, J. Discrete Algorithms, 6, 2, 229-242 (2008) · Zbl 1146.05029
[10] Provan, J. S.; Ball, M. O., The complexity of counting cuts and of computing the probability that a graph is connected, SIAM J. Comput., 12, 4, 777-788 (1983) · Zbl 0524.68041
[11] Song, Y.; Liu, T.; Xu, K., Independent domination on tree convex bipartite graphs, (Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (2012), Springer: Springer Berlin, Heidelberg), 129-138 · Zbl 1304.68064
[12] Vadhan, S. P., The complexity of counting in sparse, regular, and planar graphs, SIAM J. Comput., 31, 2, 398-427 (2001) · Zbl 0994.68070
[13] Valiant, L. G., The complexity of enumeration and reliability problems, SIAM J. Comput., 8, 3, 410-421 (1979) · Zbl 0419.68082
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.