• 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

K3 Edge Cover Problem in a Wide Sense

Chiba, Kyohei; Belmonte, Rémy; Ito, Hiro; Lampis, Michael; Nagao, Atsuki; Otachi, Yota (2020), K3 Edge Cover Problem in a Wide Sense, Journal of Information Processing, 28, p. 849–858. 10.2197/ipsjjip.28.849

View/Open
K3-Edge_Cover.pdf (1.378Mb)
Type
Article accepté pour publication ou publié
Date
2020
Journal name
Journal of Information Processing
Volume
28
Publisher
Information Processing Society of Japan
Pages
849–858
Publication identifier
10.2197/ipsjjip.28.849
Metadata
Show full item record
Author(s)
Chiba, Kyohei
Belmonte, Rémy
Ito, Hiro
Lampis, Michael
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Nagao, Atsuki
Otachi, Yota
Abstract (EN)
In this study, we consider a problem, for a given graph G = (V, E), of finding the minimum number of 3-cliques (K3s) that cover all edges of G. Multiple covering or covering one edge by more than one 3-clique is allowed. Moreover, in this problem, we allow "spilling-out," i.e., a set of three vertices {x, y, z} can be covered by a 3-clique even if the induced subgraph by them is not a clique. We call this problem K3 edge cover problem in a wide sense. This problem is a kind of extension of the schoolgirl problem and finite projective planes, and it has applications on experimental designs. Allowing spilling-out is useful for some applications: E.g., when we want to compare n items through some tries of experiments, in which at most three items can be compared simultaneously, and pairs of items that must be compared are given by a graph, finding the minimum number of tries is formalized as this problem. In the known literature, there are many results that considered problems for covering vertices or edges by the minimum number of cliques. However, there is no theoretical result that considers spilling-out. We obtain the following results: (1) The problem is NP-hard even if graphs are restricted to planar, cubic, and C4, C5-free in a sense of subgraphs (i.e., not restricted to induced ones). (2) For the problem with a parameter k, which is the number of 3-cliques in G, there is an O(mn + 2km)-time algorithm. (3) If a tree-decomposition of tree-width t is given, there is an O(22(t+1)(t+2)t2n)-time algorithm.
Subjects / Keywords
graphs; clique; edge cover; spilling-out; NP-complete; FPT; tree-width

Related items

Showing items related by title and author.

  • Thumbnail
    Independent Set Reconfiguration Parameterized by Modular-Width 
    Belmonte, Rémy; Hanaka, Tesshu; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2019) Communication / Conférence
  • Thumbnail
    Token Sliding on Split Graphs 
    Belmonte, Rémy; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Otachi, Yota; Sikora, Florian (2019) Communication / Conférence
  • Thumbnail
    Parameterized Complexity of Safe Set 
    Belmonte, Rémy; Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2019) Communication / Conférence
  • Thumbnail
    How Bad is the Freedom to Flood-It? 
    Belmonte, Rémy; Khosravian Ghadikolaei, Mehdi; Kiyomi, Masashi; Lampis, Michael; Otachi, Yota (2019) Article accepté pour publication ou publié
  • Thumbnail
    Token Sliding on Split Graphs 
    Sikora, Florian; Belmonte, Rémy; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Otachi, Yota (2020) 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