The Maximum Clique Problem for Permutation Hamming Graphs

János Barta () and Roberto Montemanni ()
Additional contact information
János Barta: IDSIA—USI/SUPSI
Roberto Montemanni: University of Modena and Reggio Emilia

Journal of Optimization Theory and Applications, 2022, vol. 194, issue 2, No 5, 492-507

Abstract: Abstract This paper explores a new approach to reduce the maximum clique problem associated with permutation Hamming graphs to smaller clique problems. The vertices of a permutation Hamming graph are permutations of n integers and the edges connect pairs of vertices at a Hamming distance greater than or equal to a threshold d. The maximum clique problem for permutation Hamming graphs is a challenging task due to the size, density and regularity of the graphs. However, symmetry properties, which are still partly unexplored, can help to reduce the problems’ size and hardness. A property of edge transitivity with respect to automorphisms is proven and leads to a classification for cycle-equivalent edges. This property enables to reduce the full-size clique problem to a set of significantly smaller (and easier to solve) clique problems. The number of reduced problems can be expressed by means of the partition function of integer numbers. Computational experiments confirm that additional knowledge on the automorphism group leads to a more targeted and efficient solving method for the maximum clique problem associated with permutation Hamming graphs.

Keywords: Graph theory; Combinatorics; Maximum clique problem; Permutations; Hamming graphs (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-022-02035-w 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:joptap:v:194:y:2022:i:2:d:10.1007_s10957-022-02035-w

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-022-02035-w

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

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