Minimum constellation covers: hardness, approximability and polynomial cases

Santiago Valdés Ravelo ()
Additional contact information
Santiago Valdés Ravelo: Federal University of Rio Grande do Sul

Journal of Combinatorial Optimization, 2021, vol. 41, issue 3, No 2, 603-624

Abstract: Abstract This paper considers two graph covering problems, the Minimum Constellation Cover (CC) and the Minimum k-Split Constellation Cover (k-SCC). The input of these problems consists on a graph $$G=\left( V,E\right) $$ G = V , E and a set $${\mathcal {C}}$$ C of stars of G, and the output is a minimum cardinality set of stars C, such that any two different stars of C are edge-disjoint and the union of the stars of C covers all edges of G. For CC, the set C must be compound by edges of G or stars of $${\mathcal {C}}$$ C while, for k-SCC, an integer k is given and the elements of C must be k-stars obtained by splitting stars of $${\mathcal {C}}$$ C . This work proves that unless $$P=NP$$ P = N P , CC does not admit polynomial time $$\left| {\mathcal {C}}\right| ^{{\mathcal {O}}\left( 1\right) }$$ C O 1 -approximation algorithms and k-SCC cannot be $$\left( \left( 1-\epsilon \right) \ln \left| E\right| \right) $$ 1 - ϵ ln E -approximated in polynomial time, for any $$\epsilon >0$$ ϵ > 0 . Additionally, approximation ratios are given for the worst feasible solutions of the problems and, for k-SCC, polynomial time approximation algorithms are proposed, achieving a $$\left( \ln \left| E\right| -\ln \ln \left| E\right| +\varTheta \left( 1\right) \right) $$ ln E - ln ln E + Θ 1 approximation ratio. Also, polynomial time algorithms are presented for special classes of graphs that include bounded degree trees and cacti.

Keywords: Exact graph cover; NP-hard; Inapproximability; Approximation algorithm; Polynomial time algorithm (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00698-1 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:jcomop:v:41:y:2021:i:3:d:10.1007_s10878-021-00698-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00698-1

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

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