Some Weighted Clique Minimization Problems and their Approximability Properties

Geoffrey Solano; Jhoirene Clemente; Richelle Ann Juayong; Ivy Ordanel

doi:10.2991/978-94-6463-388-7_3

<Previous Article In Volume

Next Article In Volume>

Some Weighted Clique Minimization Problems and their Approximability Properties

Authors

Geoffrey Solano¹^{, *}, Jhoirene Clemente², Richelle Ann Juayong², Ivy Ordanel²

¹Department Physical Sciences and Mathematics College of Arts and Sciences, University of the Philippines Manila, Manila, Philippines

²Department 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_3 How 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: 978-94-6463-388-7
ISSN: 2589-4900
DOI: 10.2991/978-94-6463-388-7_3 How to use a DOI?
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

ris enw bib

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  -

download .riscopy to clipboard