Proceedings of the Workshop on Computation: Theory and Practice (WCTP 2023)

<Previous Article In Volume
Next Article In Volume>

Some Weighted Clique Minimization Problems and their Approximability Properties

Authors
Geoffrey Solano1, *, Jhoirene Clemente2, Richelle Ann Juayong2, Ivy Ordanel2
1Department Physical Sciences and Mathematics College of Arts and Sciences, University of the Philippines Manila, Manila, Philippines
2Department of Computer Science College of Engineering, University of the Philippines Diliman, Quezon City, Philippines
*Corresponding author. Email: gasolano@up.edu.ph
Corresponding Author
Geoffrey Solano
Available Online 29 February 2024.
DOI
10.2991/978-94-6463-388-7_3How to use a DOI?
Keywords
cliques; graph theory; edge-weighted clique; approximation
Abstract

Two minimum clique problems are considered in this study along with some of their important subclasses. The first is the Minimum Edge-Weighted Clique Problem (MIN-EWCP), which is the problem of finding the clique of order m with the least total weight in a complete edge-weighted graph G. The other one is the Minimum Weighted t-partite Clique Problem (MWtCP), which is the problem of finding the t-clique with the least total weight in a complete edgeweighted t-partite graph G. The results show that the (1, 2)-metric MWtCP, the σ-metric MWtCP, and the metric MWtCP are NP-hard. The general MWtCP is inapproximable. The ultrametric variants of MWtCP and MIN-EWCP, on the other hand, are approximable with a performance guarantee of 3/2. These problems were explored mainly because of their potential as a computational models of the biological problem of finding approximate gene clusters as is shown in some related studies, particularly the Approximate Gene Cluster Discovery Problem (AGCDP). Among the results shown in this paper is that AGCDP, when w+  = w−, is in APX.

Copyright
© 2024 The Author(s)
Open Access
Open Access This chapter is licensed under the terms of the Creative Commons Attribution-NonCommercial 4.0 International License (http://creativecommons.org/licenses/by-nc/4.0/), which permits any noncommercial use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

Download article (PDF)

<Previous Article In Volume
Next Article In Volume>
Volume Title
Proceedings of the Workshop on Computation: Theory and Practice (WCTP 2023)
Series
Atlantis Highlights in Computer Sciences
Publication Date
29 February 2024
ISBN
10.2991/978-94-6463-388-7_3
ISSN
2589-4900
DOI
10.2991/978-94-6463-388-7_3How to use a DOI?
Copyright
© 2024 The Author(s)
Open Access
Open Access This chapter is licensed under the terms of the Creative Commons Attribution-NonCommercial 4.0 International License (http://creativecommons.org/licenses/by-nc/4.0/), which permits any noncommercial use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

Cite this article

risenwbib
TY  - CONF
AU  - Geoffrey Solano
AU  - Jhoirene Clemente
AU  - Richelle Ann Juayong
AU  - Ivy Ordanel
PY  - 2024
DA  - 2024/02/29
TI  - Some Weighted Clique Minimization Problems and their Approximability Properties
BT  - Proceedings of the Workshop on Computation: Theory and Practice (WCTP 2023)
PB  - Atlantis Press
SP  - 24
EP  - 37
SN  - 2589-4900
UR  - https://doi.org/10.2991/978-94-6463-388-7_3
DO  - 10.2991/978-94-6463-388-7_3
ID  - Solano2024
ER  -