• 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 - No thumbnail

Twin-width III: Max Independent Set and Coloring

Bonnet, Edouard; Geniet, Colin; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2021), Twin-width III: Max Independent Set and Coloring, in Bansal, Nikhil; Merelli, Emanuela; Worrell, James, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, p. 35:1--35:20. 10.4230/LIPIcs.ICALP.2021.35

View/Open
LIPIcs-ICALP-2021-35.pdf (927.6Kb)
Type
Communication / Conférence
Date
2021
Conference title
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Conference date
2021-07
Book title
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Book author
Bansal, Nikhil; Merelli, Emanuela; Worrell, James
Publisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
ISBN
978-3-95977-195-5
Pages
35:1--35:20
Publication identifier
10.4230/LIPIcs.ICALP.2021.35
Metadata
Show full item record
Author(s)
Bonnet, Edouard
Geniet, Colin
Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Thomassé, Stéphan
Watrigant, Rémi
Abstract (EN)
We recently introduced the graph invariant twin-width, and showed that first-order model checking can be solved in time f(d,k)n for n-vertex graphs given with a witness that the twin-width is at most d, called d-contraction sequence or d-sequence, and formulas of size k [Bonnet et al., FOCS '20]. The inevitable price to pay for such a general result is that f is a tower of exponentials of height roughly k. In this paper, we show that algorithms based on twin-width need not be impractical. We present 2O(k)n-time algorithms for k-Independent Set, r-Scattered Set, k-Clique, and k-Dominating Set when an O(1)-sequence is provided. We further show how to solve weighted k-Independent Set, Subgraph Isomorphism, and Induced Subgraph Isomorphism, in time 2O(klogk)n. These algorithms are based on a dynamic programming scheme following the sequence of contractions forward. We then show a second algorithmic use of the contraction sequence, by starting at its end and rewinding it. As an example of this reverse scheme, we present a polynomial-time algorithm that properly colors the vertices of a graph with relatively few colors, establishing that bounded twin-width classes are χ-bounded. This significantly extends the χ-boundedness of bounded rank-width classes, and does so with a very concise proof. The third algorithmic use of twin-width builds on the second one. Playing the contraction sequence backward, we show that bounded twin-width graphs can be edge-partitioned into a linear number of bicliques, such that both sides of the bicliques are on consecutive vertices, in a fixed vertex ordering. Given that biclique edge-partition, we show how to solve the unweighted Single-Source Shortest Paths and hence All-Pairs Shortest Paths in sublinear time O(nlogn) and time O(n2logn), respectively.
Subjects / Keywords
Twin-width; Max Independent Set; Min Dominating Set; Coloring; Parameterized Algorithms; Approximation Algorithms; Exact Algorithms

Related items

Showing items related by title and author.

  • Thumbnail
    Twin-width II: small classes 
    Bonnet, Edouard; Geniet, Colin; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2021) Communication / Conférence
  • Thumbnail
    Twin-width and polynomial kernels 
    Bonnet, Edouard; Kim, Eun Jung; Reinald, Amadeus; Thomassé, Stéphan; Watrigant, Rémi (2021) Communication / Conférence
  • Thumbnail
    Twin-width I: tractable FO model checking 
    Bonnet, Edouard; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2020) Communication / Conférence
  • Thumbnail
    Twin-width VI: the lens of contraction sequences 
    Bonnet, Edouard; Kim, Eun Jung; Reinald, Amadeus; Thomassé, Stéphan (2022) Communication / Conférence
  • Thumbnail
    Complexity of Grundy Coloring and Its Variants 
    Bonnet, Édouard; Foucaud, Florent; Kim, Eun Jung; Sikora, Florian (2015) Communication / Conférence
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