Twin-width I: Tractable FO Model Checking

Autor: Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant

Publikováno v: FOCS 2020
FOCS 2020, Nov 2020, online, United States
HAL
FOCS

Inspired by a width invariant defined on permutations by Guillemot and Marx [SODA '14], we introduce the notion of twin-width on graphs and on matrices. Proper minor-closed classes, bounded rank-width graphs, map graphs, $K_t$-free unit $d$-dimension

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8f5b987eafeda11a20752c19481cf809
https://doi.org/10.1145/3486655

Twin-width and polynomial kernels

Autor: Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, Rémi Watrigant

Publikováno v: IPEC 2021
IPEC 2021, Sep 2021, Lisbon, Portugal
HAL

We study the existence of polynomial kernels for parameterized problems without a polynomial kernel on general graphs, when restricted to graphs of bounded twin-width. It was previously observed in [Bonnet et al., ICALP'21] that the problem k-Indepen

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::41b1afaf94ee8faee6f8a48b79532ef0
https://hal.science/hal-03430542/file/main.pdf

Parameterized resiliency problems

Autor: Jason Crampton, Martin Koutecký, Gregory Gutin, Rémi Watrigant

Publikováno v: Theoretical Computer Science. 795:478-491

We introduce an extension of decision problems called resiliency problems. In a resiliency problem, the goal is to decide whether an instance remains positive after any (appropriately defined) perturbation has been applied to it. To tackle these kind

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::912b8e24800b86bb651a8d6ec301606c
https://doi.org/10.1016/j.tcs.2019.08.002

An Algorithmic Weakening of the Erdős-Hajnal Conjecture

Autor: Stéphan Thomassé, Edouard Bonnet, Rémi Watrigant, Xuan Thang Tran

Publikováno v: ESA 2020
ESA 2020, Sep 2020, Pisa, Italy
HAL

We study the approximability of the Maximum Independent Set (MIS) problem in $H$-free graphs (that is, graphs which do not admit $H$ as an induced subgraph). As one motivation we investigate the following conjecture: for every fixed graph $H$, there

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::eea4957a133110dbff5b93c3914f8bf2
https://hal.archives-ouvertes.fr/hal-02935948

Overlaying a hypergraph with a graph with bounded maximum degree

Autor: Dorian Mazauric, Frédéric Havet, Viet-Ha Nguyen, Rémi Watrigant

Publikováno v: [Research Report] RR-9258, Inria Sophia Antipolis. 2019
Algorithms and Discrete Applied Mathematics ISBN: 9783030392185
CALDAM
Discrete Applied Mathematics
Discrete Applied Mathematics, In press, 319, pp.394-406. ⟨10.1007/978-3-030-39219-2_32⟩
CALDAM 2020-6th Annual International Conference on Algorithms and Discrete Applied Mathematics
CALDAM 2020-6th Annual International Conference on Algorithms and Discrete Applied Mathematics, Feb 2020, Hyderabad, India
ALGOTEL 2020 – 22èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications
ALGOTEL 2020 – 22èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Sep 2020, Lyon, France

International audience; Let G be a graph and H a ​​hypergraph with the same set of vertices and let F be a fixed graph. The graph GF overlays a hyperedge S of H if F is a covering subgraph of the subgraph of G induced by S. The graph GF-overlayin

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b729b78f1ad0d0cf297a8db80413c6bb
https://hal.inria.fr/hal-02025469v2/document