×

A method for enumerating pairwise compatibility graphs with a given number of vertices. (English) Zbl 1472.05068

Summary: N. A. Azam et al. [“Enumerating all pairwise compatibility graphs with a given number of vertices based on linear programming”, in: Proceedings of 2nd International Workshop on Enumeration Problems and Applications, WEPA, Pisa, Italy. 5–8 (2018)] proposed a method to enumerate all pairwise compatibility graphs (PCGs) with a given number \(n\) of vertices. For a tuple \(( G , T , \sigma , \lambda )\) of a graph \(G\) with \(n\) vertices and a tree \(T\) with \(n\) leaves, a bijection \(\sigma\) between the vertices in \(G\) and the leaves in \(T\), and a bi-partition \(\lambda\) of the set of non-adjacent vertex pairs in \(G\), they formulated two linear programs, LP\(( G , T , \sigma , \lambda )\) and DLP\(( G , T , \sigma , \lambda )\) such that: exactly one of them is feasible; and \(G\) is a PCG if and only if LP\(( G , T , \sigma , \lambda )\) is feasible for some tuple \(( G , T , \sigma , \lambda )\). To reduce the number of graphs \(G\) with \(n\) vertices (resp., tuples) for which the LPs are solved, they excluded PCGs by heuristically generating PCGs (resp., some tuples that contain a sub-tuple \(( G^\prime , T^\prime , \sigma^\prime , \lambda^\prime )\) for \(n = 4\) whose LP\(( G^\prime , T^\prime , \sigma^\prime , \lambda^\prime )\) is infeasible). This paper proposes two improvements in the method: derive a sufficient condition for a graph to be a PCG for a given tree in order to exclude more PCGs; and characterize all sub-tuples \(( G^\prime , T^\prime , \sigma^\prime , \lambda^\prime )\) for \(n = 4\) for which LP\(( G^\prime , T^\prime , \sigma^\prime , \lambda^\prime )\) is infeasible, and enumerate tuples that contain no such sub-tuples by a branch-and-bound algorithm. Experimental results show that our method more efficiently enumerated all PCGs for \(n = 8\).

MSC:

05C30 Enumeration in graph theory
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
90C05 Linear programming

Software:

nauty; Traces
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] N.A. Azam, M. Ito, A. Shurbevski, H. Nagamochi, Enumerating all pairwise compatibility graphs with a given number of vertices based on linear programming, in: Proceedings of 2nd International Workshop on Enumeration Problems and Applications, WEPA, Pisa, Italy, 5-8 2018, WEPA2018 6c.
[2] Baiocchi, P.; Calamoneri, T.; Monti, A.; Petreschi, R., Some classes of graphs that are not PCGs, Theoret. Comput. Sci. (2019) · Zbl 1433.05307
[3] Calamoneri, T.; Frangioni, A.; Sinaimeri, B., Pairwise compatibility graphs of caterpillars, Comput. J., 57, 1616-1623 (2014)
[4] Calamoneri, T.; Frascaria, D.; Sinaimeri, B., All graphs with at most seven vertices are pairwise compatibility graphs, Comput. J., 56, 7, 882-886 (2013)
[5] Calamoneri, T.; Sinaimeri, B., Pairwise compatibility graphs: A survey, SIAM Rev., 58, 3, 445-460 (2016) · Zbl 1342.05058
[6] Calamoneri, T.; T; Montefusco, E.; Petreschi, R.; Sinaimeri, B., Exploring pairwise compatibility graphs, Theoret. Comput. Sci., 468, 23-26 (2013) · Zbl 1258.05104
[7] Durocher, S.; Mondal, D.; Rahman, M. S., On graphs that are not PCGs, Theoret. Comput. Sci., 571, 78-87 (2015) · Zbl 1306.05085
[8] Gale, D., The Theory of Linear Economic Models (1960), MacGraw-Hill · Zbl 0114.12203
[9] P.E. Kearney, J.I. Munro, D. Phillips, Efficient generation of uniform samples from phylogenetic trees, in: International Workshop on Algorithms in Bioinformatics, 2003, pp. 177-189.
[10] McKay, B. D.; Piperno, A., Practical graph isomorphism, II, J. Symbolic Comput., 60, 94-112 (2014) · Zbl 1394.05079
[11] Xiao, M.; Nagamochi, H., Some reduction operations to pairwise compatibility graphs, Inform. Process. Lett., 153, Article 105875 pp. (2020) · Zbl 1481.05150
[12] Yanhaona, N. M.; Bayzid, M. S.; Rahman, M. S., Discovering pairwise compatibility graphs, Discrete Math. Algorithms Appl., 2, 4, 479-503 (2010) · Zbl 1180.68204
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.