11 results on '"Bidimensionality"'
Search Results
2. Contraction Bidimensionality of Geometric Intersection Graphs.
- Author
-
Baste, Julien and Thilikos, Dimitrios M.
- Subjects
- *
ALGORITHMS - Abstract
Given a graph G, we define bcg (G) as the minimum k for which G can be contracted to the uniformly triangulated grid Γ k . A graph class G has the SQGC property if every graph G ∈ G has treewidth O (bcg (G) c) for some 1 ≤ c < 2 . The SQGC property is important for algorithm design as it defines the applicability horizon of a series of meta-algorithmic results, in the framework of bidimensionality theory, related to fast parameterized algorithms, kernelization, and approximation schemes. These results apply to a wide family of problems, namely problems that are contraction-bidimensional. Our main combinatorial result reveals a wide family of graph classes that satisfy the SQGC property. This family includes, in particular, bounded-degree string graphs. This considerably extends the applicability of bidimensionality theory for contraction bidimensional problems. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
3. BIDIMENSIONALITY AND KERNELS.
- Author
-
FOMIN, FEDOR V., LOKSHTANOV, DANIEL, SAURABH, SAKET, and THILIKOS, DIMITRIOS M.
- Subjects
- *
POLYNOMIAL approximation , *POLYNOMIAL time algorithms , *GRAPH algorithms , *ALGORITHMS - Abstract
Bidimensionality theory was introduced by [E. D. Demaine et al., J. ACM, 52 (2005), pp. 866--893] as a tool to obtain subexponential time parameterized algorithms on H-minor-free graphs. In [E. D. Demaine and M. Hajiaghayi, Bidimensionality: New connections between FPT algorithms and PTASs, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2005, pp. 590--601] this theory was extended in order to obtain polynomial time approximation schemes (PTASs) for bidimensional problems. In this work, we establish a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of linear kernels for parameterized problems. In particular, we prove that every minor (resp., contraction) bidimensional problem that satisfies a separation property and is expressible in Countable Monadic Second Order Logic (CMSO) admits a linear kernel for classes of graphs that exclude a fixed graph (resp., an apex graph) H as a minor. Our results imply that a multitude of bidimensional problems admit linear kernels on the corresponding graph classes. For most of these problems no polynomial kernels on H-minor-free graphs were known prior to our work. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
4. Graph Minors and Parameterized Algorithm Design
- Author
-
Thilikos, Dimitrios M., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Bodlaender, Hans L., editor, Downey, Rod, editor, Fomin, Fedor V., editor, and Marx, Dániel, editor
- Published
- 2012
- Full Text
- View/download PDF
5. Bidimensionality and Kernels
- Author
-
Saket Saurabh, Fedor V. Fomin, Dimitrios M. Thilikos, Daniel Lokshtanov, Department of Informatics [Bergen] (UiB), University of Bergen (UiB), Department of Computer Science [Santa Barbara] (CS-UCSB), University of California [Santa Barbara] (UCSB), University of California-University of California, Institute of Mathematical Sciences [Chennai] (IMSc), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), and Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)
- Subjects
FOS: Computer and information sciences ,General Computer Science ,General Mathematics ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,G.2.1 ,Parameterized algorithms ,G.2.2 ,0102 computer and information sciences ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,01 natural sciences ,Combinatorics ,Computer Science::Discrete Mathematics ,Computer Science - Data Structures and Algorithms ,FOS: Mathematics ,Mathematics - Combinatorics ,Data Structures and Algorithms (cs.DS) ,0101 mathematics ,Computer Science::Data Structures and Algorithms ,Mathematics ,010102 general mathematics ,Bidimensionality ,Treewidth ,010201 computation theory & mathematics ,Kernelization ,68R10, 05C83, 05C85 ,Combinatorics (math.CO) - Abstract
Bidimensionality Theory was introduced by [E.D. Demaine, F.V. Fomin, M.Hajiaghayi, and D.M. Thilikos. Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs, J. ACM, 52 (2005), pp.866--893] as a tool to obtain sub-exponential time parameterized algorithms on H-minor-free graphs. In [E.D. Demaine and M.Hajiaghayi, Bidimensionality: new connections between FPT algorithms and PTASs, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2005, pp.590--601] this theory was extended in order to obtain polynomial time approximation schemes (PTASs) for bidimensional problems. In this work, we establish a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of linear kernels for parameterized problems. In particular, we prove that every minor (respectively contraction) bidimensional problem that satisfies a separation property and is expressible in Countable Monadic Second Order Logic (CMSO), admits a linear kernel for classes of graphs that exclude a fixed graph (respectively an apex graph) H as a minor. Our results imply that a multitude of bidimensional problems g graph classes. For most of these problems no polynomial kernels on H-minor-free graphs were known prior to our work., Comment: An an earlier version of this paper appeared in SODA 2010. That paper contained preliminary versions of some of the results of this paper
- Published
- 2020
6. A Retrospective on (Meta) Kernelization
- Author
-
Dimitrios M. Thilikos, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), ANR-16-CE40-0028,DE-MO-GRAPH,Décomposition de Modèles Graphiques(2016), and ANR-17-CE23-0010,ESIGMA,Efficacité et structure pour les applications de la fouille de graphes(2017)
- Subjects
Polynomial ,Theoretical computer science ,Reduction (recursion theory) ,Computer science ,Treewidth ,Bidimensionality ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Separability ,Parameterized complexity ,0102 computer and information sciences ,Parameterized problems ,01 natural sciences ,Algorithmics ,Kernelization Algorithms ,Preprocessor ,Protrusion Decompositions ,0101 mathematics ,Algorithmic Meta-theorems Finite Index ,Parameterized Algorithms ,010102 general mathematics ,Finite Integer Index ,Monadic Second Order Logic ,010201 computation theory & mathematics ,Kernelization - Abstract
International audience; In parameterized complexity, a {\em kernelization algorithm} can be seen as a reduction of a parameterized problem to itself, so that the produced equivalent instance has size depending exclusively on the parameter. If this size is polynomial, then then we say that the parameterized problem in question admits a polynomial kernelization algorithm. Kernelization can be seen as a formalization of the notion of preprocessingand has occupied a big part of the research on Multi-variate Algorithmics. The first algorithmic meta-theorem on kernelizationappeared in \href{https://arxiv.org/pdf/0904.0727}{\green{[{\sl H.~L. Bodlaender, F.~V. Fomin, D.~Lokshtanov, E.~Penninkx, S.~Saurabh, and D.~M. Thilikos. (Meta) kernelization. J. {ACM}, 63(5):44:1--44:69, 2016}\,]}} and unified a large family of previously known kernelization results on problems defined on topologically embeddable graphs.In this exposition we present the central results of this paper. During our presentation we pay attention to the abstractions on which the results where founded and take into account the subsequent advancements on this topic.
- Published
- 2020
7. Subexponential parameterized algorithms
- Author
-
Fedor V. Fomin, Frederic Dorn, and Dimitrios M. Thilikos
- Subjects
Catalan number ,Discrete mathematics ,Combinatorics ,General Computer Science ,Sublinear function ,Bounded function ,Parameterized complexity ,Parameterized algorithms ,Graph ,Theoretical Computer Science ,Exponential function ,Bidimensionality ,Mathematics - Abstract
We give a review of a series of techniques and results on the design of subexponential parameterized algorithms for graph problems. The design of such algorithms usually consists of two main steps: first find a branch (or tree) decomposition of the input graph whose width is bounded by a sublinear function of the parameter and, second, use this decomposition to solve the problem in time that is single exponential to this bound. The main tool for the first step is the Bidimensionality Theory. Here we present not only the potential, but also the boundaries, of this theory. For the second step, we describe recent techniques, associating the analysis of subexponential algorithms to combinatorial bounds related to Catalan numbers. As a result, we have 2^O^(^k^)@?n^O^(^1^) time algorithms for a wide variety of parameterized problems on graphs, where n is the size of the graph and k is the parameter.
- Published
- 2008
8. Bidimensionality and Parameterized Algorithms
- Author
-
Thilikos, Dimitrios M., National and Kapodistrian University of Athens (NKUA), Computer Technology Institute (CTI), Computer Technology Institute, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), and Department of Mathematics [Athens]
- Subjects
Parameterized algorithms ,Bidimensionality ,Subexponential FPT-algorithms ,Kernelization ,[INFO]Computer Science [cs] ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,Graph Minors ,Linear kenrels ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
International audience; We provide an exposition of the main results of the theory of bidimensionality in parameterized algorithm design. This theory applies to graph problems that are bidimensional in the sense that i) their solution value is not increasing when we take minors or contractions of the input graph and ii) their solution value for the (triangulated) (k × k)-grid graph grows as a quadratic function of k. Under certain additional conditions, mainly of logical and combinatorial nature, such problems admit subexponential parameterized algorithms and linear kernels when their inputs are restricted to certain topologically defined graph classes. We provide all formal definitions and concepts in order to present these results in a rigorous way and in their latest update.
- Published
- 2015
9. Parameterized Algorithms for Finding Small Independent Dominating Sets in Planar Graphs
- Author
-
Faisal N. Abu Khzam and Henning Fernau
- Subjects
Discrete mathematics ,Planar straight-line graph ,Applied Mathematics ,Parameterized algorithms ,Planar graph ,Bidimensionality ,Combinatorics ,symbols.namesake ,Dominating set ,Independent set ,symbols ,Discrete Mathematics and Combinatorics ,Maximal independent set ,Mathematics - Published
- 2006
10. Parameterized domination in circle graphs
- Author
-
George B. Mertzios, Stéphan Thomassé, Nicolas Bousquet, Christophe Paul, Daniel Gonçalves, Ignasi Sau, Golumbic, Martin Charles, Stern, Michal, Levy, Avivit, Morgenstern, Gila, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), School of Engineering and Computing Sciences, Durham University, 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-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009), Department of Computer Science [Haifa], University of Haifa [Haifa], Modèles de calcul, Complexité, Combinatoire (MC2), 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), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), 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), É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), and 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)
- Subjects
FOS: Computer and information sciences ,Discrete Mathematics (cs.DM) ,parameterized algorithms ,Constrained domination ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Parameterized complexity ,domination problems ,G.2.2 ,0102 computer and information sciences ,02 engineering and technology ,Computational Complexity (cs.CC) ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,Dynamic programming ,01 natural sciences ,Connected dominating set ,Theoretical Computer Science ,law.invention ,Combinatorics ,Parameterized algorithms ,law ,Dominating set ,Computer Science - Data Structures and Algorithms ,0202 electrical engineering, electronic engineering, information engineering ,Data Structures and Algorithms (cs.DS) ,constrained domination ,ComputingMilieux_MISCELLANEOUS ,Mathematics ,parameterized complexity ,Discrete mathematics ,dynamic programming ,05C85, 05C10 ,Intersection graph ,Bidimensionality ,Computer Science - Computational Complexity ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Circle graphs ,circle graphs ,Domination problems ,Theory of computation ,020201 artificial intelligence & image processing ,Maximal independent set ,Tree (set theory) ,Circle graph ,Computer Science - Discrete Mathematics - Abstract
A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Appl. Math., 42(1):51–63, 1993] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-complete in circle graphs. To the best of our knowledge, nothing was known about the parameterized complexity of these problems in circle graphs. In this paper we prove the following results, which contribute in this direction: Dominating Set, Independent Dominating Set, Connected Dominating Set, Total Dominating Set, and Acyclic Dominating Set are W[1]-hard in circle graphs, parameterized by the size of the solution. Whereas both Connected Dominating Set and Acyclic Dominating Set are W[1]-hard in circle graphs, it turns out that Connected Acyclic Dominating Set is polynomial-time solvable in circle graphs. If T is a given tree, deciding whether a circle graph G has a dominating set inducing a graph isomorphic to T is NP-complete when T is in the input, and FPT when parameterized by t=|V(T)|. We prove that the FPT algorithm runs in subexponential time, namely 2O(t⋅loglogtlogt)⋅nO(1), where n=|V(G)|.
- Published
- 2012
11. Fast Sub-exponential Algorithms and Compactness in Planar Graphs
- Author
-
Dimitrios M. Thilikos
- Subjects
Combinatorics ,Discrete mathematics ,symbols.namesake ,Compact space ,symbols ,Parameterized complexity ,Parameterized algorithms ,Algorithm ,Planar graph ,Mathematics ,Exponential function ,Bidimensionality ,Vertex (geometry) - Abstract
We provide a new theory, alternative to bidimensionality, of sub-exponential parameterized algorithms on planar graphs, which is based on the notion of compactness. Roughly speaking, a parameterized problem is (r, q)-compact when all the faces and vertices of its YES-instances are "r-radially dominated" by some vertex set whose size is at most q times the parameter. We prove that if a parameterized problem can be solved in cbranchwidth(G)nO(1) steps and is (r, q)-compact, then it can be solved by a crċ2.122ċ √ qċknO(1) step algorithm (where k is the parameter). Our framework is general enough to unify the analysis of almost all known sub-exponential parameterized algorithms on planar graphs and improves or matches their running times. Our results are based on an improved combinatorial bound on the branchwidth of planar graphs that bypasses the grid-minor exclusion theorem. That way, our approach encompasses new problems where bidimensionality theory do not directly provide sub-exponential parameterized algorithms.
- Published
- 2011
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.