Clique Search in Graphs of Special Class and Job Shop Scheduling

Sándor Szabó and Bogdán Zaválnij
Additional contact information
Sándor Szabó: Institute of Mathematics and Informatics, University of Pécs, 7622 Pécs, Hungary
Bogdán Zaválnij: Rényi Institute of Mathematics, 1053 Budapest, Hungary

Mathematics, 2022, vol. 10, issue 5, 1-22

Abstract: In this paper, we single out the following particular case of the clique search problem. The vertices of the given graph are legally colored with k colors and we are looking for a clique with k nodes in the graph. In other words, we want to decide if a given k -partite graph contains a clique with k nodes. The maximum clique problem asks for finding a maximum clique in a given finite simple graph. The problem of deciding if the given graph contains a clique with k vertices is called the k -clique problem. The first problem is NP-hard and the second one is NP-complete. The special clique search problem, we propose, is still an NP-complete problem. We will show that the k -clique problem in the special case of k -partite graphs is more tractable than in the general case. In order to illustrate the possible practical utility of this restricted type clique search problem we will show that the job shop scheduling problem can be reduced to such a clique search problem in a suitable constructed graph. We carry out numerical experiments to assess the efficiency of the approach. It is a common practice that before one embarks on a large scale clique search typically one attempts to simplify and tidy up the given graph. This procedure is commonly referred as preconditioning or kernelization of the given graph. Of course, the preconditioning or kernelization is meant with respect to the given type of clique search problem. The other main topic of the paper is to describe a number of kernelization methods tailored particularly to the proposed special k -clique problem. Some of these techniques works in connection with the generic k -clique problem. In these situations, we will see that they are more efficient in the case of k -partite graphs. Some other preconditioning methods applicable only to k -partite graphs. We illustrate how expedient these preconditioning methods can be by solving non-trivial scheduling problems to optimality employing only kernelization techniques dispensing with exhaustive clique search algorithms altogether.

Keywords: job shop scheduling; kernelization; k -clique; struction (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/5/697/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/5/697/ (text/html)

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:gam:jmathe:v:10:y:2022:i:5:p:697-:d:756640

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().