On the enumeration of minimal non-pairwise compatibility graphs

Naveed Ahmed Azam (), Aleksandar Shurbevski () and Hiroshi Nagamochi ()
Additional contact information
Naveed Ahmed Azam: Kyoto University
Aleksandar Shurbevski: Kyoto University
Hiroshi Nagamochi: Kyoto University

Journal of Combinatorial Optimization, 2022, vol. 44, issue 4, No 37, 2892 pages

Abstract: Abstract A graph is said to be a pairwise compatibility graph (PCG) if there exists an edge-weighted tree whose leaf set is the graph’s vertex set, and there exists an edge between two vertices in the graph if and only if the distance between them in the tree lies within a given interval. It is a challenging task to enumerate all non-PCGs that are minimal in the sense that each of their induced subgraphs is a PCG and deliver proof of this fact. First, it involves a large number of combinatorial decisions concerning the structure of a tree and leaf-vertex correspondence. Moreover, there exists an infinite continuous domain for the edge weights even for a fixed tree. We handle the combinatorial problem by first screening graphs that are PCGs using a heuristic PCG generator. Then, we construct “configurations” that show some graphs to be PCGs. Finally, we generate configurations without including those that cannot be used to show that a given graph is a PCG. In order to construct finite-sized evidence to a graph being a minimal non-PCG in the face of an infinite search space, we use linear programming (LP) formulations whose solutions serve as evidence. To demonstrate our approach, we enumerated all minimal non-PCGs with nine vertices, which were unknown. We prove that there are exactly 1494 minimal non-PCGs with nine vertices and provide evidence for each of them.

Keywords: Pairwise compatibility graph; Branch-and-bound algorithm; Linear programming (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00799-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:4:d:10.1007_s10878-021-00799-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00799-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().