• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

Complexity Results for the Empire Problem in Collection of Stars

Couëtoux, Basile; Monnot, Jérôme; Toubaline, Sónia (2012), Complexity Results for the Empire Problem in Collection of Stars, in Lin, Guohui, Combinatorial Optimization and Applications 6th International Conference, COCOA 2012, Banff, AB, Canada, August 5-9, 2012, Proceedings, Springer : Berlin Heidelberg, p. 73-82

Type
Communication / Conférence
Date
2012
Conference title
6th International Conference on Combinatorial Optimization and Applications, COCOA 2012
Conference date
2012-08
Conference city
Banff
Conference country
Canada
Book title
Combinatorial Optimization and Applications 6th International Conference, COCOA 2012, Banff, AB, Canada, August 5-9, 2012, Proceedings
Book author
Lin, Guohui
Publisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-642-31769-9
Pages
73-82
Metadata
Show full item record
Author(s)
Couëtoux, Basile

Monnot, Jérôme cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Toubaline, Sónia
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
In this paper, we study the Empire Problem, a generalization of the coloring problem to maps on two-dimensional compact surface whose genus is positive. Given a planar graph with a certain partition of the vertices into blocks of size r, for a given integer r, the problem consists of deciding if s colors are sufficient to color the vertices of the graph such that vertices of the same block have the same color and vertices of two adjacent blocks have different colors. In this paper, we prove that given a 5-regular graph, deciding if there exists a 4-coloration is NP-complete. Also, we propose conditional NP-completeness results for the Empire Problem when the graph is a collection of stars. A star is a graph isomorphic to K 1,q for some q ≥ 1. More exactly, we prove that for r ≥ 2, if the (2r − 1)-coloring problem in 2r-regular connected graphs is NP-complete, then the Empire Problem for blocks of size r + 1 and s = 2r − 1 is NP-complete for forests of K 1, r . Moreover, we prove that this result holds for r = 2. Also for r ≥ 3, if the r-coloring problem in (r + 1)-regular graphs is NP-complete, then the Empire Problem for blocks of size r + 1 and s = r is NP-complete for forests of K 1, 1 = K 2, i.e., forest of edges. Additionally, we prove that this result is valid for r = 2 and r = 3. Finally, we prove that these results are the best possible, that is for smallest value of s or r, the Empire Problem in these classes of graphs becomes polynomial.
Subjects / Keywords
Coloring in regular graphs; Empire Problem; Forests of stars; NP-completeness

Related items

Showing items related by title and author.

  • Thumbnail
    Labeled Traveling Salesman Problems: Complexity and approximation 
    Couëtoux, Basile; Gourvès, Laurent; Monnot, Jérôme; Telelis, Orestis (2010) Article accepté pour publication ou publié
  • Thumbnail
    Complexity and inapproximability results for the Power Edge Set problem 
    Toubaline, Sónia; D’Ambrosio, Claudia; Liberti, Leo; Poirion, Pierre-Louis; Schieber, Baruch; Shachnai, Hadas (2018) Article accepté pour publication ou publié
  • Thumbnail
    Complexity and Approximation Results for the Connected Vertex Cover Problem in Graphs and Hypergraphs 
    Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno (2010) Article accepté pour publication ou publié
  • Thumbnail
    Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs 
    Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2007) Document de travail / Working paper
  • Thumbnail
    Complexity and approximability of extended Spanning Star Forest problems in general and complete graphs 
    Khoshkhah, Kaveh; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme; Theis, Dirk Oliver (2019) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo