Clique Search in Graphs of Special Class and Job Shop Scheduling
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 <i>k</i> colors and we are looking for a clique with <i>k</i> nodes in the graph. In other words, we want to decide if a given <...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-02-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/10/5/697 |
| _version_ | 1797474505207054336 |
|---|---|
| author | Sándor Szabó Bogdán Zaválnij |
| author_facet | Sándor Szabó Bogdán Zaválnij |
| author_sort | Sándor Szabó |
| collection | DOAJ |
| description | 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 <i>k</i> colors and we are looking for a clique with <i>k</i> nodes in the graph. In other words, we want to decide if a given <i>k</i>-partite graph contains a clique with <i>k</i> 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 <i>k</i> vertices is called the <i>k</i>-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 <i>k</i>-clique problem in the special case of <i>k</i>-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 <i>k</i>-clique problem. Some of these techniques works in connection with the generic <i>k</i>-clique problem. In these situations, we will see that they are more efficient in the case of <i>k</i>-partite graphs. Some other preconditioning methods applicable only to <i>k</i>-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. |
| first_indexed | 2024-03-09T20:31:03Z |
| format | Article |
| id | doaj.art-5fdf1f428a2341759dc63accbc7ec3f3 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-09T20:31:03Z |
| publishDate | 2022-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-5fdf1f428a2341759dc63accbc7ec3f32023-11-23T23:22:16ZengMDPI AGMathematics2227-73902022-02-0110569710.3390/math10050697Clique Search in Graphs of Special Class and Job Shop SchedulingSándor Szabó0Bogdán Zaválnij1Institute of Mathematics and Informatics, University of Pécs, 7622 Pécs, HungaryRényi Institute of Mathematics, 1053 Budapest, HungaryIn this paper, we single out the following particular case of the clique search problem. The vertices of the given graph are legally colored with <i>k</i> colors and we are looking for a clique with <i>k</i> nodes in the graph. In other words, we want to decide if a given <i>k</i>-partite graph contains a clique with <i>k</i> 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 <i>k</i> vertices is called the <i>k</i>-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 <i>k</i>-clique problem in the special case of <i>k</i>-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 <i>k</i>-clique problem. Some of these techniques works in connection with the generic <i>k</i>-clique problem. In these situations, we will see that they are more efficient in the case of <i>k</i>-partite graphs. Some other preconditioning methods applicable only to <i>k</i>-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.https://www.mdpi.com/2227-7390/10/5/697job shop schedulingkernelization<i>k</i>-cliquestruction |
| spellingShingle | Sándor Szabó Bogdán Zaválnij Clique Search in Graphs of Special Class and Job Shop Scheduling Mathematics job shop scheduling kernelization <i>k</i>-clique struction |
| title | Clique Search in Graphs of Special Class and Job Shop Scheduling |
| title_full | Clique Search in Graphs of Special Class and Job Shop Scheduling |
| title_fullStr | Clique Search in Graphs of Special Class and Job Shop Scheduling |
| title_full_unstemmed | Clique Search in Graphs of Special Class and Job Shop Scheduling |
| title_short | Clique Search in Graphs of Special Class and Job Shop Scheduling |
| title_sort | clique search in graphs of special class and job shop scheduling |
| topic | job shop scheduling kernelization <i>k</i>-clique struction |
| url | https://www.mdpi.com/2227-7390/10/5/697 |
| work_keys_str_mv | AT sandorszabo cliquesearchingraphsofspecialclassandjobshopscheduling AT bogdanzavalnij cliquesearchingraphsofspecialclassandjobshopscheduling |