9 results on '"Bonnet, Édouard"'
Search Results
2. 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
- Subjects
- *
BIPARTITE graphs , *DOMINATING set , *NP-complete problems , *SPARSE graphs , *POLYNOMIAL time algorithms , *INDEPENDENT sets , *COMPLETE graphs - Abstract
A graph is O k -free if it does not contain k pairwise vertex-disjoint and non-adjacent cycles. We prove that "sparse" (here, not containing large complete bipartite graphs as subgraphs) O k -free graphs have treewidth (even, feedback vertex set number) at most logarithmic in the number of vertices. This is optimal, as there is an infinite family of O 2 -free graphs without K 2 , 3 as a subgraph and whose treewidth is (at least) logarithmic. Using our result, we show that Maximum Independent Set and 3-Coloring in O k -free graphs can be solved in quasi-polynomial time. Other consequences include that most of the central NP-complete problems (such as Maximum Independent Set , Minimum Vertex Cover , Minimum Dominating Set , Minimum Coloring) can be solved in polynomial time in sparse O k -free graphs, and that deciding the O k -freeness of sparse graphs is polynomial time solvable. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
3. 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
4. Twin-width can be exponential in treewidth.
- Author
-
Bonnet, Édouard and Déprés, Hugues
- Subjects
- *
TREE size , *INTEGERS - Abstract
For any small positive real ε and integer t > 1 ε , we build a graph with a vertex deletion set of size t to a tree, and twin-width greater than 2 (1 − ε) t. In particular, this shows that the twin-width is sometimes exponential in the treewidth, in the so-called oriented twin-width and grid number, and that adding an apex may multiply the twin-width by at least 2 − ε. Except for the one in oriented twin-width, these lower bounds are essentially tight. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
5. Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth
- Author
-
Bergougnoux, Benjamin, Bonnet, Édouard, Brettell, Nick, Kwon, O-joung, 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), École normale supérieure de Lyon (ENS de Lyon), Victoria University of Wellington, Incheon National University, ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), École normale supérieure - Lyon (ENS Lyon), Bonnet, Édouard, and Digraphes - - DIGRAPHS2019 - ANR-19-CE48-0013 - AAPG2019 - VALID
- Subjects
FOS: Computer and information sciences ,Parameterized Algorithms ,Vertex Deletion Problems ,68Q27, 05C85 ,Multiway Cut ,Treewidth ,Graph Modification ,[INFO] Computer Science [cs] ,Computational Complexity (cs.CC) ,Theory of computation → Fixed parameter tractability ,Computer Science - Computational Complexity ,Theory of computation → Graph algorithms analysis ,Computer Science - Data Structures and Algorithms ,[INFO]Computer Science [cs] ,Data Structures and Algorithms (cs.DS) ,F.2.2 ,Subset Feedback Vertex Set ,Computer Science::Data Structures and Algorithms - Abstract
The Cut & Count technique and the rank-based approach have lead to single-exponential FPT algorithms parameterized by treewidth, that is, running in time $2^{O(tw)}n^{O(1)}$, for Feedback Vertex Set and connected versions of the classical graph problems (such as Vertex Cover and Dominating Set). We show that Subset Feedback Vertex Set, Subset Odd Cycle Transversal, Restricted Edge-Subset Feedback Edge Set, Node Multiway Cut, and Multiway Cut are unlikely to have such running times. More precisely, we match algorithms running in time $2^{O(tw \log tw)}n^{O(1)}$ with tight lower bounds under the Exponential-Time Hypothesis (ETH), ruling out $2^{o(tw \log tw)}n^{O(1)}$, where $n$ is the number of vertices and $tw$ is the treewidth of the input graph. Our algorithms extend to the weighted case, while our lower bounds also hold for the larger parameter pathwidth and do not require weights. We also show that, in contrast to Odd Cycle Transversal, there is no $2^{o(tw \log tw)}n^{O(1)}$-time algorithm for Even Cycle Transversal under the ETH., 25 pages, 5 figures
- Published
- 2020
- Full Text
- View/download PDF
6. Metric Dimension Parameterized by Treewidth
- Author
-
Édouard Bonnet, Nidhi Purohit, 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), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), 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), and Bonnet, Édouard
- Subjects
FOS: Computer and information sciences ,General Computer Science ,Parameterized complexity ,0102 computer and information sciences ,02 engineering and technology ,[INFO] Computer Science [cs] ,Computational Complexity (cs.CC) ,01 natural sciences ,68Q17 ,Combinatorics ,Computable function ,Pathwidth ,Computer Science - Data Structures and Algorithms ,0202 electrical engineering, electronic engineering, information engineering ,Data Structures and Algorithms (cs.DS) ,[INFO]Computer Science [cs] ,Time complexity ,ComputingMilieux_MISCELLANEOUS ,Mathematics ,Exponential time hypothesis ,Degree (graph theory) ,Applied Mathematics ,Computer Science Applications ,Metric dimension ,Treewidth ,Computer Science - Computational Complexity ,010201 computation theory & mathematics ,020201 artificial intelligence & image processing ,F.2.2 ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
A resolving set $S$ of a graph $G$ is a subset of its vertices such that no two vertices of $G$ have the same distance vector to $S$. The Metric Dimension problem asks for a resolving set of minimum size, and in its decision form, a resolving set of size at most some specified integer. This problem is NP-complete, and remains so in very restricted classes of graphs. It is also W[2]-complete with respect to the size of the solution. Metric Dimension has proven elusive on graphs of bounded treewidth. On the algorithmic side, a polytime algorithm is known for trees, and even for outerplanar graphs, but the general case of treewidth at most two is open. On the complexity side, no parameterized hardness is known. This has led several papers on the topic to ask for the parameterized complexity of Metric Dimension with respect to treewidth. We provide a first answer to the question. We show that Metric Dimension parameterized by the treewidth of the input graph is W[1]-hard. More refinedly we prove that, unless the Exponential Time Hypothesis fails, there is no algorithm solving Metric Dimension in time $f(\text{pw})n^{o(\text{pw})}$ on $n$-vertex graphs of constant degree, with $\text{pw}$ the pathwidth of the input graph, and $f$ any computable function. This is in stark contrast with an FPT algorithm of Belmonte et al. [SIAM J. Discrete Math. '17] with respect to the combined parameter $\text{tl}+\Delta$, where $\text{tl}$ is the tree-length and $\Delta$ the maximum-degree of the input graph., Comment: 23 pages, 4 figures, long version of IPEC 2019
- Published
- 2019
7. Complexity of token swapping and its variants
- Author
-
Édouard Bonnet, Paweł Rzążewski, Tillmann Miltzow, Bonnet, Édouard, Heribert, Vollmer, Brigitte, Vallée, Computer and Automation Research Institute [Budapest] (MTA SZTAKI ), Faculty of Mathematics and Information Science [Warszawa], Warsaw University of Technology [Warsaw], Modèles de calcul, Complexité, Combinatoire (MC2), 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)-É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 - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and 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)
- Subjects
FOS: Computer and information sciences ,Discrete Mathematics (cs.DM) ,Parameterized complexity ,Informatique appliquée logiciel ,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,02 engineering and technology ,Computational Complexity (cs.CC) ,Security token ,W[1]-hardness ,01 natural sciences ,Upper and lower bounds ,0202 electrical engineering, electronic engineering, information engineering ,NP-hardness ,Data Structures and Algorithms (cs.DS) ,token swapping ,Mathematics ,Complement (set theory) ,Sequence ,Token swapping ,Applied Mathematics ,Computer Science Applications ,Mathématiques ,ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory ,010201 computation theory & mathematics ,020201 artificial intelligence & image processing ,[INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC] ,[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,General Computer Science ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,0102 computer and information sciences ,[INFO] Computer Science [cs] ,Combinatorics ,Computable function ,Computer Science - Data Structures and Algorithms ,[INFO]Computer Science [cs] ,0101 mathematics ,parameterized complexity ,Discrete mathematics ,000 Computer science, knowledge, general works ,Informatique générale ,010102 general mathematics ,020206 networking & telecommunications ,QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány ,Vertex (geometry) ,Treewidth ,Computer Science - Computational Complexity ,ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY/F.2.2: Nonnumerical Algorithms and Problems ,Computer Science ,Computer Science - Discrete Mathematics ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
In the Token Swapping problem we are given a graph with a token placed on each vertex. Each token has exactly one destination vertex, and we try to move all the tokens to their destinations, using the minimum number of swaps, i.e. operations of exchanging the tokens on two adjacent vertices. As the main result of this paper, we show that Token Swapping is W[ 1 ] -hard parameterized by the length k of a shortest sequence of swaps. In fact, we prove that, for any computable function f, it cannot be solved in time f(k) no ( k / log k ) where n is the number of vertices of the input graph, unless the ETH fails. This lower bound almost matches the trivial nO ( k )-time algorithm. We also consider two generalizations of the Token Swapping, namely Colored Token Swapping (where the tokens have colors and tokens of the same color are indistinguishable), and Subset Token Swapping (where each token has a set of possible destinations). To complement the hardness result, we prove that even the most general variant, Subset Token Swapping, is FPT in nowhere-dense graph classes. Finally, we consider the complexities of all three problems in very restricted classes of graphs: graphs of bounded treewidth and diameter, stars, cliques, and paths, trying to identify the borderlines between polynomial and NP-hard cases., SCOPUS: ar.j, info:eu-repo/semantics/published
- Published
- 2018
8. Complexity of Grundy coloring and its variants
- Author
-
Eun Jung Kim, Florian Sikora, Florent Foucaud, Édouard Bonnet, Bonnet, Édouard, 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), Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (LIMOS), SIGMA Clermont (SIGMA Clermont)-Université d'Auvergne - Clermont-Ferrand I (UdA)-Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Blaise Pascal - Clermont-Ferrand 2 (UBP), Institute for Computer Science and Control [Budapest] (SZTAKI), Hungarian Academy of Sciences (MTA), Modèles de calcul, Complexité, Combinatoire (MC2), 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)-É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 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)-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), and Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
FOS: Computer and information sciences ,[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,Computational complexity theory ,Discrete Mathematics (cs.DM) ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION ,Parameterized complexity ,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,0102 computer and information sciences ,[INFO] Computer Science [cs] ,01 natural sciences ,Combinatorics ,Greedy coloring ,Grundy number ,Chordal graph ,Computer Science - Data Structures and Algorithms ,FOS: Mathematics ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,Data Structures and Algorithms (cs.DS) ,Grundy coloring ,[INFO]Computer Science [cs] ,0101 mathematics ,Mathematics ,ComputingMethodologies_COMPUTERGRAPHICS ,Exponential time hypothesis ,Mathematics::Combinatorics ,Applied Mathematics ,010102 general mathematics ,Exact algorithm ,Interval graph ,Connected Grundy ,Complexity ,Vertex (geometry) ,Treewidth ,Computational complexity ,010201 computation theory & mathematics ,Bipartite graph ,Weak Grundy ,[INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC] ,Combinatorics (math.CO) ,Computer Science - Discrete Mathematics ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
The Grundy number of a graph is the maximum number of colors used by the greedy coloring algorithm over all vertex orderings. In this paper, we study the computational complexity of GRUNDY COLORING, the problem of determining whether a given graph has Grundy number at least $k$. We also study the variants WEAK GRUNDY COLORING (where the coloring is not necessarily proper) and CONNECTED GRUNDY COLORING (where at each step of the greedy coloring algorithm, the subgraph induced by the colored vertices must be connected). We show that GRUNDY COLORING can be solved in time $O^*(2.443^n)$ and WEAK GRUNDY COLORING in time $O^*(2.716^n)$ on graphs of order $n$. While GRUNDY COLORING and WEAK GRUNDY COLORING are known to be solvable in time $O^*(2^{O(wk)})$ for graphs of treewidth $w$ (where $k$ is the number of colors), we prove that under the Exponential Time Hypothesis (ETH), they cannot be solved in time $O^*(2^{o(w\log w)})$. We also describe an $O^*(2^{2^{O(k)}})$ algorithm for WEAK GRUNDY COLORING, which is therefore $\fpt$ for the parameter $k$. Moreover, under the ETH, we prove that such a running time is essentially optimal (this lower bound also holds for GRUNDY COLORING). Although we do not know whether GRUNDY COLORING is in $\fpt$, we show that this is the case for graphs belonging to a number of standard graph classes including chordal graphs, claw-free graphs, and graphs excluding a fixed minor. We also describe a quasi-polynomial time algorithm for GRUNDY COLORING and WEAK GRUNDY COLORING on apex-minor graphs. In stark contrast with the two other problems, we show that CONNECTED GRUNDY COLORING is $\np$-complete already for $k=7$ colors., Comment: 24 pages, 7 figures. This version contains some new results and improvements. A short paper based on version v2 appeared in COCOON'15
- Published
- 2018
9. Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
- Author
-
Édouard Bonnet, Dániel Marx, Nick Brettell, O-joung Kwon, Computer and Automation Research Institute [Budapest] (MTA SZTAKI ), Bonnet, Édouard, Discrete Mathematics, and Herbstritt, Marc
- Subjects
FOS: Computer and information sciences ,[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.1: Combinatorics ,General Computer Science ,Discrete Mathematics (cs.DM) ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Block (permutation group theory) ,feed-back vertex set ,Parameterized complexity ,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,0102 computer and information sciences ,02 engineering and technology ,Characterization (mathematics) ,01 natural sciences ,Feedback Vertex Set ,Chordal graph ,Combinatorics ,Computer Science - Data Structures and Algorithms ,0202 electrical engineering, electronic engineering, information engineering ,treewidth ,Data Structures and Algorithms (cs.DS) ,fixed-parameter tractable algorithms ,Mathematics ,000 Computer science, knowledge, general works ,Applied Mathematics ,QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány ,Function (mathematics) ,chordal graphs ,Computer Science Applications ,Treewidth ,ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory ,010201 computation theory & mathematics ,Bounded function ,Computer Science ,020201 artificial intelligence & image processing ,Feedback vertex set ,[INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC] ,component order connectivity ,Computer Science - Discrete Mathematics - Abstract
It has long been known that Feedback Vertex Set can be solved in time $2^{\mathcal{O}(w\log w)}n^{\mathcal{O}(1)}$ on $n$-vertex graphs of treewidth $w$, but it was only recently that this running time was improved to $2^{\mathcal{O}(w)}n^{\mathcal{O}(1)}$, that is, to single-exponential parameterized by treewidth. We investigate which generalizations of Feedback Vertex Set can be solved in a similar running time. Formally, for a class $\mathcal{P}$ of graphs, the Bounded $\mathcal{P}$-Block Vertex Deletion problem asks, given a graph~$G$ on $n$ vertices and positive integers~$k$ and~$d$, whether $G$ contains a set~$S$ of at most $k$ vertices such that each block of $G-S$ has at most $d$ vertices and is in $\mathcal{P}$. Assuming that $\mathcal{P}$ is recognizable in polynomial time and satisfies a certain natural hereditary condition, we give a sharp characterization of when single-exponential parameterized algorithms are possible for fixed values of $d$: if $\mathcal{P}$ consists only of chordal graphs, then the problem can be solved in time $2^{\mathcal{O}(wd^2)} n^{\mathcal{O}(1)}$, and if $\mathcal{P}$ contains a graph with an induced cycle of length $\ell\ge 4$, then the problem is not solvable in time $2^{o(w\log w)} n^{\mathcal{O}(1)}$ even for fixed $d=\ell$, unless the ETH fails. We also study a similar problem, called Bounded $\mathcal{P}$-Component Vertex Deletion, where the target graphs have connected components of small size rather than blocks of small size, and we present analogous results. For this problem, we also show that if $d$ is part of the input and $\mathcal{P}$ contains all chordal graphs, then it cannot be solved in time $f(w)n^{o(w)}$ for some function $f$, unless the ETH fails., Comment: 43 pages, 9 figures
- Published
- 2017
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.