IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v44y2022i4d10.1007_s10878-021-00799-x.html
   My bibliography  Save this article

On the enumeration of minimal non-pairwise compatibility graphs

Author

Listed:
  • Naveed Ahmed Azam

    (Kyoto University)

  • Aleksandar Shurbevski

    (Kyoto University)

  • Hiroshi Nagamochi

    (Kyoto University)

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.

Suggested Citation

  • Naveed Ahmed Azam & Aleksandar Shurbevski & Hiroshi Nagamochi, 2022. "On the enumeration of minimal non-pairwise compatibility graphs," Journal of Combinatorial Optimization, Springer, vol. 44(4), pages 2871-2892, November.
    • Handle: RePEc:spr:jcomop:v:44:y:2022:i:4:d:10.1007_s10878-021-00799-x
    DOI: 10.1007/s10878-021-00799-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-021-00799-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-021-00799-x?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Gale, David, 1989. "The Theory of Linear Economic Models," University of Chicago Press Economics Books, University of Chicago Press, edition 1, number 9780226278841, September.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Romauch, Martin & Hartl, Richard F., 2017. "Capacity planning for cluster tools in the semiconductor industry," International Journal of Production Economics, Elsevier, vol. 194(C), pages 167-180.
    2. Anton Kolotilin & Roberto Corrao & Alexander Wolitzky, 2023. "Persuasion and Matching: Optimal Productive Transport," Discussion Papers 2023-12, School of Economics, The University of New South Wales.
    3. Dirk Bergemann & Stephen Morris, 2012. "Robust Implementation in General Mechanisms," World Scientific Book Chapters, in: Robust Mechanism Design The Role of Private Information and Higher Order Beliefs, chapter 5, pages 195-239, World Scientific Publishing Co. Pte. Ltd..
    4. Anton Kolotilin & Roberto Corrao & Alexander Wolitzky, 2022. "Persuasion with Non-Linear Preferences," Papers 2206.09164, arXiv.org, revised Aug 2022.
    5. Louis De Mesnard, 2009. "Is The Ghosh Model Interesting?," Journal of Regional Science, Wiley Blackwell, vol. 49(2), pages 361-372, May.
    6. Thomas L. Magnanti, 2021. "Optimization: From Its Inception," Management Science, INFORMS, vol. 67(9), pages 5349-5363, September.
    7. Alejandro Melo Ponce, 2018. "The Secret Behind The Tortoise and the Hare: Information Design in Contests," 2018 Papers pme809, Job Market Papers.
    8. Aoyagi, Masaki, 1996. "Evolution of Beliefs and the Nash Equilibrium of Normal Form Games," Journal of Economic Theory, Elsevier, vol. 70(2), pages 444-469, August.
    9. Alan Murray & Keith Skene & Kathryn Haynes, 2017. "The Circular Economy: An Interdisciplinary Exploration of the Concept and Application in a Global Context," Journal of Business Ethics, Springer, vol. 140(3), pages 369-380, February.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:44:y:2022:i:4:d:10.1007_s10878-021-00799-x. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.