110 results on '"Bonnet, Édouard"'
Search Results
2. Maximum Matchings in Geometric Intersection Graphs
- Author
-
Bonnet, Édouard, Cabello, Sergio, and Mulzer, Wolfgang
- Published
- 2023
- Full Text
- View/download PDF
3. Twin-Width IV: Ordered Graphs and Matrices.
- Author
-
Bonnet, Édouard, Giocanti, Ugo, de Mendez, Patrice Ossona, Simon, Pierre, Thomassé, Stéphan, and Toruńczyk, Szymon
- Subjects
FINITE model theory ,GRAPH theory ,APPROXIMATION algorithms ,FIRST-order logic ,MODEL theory - Abstract
We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP classes studied in model theory, as classes that do not transduce the class of all graphs studied in finite model theory, and as classes for which model checking first-order logic is fixed-parameter tractable studied in algorithmic graph theory. This has several consequences. First, it allows us to show that every hereditary class of ordered graphs either has at most exponential growth, or has at least factorial growth. This settles a question first asked by Balogh et al. [5] on the growth of hereditary classes of ordered graphs, generalizing the Stanley-Wilf conjecture/Marcus-Tardos theorem. Second, it gives a fixed-parameter approximation algorithm for twin-width on ordered graphs. Third, it yields a full classification of fixed-parameter tractable first-order model checking on hereditary classes of ordered binary structures. Fourth, it provides a model-theoretic characterization of classes with bounded twin-width. Finally, it settles the small conjecture [8] in the case of ordered graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
4. Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
- Author
-
Bonamy, Marthe, Bonnet, Édouard, Déprés, Hugues, Esperet, Louis, Geniet, Colin, Hilaire, Claire, Thomassé, Stéphan, and Wesolek, Alexandra
- Published
- 2024
- Full Text
- View/download PDF
5. Neighbourhood complexity of graphs of bounded twin-width
- Author
-
Bonnet, Édouard, Foucaud, Florent, Lehtilä, Tuomo, and Parreau, Aline
- Published
- 2024
- Full Text
- View/download PDF
6. Grundy Coloring and Friends, Half-Graphs, Bicliques
- Author
-
Aboulker, Pierre, Bonnet, Édouard, Kim, Eun Jung, and Sikora, Florian
- Published
- 2023
- Full Text
- View/download PDF
7. Twin-width and Polynomial Kernels
- Author
-
Bonnet, Édouard, Kim, Eun Jung, Reinald, Amadeus, Thomassé, Stéphan, and Watrigant, Rémi
- Published
- 2022
- Full Text
- View/download PDF
8. Twin-width can be exponential in treewidth
- Author
-
Bonnet, Édouard and Déprés, Hugues
- Published
- 2023
- Full Text
- View/download PDF
9. The complexity of mixed-connectivity
- Author
-
Bonnet, Édouard and Cabello, Sergio
- Published
- 2021
- Full Text
- View/download PDF
10. Metric Dimension Parameterized By Treewidth
- Author
-
Bonnet, Édouard and Purohit, Nidhi
- Published
- 2021
- Full Text
- View/download PDF
11. The Inverse Voronoi Problem in Graphs II: Trees
- Author
-
Bonnet, Édouard, Cabello, Sergio, Mohar, Bojan, and Pérez-Rosés, Hebert
- Published
- 2021
- Full Text
- View/download PDF
12. TWIN-WIDTH AND PERMUTATIONS.
- Author
-
BONNET, ÉDOUARD, NEŠETŘIL, JAROSLAV, OSSONA DE MENDEZ, PATRICE, SIEBERTZ, SEBASTIAN, and THOMASSÉ, STÉPHAN
- Subjects
GRAPH theory ,GENETIC transduction ,DIRECTED graphs ,PERMUTATIONS - Abstract
Inspired by a width invariant on permutations defined by Guillemot and Marx, Bonnet, Kim, Thomassé, and Watrigant introduced the twin-width of graphs, which is a parameter describing its structural complexity. This invariant has been further extended to binary structures, in several (basically equivalent) ways. We prove that a class of binary relational structures (that is: edge-colored partially directed graphs) has bounded twin-width if and only if it is a first-order transduction of a proper permutation class. As a by-product, we show that every class with bounded twin-width contains at most 2
O(n) pairwise non-isomorphic n-vertex graphs. [ABSTRACT FROM AUTHOR]- Published
- 2024
- Full Text
- View/download PDF
13. The Inverse Voronoi Problem in Graphs I: Hardness
- Author
-
Bonnet, Édouard, Cabello, Sergio, Mohar, Bojan, and Pérez-Rosés, Hebert
- Published
- 2020
- Full Text
- View/download PDF
14. Parameterized Complexity of Independent Set in H-Free Graphs
- Author
-
Bonnet, Édouard, Bousquet, Nicolas, Charbit, Pierre, Thomassé, Stéphan, and Watrigant, Rémi
- Published
- 2020
- Full Text
- View/download PDF
15. Complexity of Grundy coloring and its variants
- Author
-
Bonnet, Édouard, Foucaud, Florent, Kim, Eun Jung, and Sikora, Florian
- Published
- 2018
- Full Text
- View/download PDF
16. Purely combinatorial approximation algorithms for maximum [formula omitted]-vertex cover in bipartite graphs
- Author
-
Bonnet, Édouard, Escoffier, Bruno, Paschos, Vangelis Th., and Stamoulis, Georgios
- Published
- 2018
- Full Text
- View/download PDF
17. Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality is the Key to Single-Exponential Parameterized Algorithms
- Author
-
Bonnet, Édouard, Brettell, Nick, Kwon, O-joung, and Marx, Dániel
- Published
- 2019
- Full Text
- View/download PDF
18. Optimality Program in Segment and String Graphs
- Author
-
Bonnet, Édouard and Rzążewski, Paweł
- Published
- 2019
- Full Text
- View/download PDF
19. The Graph Motif problem parameterized by the structure of the input graph
- Author
-
Bonnet, Édouard and Sikora, Florian
- Published
- 2017
- Full Text
- View/download PDF
20. Twin-width I: Tractable FO Model Checking.
- Author
-
BONNET, ÉDOUARD, EUN JUNG KIM, THOMASSÉ, STÉPHAN, and WATRIGANT, RÉMI
- Subjects
POLYNOMIAL time algorithms ,PARTIALLY ordered sets ,UNIT ball (Mathematics) ,CHARTS, diagrams, etc. ,GENETIC transduction - Abstract
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, Kt -free unit d-dimensional ball graphs, posets with antichains of bounded size, and proper subclasses of dimension-2 posets all have bounded twin-width. On all these classes (except map graphs without geometric embedding) we show how to compute in polynomial time a sequence of d-contractions, witness that the twin-width is at most d. We show that FO model checking, that is deciding if a given first-order formula ϕ evaluates to true for a given binary structure G on a domain D, is FPT in |ϕ| on classes of bounded twin-width, provided the witness is given. More precisely, being given a d-contraction sequence for G, our algorithm runs in time f (d, |ϕ|) · |D| where f is a computable but non-elementary function. We also prove that bounded twin-width is preserved under FO interpretations and transductions (allowing operations such as squaring or complementing a graph). This unifies and significantly extends the knowledge on fixed-parameter tractability of FO model checking on non-monotone classes, such as the FPT algorithm on bounded-width posets by Gajarský et al. [FOCS'15]. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
21. Stretch-width
- Author
-
Bonnet, Édouard and Duron, Julien
- Subjects
Computer Science - Data Structures and Algorithms ,Mathematics - Combinatorics ,05C85 ,F.2.2 ,Computer Science - Discrete Mathematics - Abstract
We introduce a new parameter, called stretch-width, that we show sits strictly between clique-width and twin-width. Unlike the reduced parameters [BKW '22], planar graphs and polynomial subdivisions do not have bounded stretch-width. This leaves open the possibility of efficient algorithms for a broad fragment of problems within Monadic Second-Order (MSO) logic on graphs of bounded stretch-width. In this direction, we prove that graphs of bounded maximum degree and bounded stretch-width have at most logarithmic treewidth. As a consequence, in classes of bounded stretch-width, Maximum Independent Set can be solved in subexponential time $2^{O(n^{4/5} \log n)}$ on $n$-vertex graphs, and, if further the maximum degree is bounded, Existential Counting Modal Logic [Pilipczuk '11] can be model-checked in polynomial time. We also give a polynomial-time $O(\text{OPT}^2)$-approximation for the stretch-width of symmetric $0,1$-matrices or ordered graphs. Somewhat unexpectedly, we prove that exponential subdivisions of bounded-degree graphs have bounded stretch-width. This allows to complement the logarithmic upper bound of treewidth with a matching lower bound. We leave as open the existence of an efficient approximation algorithm for the stretch-width of unordered graphs, if the exponential subdivisions of all graphs have bounded stretch-width, and if graphs of bounded stretch-width have logarithmic clique-width (or rank-width)., Comment: 28 pages, 12 figures
- Published
- 2023
22. Complexity of Token Swapping and Its Variants
- Author
-
Bonnet, Édouard, Miltzow, Tillmann, and Rzążewski, Paweł
- Published
- 2018
- Full Text
- View/download PDF
23. A tamed family of triangle-free graphs with unbounded chromatic number
- Author
-
Bonnet, Édouard, Bourneuf, Romain, Duron, Julien, Geniet, Colin, Thomassé, Stéphan, and Trotignon, Nicolas
- Subjects
05C15 ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) - Abstract
We construct a hereditary class of triangle-free graphs with unbounded chromatic number, in which every non-trivial graph either contains a pair of non-adjacent twins or has an edgeless vertex cutset of size at most two. This answers in the negative a question of Chudnovsky, Penev, Scott, and Trotignon. The class is the hereditary closure of a family of (triangle-free) twincut graphs $G_1, G_2, \ldots$ such that $G_k$ has chromatic number $k$. We also show that every twincut graph is edge-critical.
- Published
- 2023
24. Maximum Independent Set when excluding an induced minor: $K_1 + tK_2$ and $tC_3 \uplus C_4$
- Author
-
Bonnet, Édouard, Duron, Julien, Geniet, Colin, Thomassé, Stéphan, and Wesolek, Alexandra
- Subjects
FOS: Computer and information sciences ,Discrete Mathematics (cs.DM) ,Computer Science - Data Structures and Algorithms ,FOS: Mathematics ,Mathematics - Combinatorics ,Data Structures and Algorithms (cs.DS) ,05C85 ,Combinatorics (math.CO) ,F.2.2 ,Computer Science - Discrete Mathematics - Abstract
Dallard, Milani\v{c}, and \v{S}torgel [arXiv '22] ask if for every class excluding a fixed planar graph $H$ as an induced minor, Maximum Independent Set can be solved in polynomial time, and show that this is indeed the case when $H$ is any planar complete bipartite graph, or the 5-vertex clique minus one edge, or minus two disjoint edges. A positive answer would constitute a far-reaching generalization of the state-of-the-art, when we currently do not know if a polynomial-time algorithm exists when $H$ is the 7-vertex path. Relaxing tractability to the existence of a quasipolynomial-time algorithm, we know substantially more. Indeed, quasipolynomial-time algorithms were recently obtained for the $t$-vertex cycle, $C_t$ [Gartland et al., STOC '21] and the disjoint union of $t$ triangles, $tC_3$ [Bonamy et al., SODA '23]. We give, for every integer $t$, a polynomial-time algorithm running in $n^{O(t^5)}$ when $H$ is the friendship graph $K_1 + tK_2$ ($t$ disjoint edges plus a vertex fully adjacent to them), and a quasipolynomial-time algorithm running in $n^{O(t^2 \log n)+t^{O(1)}}$ when $H$ is $tC_3 \uplus C_4$ (the disjoint union of $t$ triangles and a 4-vertex cycle). The former extends a classical result on graphs excluding $tK_2$ as an induced subgraph [Alekseev, DAM '07], while the latter extends Bonamy et al.'s result., Comment: 15 pages, 2 figures
- Published
- 2023
25. Parameterized Intractability of Even Set and Shortest Vector Problem.
- Author
-
BHATTACHARYYA, ARNAB, BONNET, ÉDOUARD, EGRI, LÁSZLÓ, GHOSHAL, SUPROVAT, C. S., KARTHIK, BINGKAI LIN, MANURANGSI, PASIN, and MARX, DÁNIEL
- Subjects
OPEN-ended questions ,INTEGERS ,MAXIMA & minima - Abstract
The k-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over F
2 , which can be stated as follows: given a generator matrix A and an integer k, determine whether the code generated by A has distance at most k, or, in other words, whether there is a nonzero vector x such that Ax has at most k nonzero coordinates. The question of whether k-Even Set is fixed parameter tractable (FPT) parameterized by the distance k has been repeatedly raised in the literature; in fact, it is one of the few remaining open questions from the seminal book of Downey and Fellows [1999]. In this work, we show that k-Even Set is W[1]-hard under randomized reductions. We also consider the parameterized k-Shortest Vector Problem (SVP), in which we are given a latticewhose basis vectors are integral and an integer k, and the goal is to determine whether the norm of the shortest vector (in the ℓp norm for some fixed p) is at most k. Similar to k-Even Set, understanding the complexity of this problem is also a long-standing open question in the field of Parameterized Complexity. We show that, for any p > 1, k-SVP is W[1]-hard to approximate (under randomized reductions) to some constant factor. [ABSTRACT FROM AUTHOR]- Published
- 2021
- Full Text
- View/download PDF
26. Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width
- Author
-
Bergé, Pierre, Bonnet, Édouard, Déprés, Hugues, and Watrigant, Rémi
- Subjects
FOS: Computer and information sciences ,Discrete Mathematics (cs.DM) ,Theory of computation → Design and analysis of algorithms ,Computational Complexity (cs.CC) ,68W25 ,Approximation algorithms ,bounded twin-width ,Computer Science - Computational Complexity ,Theory of computation → Graph algorithms analysis ,Computer Science - Data Structures and Algorithms ,FOS: Mathematics ,Mathematics - Combinatorics ,Data Structures and Algorithms (cs.DS) ,Combinatorics (math.CO) ,F.2.2 ,Computer Science - Discrete Mathematics - Abstract
For any $\varepsilon > 0$, we give a polynomial-time $n^\varepsilon$-approximation algorithm for Max Independent Set in graphs of bounded twin-width given with an $O(1)$-sequence. This result is derived from the following time-approximation trade-off: We establish an $O(1)^{2^q-1}$-approximation algorithm running in time $\exp(O_q(n^{2^{-q}}))$, for every integer $q \geqslant 0$. Guided by the same framework, we obtain similar approximation algorithms for Min Coloring and Max Induced Matching. In general graphs, all these problems are known to be highly inapproximable: for any $\varepsilon > 0$, a polynomial-time $n^{1-\varepsilon}$-approximation for any of them would imply that P$=$NP [Hastad, FOCS '96; Zuckerman, ToC '07; Chalermsook et al., SODA '13]. We generalize the algorithms for Max Independent Set and Max Induced Matching to the independent (induced) packing of any fixed connected graph $H$. In contrast, we show that such approximation guarantees on graphs of bounded twin-width given with an $O(1)$-sequence are very unlikely for Min Independent Dominating Set, and somewhat unlikely for Longest Path and Longest Induced Path. Regarding the existence of better approximation algorithms, there is a (very) light evidence that the obtained approximation factor of $n^\varepsilon$ for Max Independent Set may be best possible. This is the first in-depth study of the approximability of problems in graphs of bounded twin-width. Prior to this paper, essentially the only such result was a~polynomial-time $O(1)$-approximation algorithm for Min Dominating Set [Bonnet et al., ICALP '21]., 32 pages, 3 figures, 1 table
- Published
- 2023
- Full Text
- View/download PDF
27. EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs.
- Author
-
BONAMY, MARTHE, BONNET, ÉDOUARD, BOUSQUET, NICOLAS, CHARBIT, PIERRE, GIANNOPOULOS, PANOS, EUN JUNG KIM, RZĄŻEWSKI, PAWEŁ, SIKORA, FLORIAN, and THOMASSÉ, STÉPHAN
- Subjects
UNIT ball (Mathematics) ,COMPUTATIONAL mathematics ,ALGORITHMS ,DIAMETER ,INTERSECTION graph theory ,ELLIPSES (Geometry) ,OPEN-ended questions ,APPROXIMATION algorithms - Abstract
A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for Maximum Cliqe on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematics '90]. Since then, it has been an intriguing open question whether or not tractability can be extended to general disk graphs. We show that the disjoint union of two odd cycles is never the complement of a disk graph nor of a unit (3-dimensional) ball graph. From that fact and existing results, we derive a simple QPTAS and a subexponential algorithm running in time 2õ (n²/
3 ) for Maximum Cliqe on disk and unit ball graphs. We then obtain a randomized EPTAS for computing the independence number on graphs having no disjoint union of two odd cycles as an induced subgraph, bounded VC-dimension, and linear independence number. This, in combination with our structural results, yields a randomized EPTAS for Max Cliqe on disk and unit ball graphs. Max Cliqe on unit ball graphs is equivalent to finding, given a collection of points in R³, a maximum subset of pointswith diameter at most some fixed value. In stark contrast, Maximum Cliqe on ball graphs and unit 4-dimensional ball graphs, as well as intersection graphs of filled ellipses (even close to unit disks) or filled triangles is unlikely to have such algorithms. Indeed, we showthat, for all those problems, there is a constant ratio of approximation that cannot be attained even in time 2n 1-ε , unless the Exponential Time Hypothesis fails. [ABSTRACT FROM AUTHOR]- Published
- 2021
- Full Text
- View/download PDF
28. Twin-width V: linear minors, modular counting, and matrix multiplication
- Author
-
Bonnet, Édouard, Giocanti, Ugo, Ossona de Mendez, Patrice, and Thomassé, Stéphan
- Subjects
FOS: Computer and information sciences ,Computer Science - Logic in Computer Science ,computational complexity ,Discrete Mathematics (cs.DM) ,matrix multiplication ,algorithms ,68W01 ,Theory of computation → Logic ,Logic in Computer Science (cs.LO) ,linear algebra ,matrices ,model theory ,parity and linear minors ,Computer Science - Data Structures and Algorithms ,FOS: Mathematics ,Theory of computation → Parameterized complexity and exact algorithms ,Mathematics - Combinatorics ,Data Structures and Algorithms (cs.DS) ,Combinatorics (math.CO) ,F.2.2 ,Twin-width ,Computer Science - Discrete Mathematics - Abstract
We continue developing the theory around the twin-width of totally ordered binary structures (or equivalently, matrices over a finite alphabet), initiated in the previous paper of the series. We first introduce the notion of parity and linear minors of a matrix, which consists of iteratively replacing consecutive rows or consecutive columns with a linear combination of them. We show that a matrix class (i.e., a set of matrices closed under taking submatrices) has bounded twin-width if and only if its linear-minor closure does not contain all matrices. We observe that the fixed-parameter tractable (FPT) algorithm for first-order model checking on structures given with an O(1)-sequence (certificate of bounded twin-width) and the fact that first-order transductions of bounded twin-width classes have bounded twin-width, both established in Twin-width I, extend to first-order logic with modular counting quantifiers. We make explicit a win-win argument obtained as a by-product of Twin-width IV, and somewhat similar to bidimensionality, that we call rank-bidimensionality. This generalizes the seminal work of Guillemot and Marx [SODA '14], which builds on the Marcus-Tardos theorem [JCTA '04]. It works on general matrices (not only on classes of bounded twin-width) and, for example, yields FPT algorithms deciding if a small matrix is a parity or a linear minor of another matrix given in input, or exactly computing the grid or mixed number of a given matrix (i.e., the maximum integer k such that the row set and the column set of the matrix can be partitioned into k intervals, with each of the k² defined cells containing a non-zero entry, or two distinct rows and two distinct columns, respectively). Armed with the above-mentioned extension to modular counting, we show that the twin-width of the product of two conformal matrices A, B (i.e., whose dimensions are such that AB is defined) over a finite field is bounded by a function of the twin-width of A, of B, and of the size of the field. Furthermore, if A and B are n × n matrices of twin-width d over F_q, we show that AB can be computed in time O_{d,q}(n² log n). We finally present an ad hoc algorithm to efficiently multiply two matrices of bounded twin-width, with a single-exponential dependence in the twin-width bound. More precisely, pipelined to observations and results of Pilipczuk et al. [STACS '22], we obtain the following. If the inputs are given in a compact tree-like form (witnessing twin-width at most d), called twin-decomposition of width d, then two n × n matrices A, B over F₂ can be multiplied in time 4^{d+o(d)}n, in the sense that a twin-decomposition of their product AB, with width 2^{d+o(d)}, is output within that time, and each entry of AB can be queried in time O_d(log log n). Furthermore, for every ε > 0, the query time can be brought to constant time O(1/ε) if the running time is increased to near-linear 4^{d+o(d)}n^{1+ε}. Notably, the running time is sublinear (essentially square root) in the number of (non-zero) entries., LIPIcs, Vol. 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), pages 15:1-15:16
- Published
- 2022
29. Twin-width VIII: delineation and win-wins
- Author
-
Bonnet, Édouard, Chakraborty, Dibyayan, Kim, Eun Jung, Köhler, Noleen, Lopes, Raul, Thomassé, Stéphan, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
FOS: Computer and information sciences ,Computer Science - Logic in Computer Science ,05C85, 05C75 ,Discrete Mathematics (cs.DM) ,monadic dependence and stability ,intersection graphs ,visibility graphs ,Logic in Computer Science (cs.LO) ,Theory of computation → Fixed parameter tractability ,Theory of computation → Graph algorithms analysis ,Computer Science - Data Structures and Algorithms ,FOS: Mathematics ,Mathematics - Combinatorics ,first-order model checking ,Data Structures and Algorithms (cs.DS) ,[INFO]Computer Science [cs] ,Combinatorics (math.CO) ,F.2.2 ,Computer Science - Discrete Mathematics ,Twin-width - Abstract
We introduce the notion of delineation. A graph class C is said delineated by twin-width (or simply, delineated) if for every hereditary closure D of a subclass of C, it holds that D has bounded twin-width if and only if D is monadically dependent. An effective strengthening of delineation for a class C implies that tractable FO model checking on C is perfectly understood: On hereditary closures of subclasses D of C, FO model checking on D is fixed-parameter tractable (FPT) exactly when D has bounded twin-width. Ordered graphs [BGOdMSTT, STOC '22] and permutation graphs [BKTW, JACM '22] are effectively delineated, while subcubic graphs are not. On the one hand, we prove that interval graphs, and even, rooted directed path graphs are delineated. On the other hand, we observe or show that segment graphs, directed path graphs (with arbitrarily many roots), and visibility graphs of simple polygons are not delineated. In an effort to draw the delineation frontier between interval graphs (that are delineated) and axis-parallel two-lengthed segment graphs (that are not), we investigate the twin-width of restricted segment intersection classes. It was known that (triangle-free) pure axis-parallel unit segment graphs have unbounded twin-width [BGKTW, SODA '21]. We show that K_{t,t}-free segment graphs, and axis-parallel H_t-free unit segment graphs have bounded twin-width, where H_t is the half-graph or ladder of height t. In contrast, axis-parallel H₄-free two-lengthed segment graphs have unbounded twin-width. We leave as an open question whether unit segment graphs are delineated. More broadly, we explore which structures (large bicliques, half-graphs, or independent sets) are responsible for making the twin-width large on the main classes of intersection and visibility graphs. Our new results, combined with the FPT algorithm for first-order model checking on graphs given with O(1)-sequences [BKTW, JACM '22], give rise to a variety of algorithmic win-win arguments. They all fall in the same framework: If p is an FO definable graph parameter that effectively functionally upperbounds twin-width on a class C, then p(G) ⩾ k can be decided in FPT time f(k) ⋅ |V(G)|^O(1). For instance, we readily derive FPT algorithms for k-Ladder on visibility graphs of 1.5D terrains, and k-Independent Set on visibility graphs of simple polygons. This showcases that the theory of twin-width can serve outside of classes of bounded twin-width., LIPIcs, Vol. 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022), pages 9:1-9:18
- Published
- 2022
30. Deciding twin-width at most 4 is NP-complete
- Author
-
Bergé, Pierre, Bonnet, Édouard, Déprés, Hugues, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), ANR-21-CE48-0014,TWIN-WIDTH,Twin-width: théorie et applications(2021), and ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019)
- Subjects
FOS: Computer and information sciences ,Discrete Mathematics (cs.DM) ,Computational Complexity (cs.CC) ,68Q17 ,Computer Science - Computational Complexity ,lower bounds ,Theory of computation → Fixed parameter tractability ,Theory of computation → Graph algorithms analysis ,Computer Science - Data Structures and Algorithms ,FOS: Mathematics ,Mathematics - Combinatorics ,Data Structures and Algorithms (cs.DS) ,[INFO]Computer Science [cs] ,Combinatorics (math.CO) ,F.2.2 ,Computer Science - Discrete Mathematics ,Twin-width - Abstract
We show that determining if an $n$-vertex graph has twin-width at most 4 is NP-complete, and requires time $2^{\Omega(n/\log n)}$ unless the Exponential-Time Hypothesis fails. Along the way, we give an elementary proof that $n$-vertex graphs subdivided at least $2 \log n$ times have twin-width at most 4. We also show how to encode trigraphs $H$ (2-edge colored graphs involved in the definition of twin-width) into graphs $G$, in the sense that every $d$-sequence (sequence of vertex contractions witnessing that the twin-width is at most $d$) of $G$ inevitably creates $H$ as an induced subtrigraph, whereas there exists a partial $d$-sequence that actually goes from $G$ to $H$. We believe that these facts and their proofs can be of independent interest., Comment: 30 pages, 17 figures
- Published
- 2022
31. Twin-width IV: ordered graphs and matrices
- Author
-
Bonnet, Édouard, Giocanti, Ugo, de Mendez, Patrice Ossona, Simon, Pierre, Thomassé, Stéphan, Toruńczyk, Szymon, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Centre d'Analyse et de Mathématique sociales (CAMS), École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS), Computer Science Institute of Charles University [Prague] (IUUK), Charles University [Prague] (CU), University of California [Berkeley] (UC Berkeley), University of California (UC), University of Varsaw, ANR-21-CE48-0014,TWIN-WIDTH,Twin-width: théorie et applications(2021), and ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019)
- Subjects
FOS: Computer and information sciences ,[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,Computer Science - Logic in Computer Science ,Discrete Mathematics (cs.DM) ,Computational Complexity (cs.CC) ,05A05, 05A16, 05C30 ,Logic in Computer Science (cs.LO) ,Computer Science - Computational Complexity ,Computer Science - Data Structures and Algorithms ,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] ,FOS: Mathematics ,Mathematics - Combinatorics ,Data Structures and Algorithms (cs.DS) ,[INFO]Computer Science [cs] ,Combinatorics (math.CO) ,F.2.2 ,Computer Science - Discrete Mathematics - Abstract
We establish a list of characterizations of bounded twin-width for hereditary, totally ordered binary structures. This has several consequences. First, it allows us to show that a (hereditary) class of matrices over a finite alphabet either contains at least $n!$ matrices of size $n \times n$, or at most $c^n$ for some constant $c$. This generalizes the celebrated Stanley-Wilf conjecture/Marcus-Tardos theorem from permutation classes to any matrix class over a finite alphabet, answers our small conjecture [SODA '21] in the case of ordered graphs, and with more work, settles a question first asked by Balogh, Bollob\'as, and Morris [Eur. J. Comb. '06] on the growth of hereditary classes of ordered graphs. Second, it gives a fixed-parameter approximation algorithm for twin-width on ordered graphs. Third, it yields a full classification of fixed-parameter tractable first-order model checking on hereditary classes of ordered binary structures. Fourth, it provides a model-theoretic characterization of classes with bounded twin-width., Comment: 53 pages, 18 figures
- Published
- 2022
32. Sparsification and subexponential approximation
- Author
-
Bonnet, Édouard and Paschos, Vangelis Th.
- Published
- 2016
- Full Text
- View/download PDF
33. Twin-width VII: groups
- Author
-
Bonnet, Édouard, Geniet, Colin, Tessera, Romain, and Thomassé, Stéphan
- Subjects
FOS: Computer and information sciences ,Discrete Mathematics (cs.DM) ,FOS: Mathematics ,Mathematics - Combinatorics ,Group Theory (math.GR) ,Combinatorics (math.CO) ,G.2.2 ,05C25 (Primary) 20F65, 05C30 (Secondary) ,Mathematics - Group Theory ,Computer Science - Discrete Mathematics - Abstract
Twin-width is a recently introduced graph parameter with applications in algorithmics, combinatorics, and finite model theory. For graphs of bounded degree, finiteness of twin-width is preserved by quasi-isometry. Thus, through Cayley graphs, it defines a group invariant. We prove that groups which are abelian, hyperbolic, ordered, solvable, or with polynomial growth, have finite twin-width. Twin-width can be characterised by excluding patterns in the self-action by product of the group elements. Based on this characterisation, we propose a strengthening called uniform twin-width, which is stable under constructions such as group extensions, direct products, and direct limits. The existence of finitely generated groups with infinite twin-width is not immediate. We construct one using a result of Osajda on embeddings of graphs into groups. This implies the existence of a class of finite graphs with unbounded twin-width but containing $2^{O(n)} \cdot n!$ graphs on vertex set $\{1,\dots,n\}$, settling a question asked in a previous work., 33 pages, 7 figures
- Published
- 2022
34. Multi-parameter Analysis for Local Graph Partitioning Problems: Using Greediness for Parameterization
- Author
-
Bonnet, Édouard, Escoffier, Bruno, Paschos, Vangelis Th., and Tourniaire, Émeric
- Published
- 2015
- Full Text
- View/download PDF
35. Maximum Clique in Disk-Like Intersection Graphs
- Author
-
Bonnet, Édouard, Miltzow, T., Grelier, Nicolas, Saxena, Nitin, Simon, Sunil, Sub Geometric Computing, Geometric Computing, Bonnet, Édouard, Digraphes - - DIGRAPHS2019 - ANR-19-CE48-0013 - AAPG2019 - VALID, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon), Department of Computer Science [ETH Zürich] (D-INFK), Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich] (ETH Zürich), Utrecht University [Utrecht], ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), École normale supérieure de Lyon (ENS de Lyon), Nitin, Saxena, and Sunil, Simon
- Subjects
Computational Geometry (cs.CG) ,FOS: Computer and information sciences ,Maximum Clique ,Mathematics of computing → Graph algorithms ,Intersection Graphs ,Theory of computation → Computational geometry ,Computational Complexity (cs.CC) ,Disk Graphs ,[INFO] Computer Science [cs] ,16. Peace & justice ,APX-hardness ,Computer Science - Computational Complexity ,Disk graphs ,Intersection graphs ,Maximum clique ,Algorithms ,NP-hardness ,Computer Science - Data Structures and Algorithms ,68Q25, 68U05 ,Computer Science - Computational Geometry ,[INFO]Computer Science [cs] ,Data Structures and Algorithms (cs.DS) ,F.2.2 ,MathematicsofComputing_DISCRETEMATHEMATICS ,NPhardness - Abstract
We study the complexity of Maximum Clique in intersection graphs of convex objects in the plane. On the algorithmic side, we extend the polynomial-time algorithm for unit disks [Clark '90, Raghavan and Spinrad '03] to translates of any fixed convex set. We also generalize the efficient polynomial-time approximation scheme (EPTAS) and subexponential algorithm for disks [Bonnet et al. '18, Bonamy et al. '18] to homothets of a fixed centrally symmetric convex set. The main open question on that topic is the complexity of Maximum Clique in disk graphs. It is not known whether this problem is NP-hard. We observe that, so far, all the hardness proofs for Maximum Clique in intersection graph classes $\mathcal I$ follow the same road. They show that, for every graph $G$ of a large-enough class $\mathcal C$, the complement of an even subdivision of $G$ belongs to the intersection class $\mathcal I$. Then they conclude invoking the hardness of Maximum Independent Set on the class $\mathcal C$, and the fact that the even subdivision preserves that hardness. However there is a strong evidence that this approach cannot work for disk graphs [Bonnet et al. '18]. We suggest a new approach, based on a problem that we dub Max Interval Permutation Avoidance, which we prove unlikely to have a subexponential-time approximation scheme. We transfer that hardness to Maximum Clique in intersection graphs of objects which can be either half-planes (or unit disks) or axis-parallel rectangles. That problem is not amenable to the previous approach. We hope that a scaled down (merely NP-hard) variant of Max Interval Permutation Avoidance could help making progress on the disk case, for instance by showing the NP-hardness for (convex) pseudo-disks., Comment: 23 pages, 5 figures
- Published
- 2020
36. Twin-width III: Max Independent Set, Min Dominating Set, and Coloring
- Author
-
Bonnet, Édouard, Geniet, Colin, Kim, Eun Jung, Thomassé, Stéphan, Watrigant, Rémi, École normale supérieure de Lyon (ENS de Lyon), Warsaw University of Technology [Warsaw], Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), and ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019)
- Subjects
FOS: Computer and information sciences ,Discrete Mathematics (cs.DM) ,Parameterized Algorithms ,Computational Complexity (cs.CC) ,Exact Algorithms ,Max Independent Set ,Min Dominating Set ,Theory of computation → Fixed parameter tractability ,Computer Science - Computational Complexity ,Theory of computation → Graph algorithms analysis ,Computer Science - Data Structures and Algorithms ,FOS: Mathematics ,Coloring ,Mathematics - Combinatorics ,Data Structures and Algorithms (cs.DS) ,05C85 ,[INFO]Computer Science [cs] ,Combinatorics (math.CO) ,F.2.2 ,Approximation Algorithms ,Twin-width ,Computer Science - Discrete Mathematics ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
We recently introduced the notion of twin-width, a novel graph invariant, 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 2^{O(k)}n-time algorithms for k-Independent Set, r-Scattered Set, k-Clique, and k-Dominating Set when an O(1)-sequence of the graph is given in input. We further show how to solve the weighted version of k-Independent Set, Subgraph Isomorphism, and Induced Subgraph Isomorphism, in the slightly worse running time 2^{O(k log k)}n. Up to logarithmic factors in the exponent, all these running times are optimal, unless the Exponential Time Hypothesis fails. Like our FO model checking algorithm, these new 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 such a reverse scheme, we present a polynomial-time algorithm that properly colors the vertices of a graph with relatively few colors, thereby 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. It readily yields a constant approximation for Max Independent Set on K_t-free graphs of bounded twin-width, and a 2^{O(OPT)}-approximation for Min Coloring on bounded twin-width graphs. We further observe that a constant approximation for Max Independent Set on bounded twin-width graphs (but arbitrarily large clique number) would actually imply a PTAS. 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. This property is trivially shared with graphs of bounded average degree. Given that biclique edge-partition, we show how to solve the unweighted Single-Source Shortest Paths and hence All-Pairs Shortest Paths in time O(n log n) and time O(n² log n), respectively. In sharp contrast, even Diameter does not admit a truly subquadratic algorithm on bounded twin-width graphs, unless the Strong Exponential Time Hypothesis fails. The fourth algorithmic use of twin-width builds on the so-called versatile tree of contractions [Bonnet et al., SODA '21], a branching and more robust witness of low twin-width. We present constant-approximation algorithms for Min Dominating Set and related problems, on bounded twin-width graphs, by showing that the integrality gap is constant. This is done by going down the versatile tree and stopping accordingly to a problem-dependent criterion. At the reached node, a greedy approach yields the desired approximation., LIPIcs, Vol. 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), pages 35:1-35:20
- Published
- 2021
37. Inapproximability of Diameter in super-linear time: Beyond the 5/3 ratio
- Author
-
Bonnet, Édouard, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and École normale supérieure de Lyon (ENS de Lyon)
- Subjects
FOS: Computer and information sciences ,inapproximability ,SETH lower bounds ,Computational Complexity (cs.CC) ,k-Orthogonal Vectors ,Computer Science - Computational Complexity ,Theory of computation → Graph algorithms analysis ,Diameter ,Computer Science - Data Structures and Algorithms ,FOS: Mathematics ,Mathematics - Combinatorics ,Data Structures and Algorithms (cs.DS) ,05C85 ,[INFO]Computer Science [cs] ,Combinatorics (math.CO) ,F.2.2 - Abstract
We show, assuming the Strong Exponential Time Hypothesis, that for every $\varepsilon > 0$, approximating directed Diameter on $m$-arc graphs within ratio $7/4 - \varepsilon$ requires $m^{4/3 - o(1)}$ time. Our construction uses nonnegative edge weights but even holds for sparse digraphs, i.e., for which the number of vertices $n$ and the number of arcs $m$ satisfy $m = n \log^{O(1)} n$. This is the first result that conditionally rules out a near-linear time $5/3$-approximation for Diameter., 13 pages, 4 figures, expanded introduction and discussion on follow-up works
- Published
- 2021
38. Twin-width and permutations
- Author
-
Bonnet, Édouard, Nešetřil, Jaroslav, de Mendez, Patrice Ossona, Siebertz, Sebastian, and Thomassé, Stéphan
- Subjects
FOS: Computer and information sciences ,Computer Science - Logic in Computer Science ,Discrete Mathematics (cs.DM) ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Logic in Computer Science (cs.LO) ,Computer Science - Discrete Mathematics - Abstract
Inspired by a width invariant on permutations defined by Guillemot and Marx, Bonnet, Kim, Thomass\'e, and Watrigant introduced the twin-width of graphs, which is a parameter describing its structural complexity. This invariant has been further extended to binary structures, in several (basically equivalent) ways. We prove that a class of binary relational structures (that is: edge-colored partially directed graphs) has bounded twin-width if and only if it is a first-order transduction of a~proper permutation class. As a by-product, we show that every class with bounded twin-width contains at most $2^{O(n)}$ pairwise non-isomorphic $n$-vertex graphs.
- Published
- 2021
39. Parameterized Streaming Algorithms for Min-Ones d-SAT
- Author
-
Agrawal, Akanksha, Bonnet, Édouard, Curticapean, Radu, Miltzow, Tillmann, Saurabh, Saket, Biswas, Arindam, Brettell, Nick, Marx, Dániel, Raman, Venkatesh, Bonnet, Édouard, Homi Bhabha National Institute (HBNI), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Department of Mathematical Sciences (Durham University), Durham University, IT University of Copenhagen (ITU), Institute for Computer Science and Control [Budapest] (SZTAKI), Hungarian Academy of Sciences (MTA), Utrecht University [Utrecht], University of Bergen (UiB), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), IT University of Copenhagen, Wagner, Michael, Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)
- Subjects
000 Computer science, knowledge, general works ,Computer Science ,[INFO]Computer Science [cs] ,[INFO] Computer Science [cs] ,ComputingMilieux_MISCELLANEOUS - Abstract
In this work, we initiate the study of the Min-Ones d-SAT problem in the parameterized streaming model. An instance of the problem consists of a d-CNF formula F and an integer k, and the objective is to determine if F has a satisfying assignment which sets at most k variables to 1. In the parameterized streaming model, input is provided as a stream, just as in the usual streaming model. A key difference is that the bound on the read-write memory available to the algorithm is O(f(k) log n) (f: N -> N, a computable function) as opposed to the O(log n) bound of the usual streaming model. The other important difference is that the number of passes the algorithm makes over its input must be a (preferably small) function of k. We design a (k + 1)-pass parameterized streaming algorithm that solves Min-Ones d-SAT (d >= 2) using space O((kd^(ck) + k^d)log n) (c > 0, a constant) and a (d + 1)^k-pass algorithm that uses space O(k log n). We also design a streaming kernelization for Min-Ones 2-SAT that makes (k + 2) passes and uses space O(k^6 log n) to produce a kernel with O(k^6) clauses. To complement these positive results, we show that any k-pass algorithm for or Min-Ones d-SAT (d >= 2) requires space Omega(max{n^(1/k) / 2^k, log(n / k)}) on instances (F, k). This is achieved via a reduction from the streaming problem POT Pointer Chasing (Guha and McGregor [ICALP 2008]), which might be of independent interest. Given this, our (k + 1)-pass parameterized streaming algorithm is the best possible, inasmuch as the number of passes is concerned. In contrast to the results of Fafianie and Kratsch [MFCS 2014] and Chitnis et al. [SODA 2015], who independently showed that there are 1-pass parameterized streaming algorithms for Vertex Cover (a restriction of Min-Ones 2-SAT), we show using lower bounds from Communication Complexity that for any d >= 1, a 1-pass streaming algorithm for Min-Ones d-SAT requires space Omega(n). This excludes the possibility of a 1-pass parameterized streaming algorithm for the problem. Additionally, we show that any p-pass algorithm for the problem requires space Omega(n/p). publishedVersion
- Published
- 2019
40. Parameterized Hardness of Art Gallery Problems
- Author
-
Bonnet, Édouard, Miltzow, T., Sub Geometric Computing, Geometric Computing, Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Utrecht University [Utrecht], Edouard Bonnet is supported by the LABEX MILYON (ANR-10- LABX-0070) of Université de Lyon, within the program 'Investissementsd’Avenir' (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR). Tillmann Miltzow is supported by the ERC Consolidator Grant 615640-ForEFront. The author acknowledges generous support from the Netherlands Organisation for Scientific Research (NWO) under project no. 016.Veni.192.250., ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), ANR-11-IDEX-0007,Avenir L.S.E.,PROJET AVENIR LYON SAINT-ETIENNE(2011), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Sub Geometric Computing, Geometric Computing, Computer and Automation Research Institute [Budapest] (MTA SZTAKI ), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Sankowski, P, and Zaroliagis, C
- Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,Art gallery problem ,Art Gallery ,Parameterized complexity ,Computational Geometry ,0102 computer and information sciences ,[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] ,01 natural sciences ,Computational geometry ,Combinatorics ,Mathematics (miscellaneous) ,Computable function ,Line segment ,ETH lower bound ,Point (geometry) ,[INFO]Computer Science [cs] ,0101 mathematics ,Simple polygon ,Mathematics ,parameterized complexity ,Exponential time hypothesis ,000 Computer science, knowledge, general works ,010102 general mathematics ,QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány ,art gallery ,Vertex (geometry) ,ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY/F.2.2: Nonnumerical Algorithms and Problems ,010201 computation theory & mathematics ,intractability ,Computer Science ,Parameterized Complexity - Abstract
Given a simple polygon P on n vertices, two points x , y in P are said to be visible to each other if the line segment between x and y is contained in P . The P oint G uard A rt G allery problem asks for a minimum set S such that every point in P is visible from a point in S . The V ertex G uard A rt G allery problem asks for such a set S subset of the vertices of P . A point in the set S is referred to as a guard. For both variants, we rule out any f ( k ) n o ( k / log k ) algorithm, where k := | S | is the number of guards, for any computable function f , unless the exponential time hypothesis fails. These lower bounds almost match the n O ( k ) algorithms that exist for both problems.
- Published
- 2020
41. 4 vs 7 Sparse Undirected Unweighted Diameter Is SETH-hard at Time n4/3.
- Author
-
BONNET, ÉDOUARD
- Subjects
TIME ,DIAMETER ,HYPOTHESIS - Abstract
We show, assuming the Strong Exponential Time Hypothesis, that for every ε > 0, approximating undirected unweighted Diameter on n-vertexm-edge graphs within ratio 7/4-ε requiresm
4/3-o(1) time, evenwhenm = ˜O (n). This is the first result that conditionally rules out a near-linear time 5/3-approximation for undirected Diameter. [ABSTRACT FROM AUTHOR]- Published
- 2022
- Full Text
- View/download PDF
42. Fine-grained complexity of coloring unit disks and balls
- Author
-
Biró, Csaba, Bonnet, Édouard, Marx, Dániel, Miltzow, Tillmann, Rzazewski, Pawel, Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Computer and Automation Research Institute [Budapest] (MTA SZTAKI ), Faculty of Mathematics and Information Science [Warszawa], Warsaw University of Technology [Warsaw], École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), University of Louisville, Katz, MJ, Aronov, B, and Bonnet, Édouard
- Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,000 Computer science, knowledge, general works ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány ,0102 computer and information sciences ,02 engineering and technology ,[INFO] Computer Science [cs] ,[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] ,01 natural sciences ,ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory ,[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG] ,ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY/F.2.2: Nonnumerical Algorithms and Problems ,010201 computation theory & mathematics ,Computer Science ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,[INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC] ,[INFO]Computer Science [cs] - Abstract
On planar graphs, many classic algorithmic problems enjoy a certain ``square root phenomenon'' and can be solved significantly faster than what is known to be possible on general graphs: for example, Independent Set, 3-Coloring, Hamiltonian Cycle, Dominating Set can be solved in time $2^{O(\sqrt{n})}$ on an $n$-vertex planar graph, while no $2^{o(n)}$ algorithms exist for general graphs, assuming the Exponential Time Hypothesis (ETH). The square root in the exponent seems to be best possible for planar graphs: assuming the ETH, the running time for these problems cannot be improved to $2^{o(\sqrt{n})}$. In some cases, a similar speedup can be obtained for 2-dimensional geometric problems, for example, there are $2^{O(\sqrt{n}\log n)}$ time algorithms for Independent Set on unit disk graphs or for TSP on 2-dimensional point sets. In this paper, we explore whether such a speedup is possible for geometric coloring problems. On the one hand, geometric objects can behave similarly to planar graphs: 3-Coloring can be solved in time $2^{O(\sqrt{n})}$ on the intersection graph of $n$ disks in the plane and, assuming the ETH, there is no such algorithm with running time $2^{o(\sqrt{n})}$. On the other hand, if the number $\ell$ of colors is part of the input, then no such speedup is possible: Coloring the intersection graph of $n$ unit disks with $\ell$ colors cannot be solved in time $2^{o(n)}$, assuming the ETH. More precisely, we exhibit a smooth increase of complexity as the number $\ell$ of colors increases: If we restrict the number of colors to $\ell=\Theta(n^{\alpha})$ for some $0\le \alpha\le 1$, then the problem of coloring the intersection graph of $n$ disks with $\ell$ colors • can be solved in time $\exp \left( O(n^{\frac{1+\alpha}{2}}\log n) \right)=\exp \left( O(\sqrt{n\ell}\log n) \right)$, and • cannot be solved in time $\exp \left ( o(n^{\frac{1+\alpha}{2}})\right )=\exp \left( o(\sqrt{n\ell}) \right)$, even on unit disks, unless the ETH fails. More generally, we consider the problem of coloring $d$-dimensional balls in the Euclidean space and obtain analogous results showing that the problem • can be solved in time $\exp \left( O(n^{\frac{d-1+\alpha}{d}}\log n) \right)$ $=\exp \left( O(n^{1-1/d}\ell^{1/d}\log n) \right)$, and • cannot be solved in time $\exp \left(O(n^{\frac{d-1+\alpha}{d}-\epsilon})\right)= \exp \left(O(n^{1-1/d-\epsilon}\ell^{1/d})\right)$ for any $\epsilon>0$, even for unit balls, unless the ETH fails. Finally, we prove that fatness is crucial to obtain subexponential algorithms for coloring. We show that existence of an algorithm coloring an intersection graph of segments using a constant number of colors in time $2^{o(n)}$ already refutes the ETH., Journal of Computational Geometry, Vol. 9 No. 2 (2018): Special Issue of Selected Papers from SoCG 2017
- Published
- 2018
43. Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP
- Author
-
Bonnet, Édouard, Iwata, Yoichi, Jansen, Bart M.P., Kowalik, Łukasz, Bender, Michael A., Svensson, Ola, Herman, Grzegorz, National Institute of Informatics (NII), Eindhoven University of Technology [Eindhoven] (TU/e), University of Warsaw (UW), Algorithms, Geometry and Applications, and Wagner, Michael
- Subjects
FOS: Computer and information sciences ,Computer Science - Computational Complexity ,000 Computer science, knowledge, general works ,Computational Complexity ,Data Structures and Algorithms ,Computer Science ,Computer Science - Data Structures and Algorithms ,traveling salesman problem ,bounded degree ,Data Structures and Algorithms (cs.DS) ,[INFO]Computer Science [cs] ,Computational Complexity (cs.CC) ,k-OPT - Abstract
Local search is a widely-employed strategy for finding good solutions to Traveling Salesman Problem. We analyze the problem of determining whether the weight of a given cycle can be decreased by a popular $k$-opt move. Earlier work has shown that (i) assuming the Exponential Time Hypothesis, there is no algorithm to find an improving $k$-opt move in time $f(k)n^{o(k/\log k)}$ for any function $f$, while (ii) it is possible to improve on the brute-force running time of $O(n^k)$ and save linear factors in the exponent. Modern TSP heuristics show that very good global solutions can already be reached using only the top-$O(1)$ most promising edges incident to each vertex. Motivated by this, we study the problem of finding an improving $k$-move in bounded degree graphs, presenting new algorithms and conditional lower bounds. We show that the aforementioned ETH lower bound also holds for graphs of maximum degree three, but that in bounded-degree graphs the best improving $k$-move can be found in time $O(n^{23k/135+o(k)})$. This improves upon the best-known bounds for general graphs. Due to its practical importance, we devote special attention to the range of $k$ in which improving $k$-moves in bounded-degree graphs can be found in quasi-linear time. For $k\le 7$, we give quasi-linear time algorithms for general weights. For $k=8$ we obtain a quasi-linear time algorithm for polylogarithmic weights. On the other hand, based on established fine-grained complexity hypotheses, we prove that the $k=9$ case does not admit quasi-linear time algorithms. Hence we fully characterize the values of $k$ for which quasi-linear time algorithms exist for polylogarithmic weights on bounded-degree graphs. As a byproduct, we show a new bound on pathwidth of even graphs which results in improved running time bounds for counting $k$-vertex paths and cycles., A new running time bound for counting cycles and paths in graphs was added
- Published
- 2019
44. The Parameterized Complexity of Positional Games
- Author
-
Bonnet, Édouard, Gaspers, Serge, Lambilliotte, Antonin, Rümmele, Stefan, Saffidine, Abdallah, Middlesex University [London], Data61 [Canberra] (CSIRO), Australian National University (ANU)-Commonwealth Scientific and Industrial Research Organisation [Canberra] (CSIRO), École normale supérieure de Lyon (ENS de Lyon), and École normale supérieure - Lyon (ENS Lyon)
- Subjects
FOS: Computer and information sciences ,[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,Computer Science::Computer Science and Game Theory ,000 Computer science, knowledge, general works ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,ComputingMilieux_PERSONALCOMPUTING ,Computational Complexity (cs.CC) ,Maker-Maker games ,Computer Science - Computational Complexity ,Computer Science ,Hex ,Enforcer-Avoider games ,parameterized complexity theory ,[INFO]Computer Science [cs] ,Maker-Breaker games ,F.2.2 - Abstract
We study the parameterized complexity of several positional games. Our main result is that Short Generalized Hex is W[1]-complete parameterized by the number of moves. This solves an open problem from Downey and Fellows' influential list of open problems from 1999. Previously, the problem was thought of as a natural candidate for AW[*]-completeness. Our main tool is a new fragment of first-order logic where universally quantified variables only occur in inequalities. We show that model-checking on arbitrary relational structures for a formula in this fragment is W[1]-complete when parameterized by formula size. We also consider a general framework where a positional game is represented as a hypergraph and two players alternately pick vertices. In a Maker-Maker game, the first player to have picked all the vertices of some hyperedge wins the game. In a Maker-Breaker game, the first player wins if she picks all the vertices of some hyperedge, and the second player wins otherwise. In an Enforcer-Avoider game, the first player wins if the second player picks all the vertices of some hyperedge, and the second player wins otherwise. Short Maker-Maker is AW[*]-complete, whereas Short Maker-Breaker is W[1]-complete and Short Enforcer-Avoider co-W[1]-complete parameterized by the number of moves. This suggests a rough parameterized complexity categorization into positional games that are complete for the first level of the W-hierarchy when the winning configurations only depend on which vertices one player has been able to pick, but AW[*]-completeness when the winning condition depends on which vertices both players have picked. However, some positional games where the board and the winning configurations are highly structured are fixed-parameter tractable. We give another example of such a game, Short k-Connect, which is fixed-parameter tractable when parameterized by the number of moves., Comment: To appear in the Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
- Published
- 2017
45. Designing RNA Secondary Structures Is Hard.
- Author
-
Bonnet, Édouard, Rzążewski, Paweł, and Sikora, Florian
- Subjects
- *
RNA , *NUCLEOTIDE sequence , *LIBRARY software , *COMPUTATIONAL complexity , *DESIGN software , *BASE pairs , *OPEN-ended questions - Abstract
A ribonucleic acid (RNA) sequence is a word over an alphabet on four elements { A , C , G , U } called bases. RNA sequences fold into secondary structures where some bases pair with one another, while others remain unpaired. The two fundamental problems in RNA algorithmic are to predict how sequences fold within some models of energy and to design sequences of bases that will fold into targeted secondary structures. Predicting how a given RNA sequence folds into a pseudoknot-free secondary structure is known to be solvable in cubic time since the eighties and in truly subcubic time by a recent result of Bringmann et al. (FOCS, 2016), whereas Lyngsø has shown it is computationally hard if pseudoknots are allowed (ICALP, 2004). As a stark contrast, it is unknown whether or not designing a given RNA secondary structure is a tractable task; this has been raised as a challenging open question by Condon (ICALP, 2003). Because of its crucial importance in a number of fields such as pharmaceutical research and biochemistry, there are dozens of heuristics and software libraries dedicated to the RNA secondary structure design. It is therefore rather surprising that the computational complexity of this central problem in bioinformatics has been unsettled for decades. In this article, we show that in the simplest model of energy, which is the Watson–Crick model, the design of secondary structures is computationally hard if one adds natural constraints of the form: indexiof the sequence has to be labeled by baseb. This negative result suggests that the same lower bound holds for more realistic models of energy. It is noteworthy that the additional constraints are by no means artificial: they are provided by all the RNA design pieces of software and they do correspond to the actual practice (e.g., the instances of the EteRNA project). [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
46. Fixed-Parameter Approximability of Boolean MinCSPs
- Author
-
Bonnet, Édouard, Egri, László, Marx, Dániel, Sankowski, P, Zaroliagis, C, and Computer and Automation Research Institute [Budapest] (MTA SZTAKI )
- Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,000 Computer science, knowledge, general works ,fixed-parameter tractability ,Computer Science ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,approximability ,QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány ,Computer Science::Computational Complexity ,constraint satisfaction problems - Abstract
The minimum unsatisfiability version of a constraint satisfaction problem (CSP) asks for an assignment where the number of unsatisfied constraints is minimum possible, or equivalently, asks for a minimum-size set of constraints whose deletion makes the instance satisfiable. For a finite set Gamma of constraints, we denote by CSP(Gamma) the restriction of the problem where each constraint is from Gamma. The polynomial-time solvability and the polynomial-time approximability of CSP(Gamma) were fully characterized by [Khanna et al. SICOMP 2000]. Here we study the fixed-parameter (FP-) approximability of the problem: given an instance and an integer k, one has to find a solution of size at most g(k) in time f(k)n^{O(1)} if a solution of size at most k exists. We especially focus on the case of constant-factor FP-approximability. Our main result classifies each finite constraint language Gamma into one of three classes: (1) CSP(Gamma) has a constant-factor FP-approximation; (2) CSP(Gamma) has a (constant-factor) FP-approximation if and only if Nearest Codeword has a (constant-factor) FP-approximation; (3) CSP(Gamma) has no FP-approximation, unless FPT=W[P]. We show that problems in the second class do not have constant-factor FP-approximations if both the Exponential-Time Hypothesis (ETH) and the Linear PCP Conjecture (LPC) hold. We also show that such an approximation would imply the existence of an FP-approximation for the k-Densest Subgraph problem with ratio 1-epsilon for any epsilon>0.
- Published
- 2016
47. Parameterized (in)approximability of subset problems
- Author
-
Bonnet, Édouard and Paschos, Vangelis Th.
- Published
- 2014
- Full Text
- View/download PDF
48. Time-approximation trade-offs for inapproximable problems.
- Author
-
Bonnet, Édouard, Lampis, Michael, and Paschos, Vangelis Th.
- Subjects
- *
POLYNOMIAL time algorithms , *APPROXIMATION algorithms , *EXPONENTIAL functions , *GEOMETRIC vertices , *SET theory - Abstract
In this paper we focus on problems inapproximable in polynomial time and explore how quickly their approximability improves as the allowed running time is gradually increased from polynomial to (sub-)exponential. We tackle a number of problems: For Min Independent Dominating Set , Max Induced Path , Forest and Tree , for any r ( n ) , a simple, known scheme gives an approximation ratio of r in time roughly r n / r . We show that, if this running time could be significantly improved, the ETH would fail. For Max Minimal Vertex Cover we give a r -approximation in time 2 n / r . We match this with a similarly tight result. We also give a log r -approximation for Min ATSP in time 2 n / r and an r -approximation for Max Grundy Coloring in time r n / r . Finally, we investigate the approximability of Min Set Cover , when measuring the running time as a function of the number of sets in the input. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
49. Sparsification and subexponential approximation.
- Author
-
Bonnet, Édouard and Paschos, Vangelis Th.
- Subjects
- *
GEOMETRIC vertices , *APPROXIMATION theory , *FEEDBACK control systems , *MATHEMATICAL optimization , *COMPUTER science - Abstract
Instance sparsification is well-known in the world of exact computation since it is very closely linked to the
Exponential Time Hypothesis . In this paper, we extend the concept of sparsification in order to capture subexponential time approximation. We develop a new tool for inapproximability, called approximation preserving sparsification, and use it in order to get strong inapproximability results in subexponential time for several fundamental optimization problems such as min dominating set, min feedback vertex set, min set cover, min feedback arc set, and others. [ABSTRACT FROM AUTHOR]- Published
- 2018
- Full Text
- View/download PDF
50. Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property.
- Author
-
Bonnet, Édouard, Brettell, Nick, Kwon, O-joung, and Marx, Dániel
- Published
- 2016
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.