23 results on '"Sau, Ignasi"'
Search Results
2. Faster Parameterized Algorithms for Modification Problems to Minor-Closed Classes
- Author
-
Morelle, Laure, Sau, Ignasi, Stamoulis, Giannos, and Thilikos, Dimitrios M.
- Subjects
FOS: Computer and information sciences ,F.2.2 ,G.2.2 ,Elimination distance ,05C85, 68R10, 05C75, 05C83, 05C75, 05C69 ,Obstructions ,Graph minors ,Computational Complexity (cs.CC) ,Vertex deletion ,Irrelevant vertex technique ,Computer Science - Computational Complexity ,Parameterized algorithms ,Computer Science - Data Structures and Algorithms ,FOS: Mathematics ,Mathematics - Combinatorics ,Theory of computation → Parameterized complexity and exact algorithms ,Data Structures and Algorithms (cs.DS) ,Flat Wall Theorem ,Combinatorics (math.CO) ,Graph modification problems - Abstract
Let G be a minor-closed graph class and let G be an n-vertex graph. We say that G is a k-apex of G if G contains a set S of at most k vertices such that G⧵S belongs to G. Our first result is an algorithm that decides whether G is a k-apex of G in time 2^poly(k)⋅n². This algorithm improves the previous one, given by Sau, Stamoulis, and Thilikos [ICALP 2020, TALG 2022], whose running time was 2^poly(k)⋅n³. The elimination distance of G to G, denoted by ed_G(G), is the minimum number of rounds required to reduce each connected component of G to a graph in G by removing one vertex from each connected component in each round. Bulian and Dawar [Algorithmica 2017] proved the existence of an FPT-algorithm, with parameter k, to decide whether ed_G(G) ≤ k. This algorithm is based on the computability of the minor-obstructions and its dependence on k is not explicit. We extend the techniques used in the first algorithm to decide whether ed_G(G) ≤ k in time 2^{2^{2^poly(k)}}⋅n². This is the first algorithm for this problem with an explicit parametric dependence in k. In the special case where G excludes some apex-graph as a minor, we give two alternative algorithms, one running in time 2^{2^O(k²log k)}⋅n² and one running in time 2^{poly(k)}⋅n³. As a stepping stone for these algorithms, we provide an algorithm that decides whether ed_G(G) ≤ k in time 2^O(tw⋅ k + tw log tw)⋅n, where tw is the treewidth of G. This algorithm combines the dynamic programming framework of Reidl, Rossmanith, Villaamil, and Sikdar [ICALP 2014] for the particular case where G contains only the empty graph (i.e., for treedepth) with the representative-based techniques introduced by Baste, Sau, and Thilikos [SODA 2020]. In all the algorithmic complexities above, poly is a polynomial function whose degree depends on G, while the hidden constants also depend on G. Finally, we provide explicit upper bounds on the size of the graphs in the minor-obstruction set of the class of graphs E_k(G) = {G ∣ ed_G(G) ≤ k}., LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 93:1-93:19
- Published
- 2023
- Full Text
- View/download PDF
3. Linear Kernels and Single-Exponential Algorithms via Protrusion Decompositions
- Author
-
Kim, Eun Jung, Langer, Alexander, Paul, Christophe, Reidl, Felix, Rossmanith, Peter, Sau, Ignasi, Sikdar, Somnath, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Fomin, Fedor V., editor, Freivalds, Rūsiņš, editor, Kwiatkowska, Marta, editor, and Peleg, David, editor
- Published
- 2013
- Full Text
- View/download PDF
4. Hitting and Harvesting Pumpkins
- Author
-
Joret, Gwenaël, Paul, Christophe, Sau, Ignasi, Saurabh, Saket, Thomassé, Stéphan, 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, Demetrescu, Camil, editor, and Halldórsson, Magnús M., editor
- Published
- 2011
- Full Text
- View/download PDF
5. Fast Minor Testing in Planar Graphs
- Author
-
Adler, Isolde, Dorn, Frederic, Fomin, Fedor V., Sau, Ignasi, Thilikos, Dimitrios M., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, de Berg, Mark, editor, and Meyer, Ulrich, editor
- Published
- 2010
- Full Text
- View/download PDF
6. Faster Parameterized Algorithms for Minor Containment
- Author
-
Adler, Isolde, Dorn, Frederic, Fomin, Fedor V., Sau, Ignasi, Thilikos, Dimitrios M., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Kaplan, Haim, editor
- Published
- 2010
- Full Text
- View/download PDF
7. HITTING MINORS ON BOUNDED TREEWIDTH GRAPHS. IV. AN OPTIMAL ALGORITHM.
- Author
-
BASTE, JULIEN, SAU, IGNASI, and THILIKOS, DIMITRIOS M.
- Subjects
- *
INTERSECTION graph theory , *MINORS , *DYNAMIC programming , *ALGORITHMS , *GRAPH connectivity - Abstract
For a fixed finite collection of graphs F, the F-M-DELETION problem is as follows: given an n-vertex input graph G, find the minimum number of vertices that intersect all minor models in G of the graphs in F. by Courcelle's Theorem, this problem can be solved in time fF(tw) - n°(1), where tw is the treewidth of G for some function ƒ depending on F. In a recent series of articles, we have initiated the program of optimizing asymptotically the function ff. Here we provide an algorithm showing that fF(tw) = 2° (tw.log tw) for every collection F. Prior to this work, the best known function ƒ was double- exponential in tw. In particular, our algorithm vastly extends the results of Jansen, Lokshtanov, and Saurabh [Proc. of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2014, pp. 1802-1811] for the particular case F = {K5, K3,3} and of Kociumaka and Pilipczuk [Algorithmica, 81 (2019), pp. 3655-3691] for graphs of bounded genus, and answers an open problem posed by Cygan et al. [Inform. Comput., 256 (2017), pp. 62-82]. We combine several ingredients such as the machinery of boundaried graphs in dynamic programming via representatives, the Flat Wall Theorem, bidimensionality, the irrelevant vertex technique, treewidth modulators, and protrusion replacement. Together with our previous results providing single-exponential algorithms for particular collections F [J. Baste, I. Sau, and D. M. Thilikos, Theoret. Comput. Sci., 814 (2020), pp. 135-152] and general lower bounds [J. Baste, I. Sau, and D. M. Thilikos, J. Comput. Syst. Sci., 109 (2020), pp. 56-77], our algorithm yields the following complexity dichotomy when F = {H} contains a single connected graph H, assuming the Exponential Time Hypothesis: ƒH(tw) = 2Θ(tw) if H is a contraction of the chair or the banner, and fH(tw) = 2Θ(tw-log tw) otherwise. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
8. k-apices of minor-closed graph classes. I. Bounding the obstructions.
- Author
-
Sau, Ignasi, Stamoulis, Giannos, and Thilikos, Dimitrios M.
- Subjects
- *
MINORS , *POLYNOMIALS , *MATROIDS - Abstract
Let G be a minor-closed graph class. We say that a graph G is a k-apex of G if G contains a set S of at most k vertices such that G ∖ S belongs to G. We denote by A k (G) the set of all graphs that are k -apices of G. We prove that every graph in the obstruction set of A k (G) , i.e., the minor-minimal set of graphs not belonging to A k (G) , has order at most 2 2 2 2 poly (k) , where poly is a polynomial function whose degree depends on the order of the minor-obstructions of G. This bound drops to 2 2 poly (k) when G excludes some apex graph as a minor. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
9. Compound Logics for Modification Problems
- Author
-
Fomin, Fedor V., Golovach, Petr A., Sau, Ignasi, Stamoulis, Giannos, and Thilikos, Dimitrios M.
- Subjects
FOS: Computer and information sciences ,Flat Wall theorem ,Computer Science - Logic in Computer Science ,Mathematics of computing → Graph algorithms ,G.2.2 ,Theory of computation → Logic ,Irrelevant vertex technique ,05C83, 05C85, 68R10, 68Q19, 68Q27, 68Q25 ,Computer Science - Data Structures and Algorithms ,FOS: Mathematics ,Theory of computation → Parameterized complexity and exact algorithms ,Mathematics - Combinatorics ,Data Structures and Algorithms (cs.DS) ,Graph minors ,F.2.2 ,F.4.1 ,Logic in Computer Science (cs.LO) ,Model-checking ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,Algorithmic meta-theorems ,Monadic second-order logic ,Combinatorics (math.CO) ,First-order logic ,Graph modification problems ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
We introduce a novel model-theoretic framework inspired from graph modification and based on the interplay between model theory and algorithmic graph minors. The core of our framework is a new compound logic operating with two types of sentences, expressing graph modification: the modulator sentence, defining some property of the modified part of the graph, and the target sentence, defining some property of the resulting graph. In our framework, modulator sentences are in counting monadic second-order logic (CMSOL) and have models of bounded treewidth, while target sentences express first-order logic (FOL) properties along with minor-exclusion. Our logic captures problems that are not definable in first-order logic and, moreover, may have instances of unbounded treewidth. Also, it permits the modeling of wide families of problems involving vertex/edge removals, alternative modulator measures (such as elimination distance or G-treewidth), multistage modifications, and various cut problems. Our main result is that, for this compound logic, model-checking can be done in quadratic time. All derived algorithms are constructive and this, as a byproduct, extends the constructibility horizon of the algorithmic applications of the Graph Minors theorem of Robertson and Seymour. The proposed logic can be seen as a general framework to capitalize on the potential of the irrelevant vertex technique. It gives a way to deal with problem instances of unbounded treewidth, for which Courcelle’s theorem does not apply., LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 61:1-61:21
- Published
- 2021
10. k-apices of Minor-closed Graph Classes. II. Parameterized Algorithms.
- Author
-
SAU, IGNASI, STAMOULIS, GIANNOS, and THILIKOS, DIMITRIOS M.
- Subjects
ALGORITHMS ,CHARTS, diagrams, etc. ,MINORS ,POLYNOMIALS - Abstract
Let G be a minor-closed graph class. We say that a graph G is a k-apex of G if G contains a set S of at most k vertices such that G\S belongs to G. We denote by A
k (G) the set of all graphs that are k-apices of G. In the first paper of this series, we obtained upper bounds on the size of the graphs in the minor-obstruction set of Ak (G), i.e., the minor-minimal set of graphs not belonging to Ak (G). In this article, we provide an algorithm that, given a graph G on n vertices, runs in time 2poly(k) · n3 and either returns a set S certifying that G ∈ Ak (G), or reports that G ∉ Ak (G). Here poly is a polynomial function whose degree depends on the maximum size of a minor-obstruction of G. In the special case where G excludes some apex graph as a minor, we give an alternative algorithm running in 2poly(k) · n²-time. [ABSTRACT FROM AUTHOR]- Published
- 2022
- Full Text
- View/download PDF
11. An FPT-Algorithm for Recognizing k-Apices of Minor-Closed Graph Classes
- Author
-
Sau, Ignasi, Stamoulis, Giannos, Thilikos, Dimitrios M., 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), National and Kapodistrian University of Athens (NKUA), Artur Czumaj, Anuj Dawar, Emanuela Merelli, 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
irrelevant vertex technique ,parameterized algorithms ,Theory of computation → Parameterized complexity and exact algorithms ,[MATH]Mathematics [math] ,graph minors ,Graph modification problems - Abstract
International audience; Let G be a graph class. We say that a graph G is a k-apex of G if G contains a set S of at most k vertices such that G \ S belongs to G. We prove that if G is minor-closed, then there is an algorithm that either returns a set S certifying that G is a k-apex of G or reports that such a set does not exist, in 2 poly(k) n 3 time. Here poly is a polynomial function whose degree depends on the maximum size of a minor-obstruction of G, i.e., the minor-minimal set of graphs not belonging to G. In the special case where G excludes some apex graph as a minor, we give an alternative algorithm running in 2 poly(k) n 2 time.
- Published
- 2020
12. A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth
- Author
-
Baste, Julien, Sau, Ignasi, Thilikos, Dimitrios M., École normale supérieure - Cachan, antenne de Bretagne (ENS Cachan Bretagne), École normale supérieure - Cachan (ENS Cachan), 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), Christophe Paul, and Michal Pilipczuk
- Subjects
000 Computer science, knowledge, general works ,Treewidth ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Graph minors ,0102 computer and information sciences ,02 engineering and technology ,Topological minors ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,Dynamic programming ,01 natural sciences ,Parameterized complexity ,010201 computation theory & mathematics ,Hitting minors ,Computer Science ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Exponential Time Hypothesis - Abstract
International audience; For a fixed graph H, we are interested in the parameterized complexity of the following problem, called {H}-M-Deletion, parameterized by the treewidth tw of the input graph: given an n-vertex graph G and an integer k, decide whether there exists S ⊆ V (G) with |S| ≤ k such that G\S does not contain H as a minor. In previous work [IPEC, 2017] we proved that if H is planar and connected, then the problem cannot be solved in time 2 o(tw) · n O(1) under the ETH, and can be solved in time 2 O(tw·log tw) · n O(1). In this article we manage to classify the optimal asymptotic complexity of {H}-M-Deletion when H is a connected planar graph on at most 5 vertices. Out of the 29 possibilities (discarding the trivial case H = K 1), we prove that 9 of them are solvable in time 2 Θ(tw) · n O(1) , and that the other 20 ones are solvable in time 2 Θ(tw·log tw) · n O(1). Namely, we prove that K 4 and the diamond are the only graphs on at most 4 vertices for which the problem is solvable in time 2 Θ(tw·log tw) · n O(1) , and that the chair and the banner are the only graphs on 5 vertices for which the problem is solvable in time 2 Θ(tw) · n O(1). For the version of the problem where H is forbidden as a topological minor, the case H = K 1,4 can be solved in time 2 Θ(tw) · n O(1). This exhibits, to the best of our knowledge, the first difference between the computational complexity of both problems. 2012 ACM Subject Classification Mathematics of computing → Graph algorithms, Theory of computation → Parameterized complexity and exact algorithms
- Published
- 2018
13. Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth
- Author
-
Baste , Julien, Sau , Ignasi, Thilikos , Dimitrios M., 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 ), ANR-16-CE40-0028,DEMOGRAPH,Décomposition de Modèles Graphiques ( 2016 ), 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 ANR-16-CE40-0028,DE-MO-GRAPH,Décomposition de Modèles Graphiques(2016)
- Subjects
[ MATH ] Mathematics [math] ,Parameterized complexity ,000 Computer science, knowledge, general works ,[ INFO ] Computer Science [cs] ,Treewidth ,Hitting minors ,Computer Science ,[INFO]Computer Science [cs] ,Graph minors ,Topological minors ,[MATH]Mathematics [math] ,Dynamic programming ,Exponential Time Hypothesis - Abstract
International audience; For a fixed collection of graphs F, the F-M-DELETION problem consists in, given a graph G and an integer k, decide whether there exists a subset S of V(G) of size at most k such that G-S does not contain any of the graphs in F as a minor. We are interested in the parameterized complexity of F-M-DELETION when the parameter is the treewidth of G, denoted by tw. Our objective is to determine, for a fixed F}, the smallest function f_F such that F-M-DELETION can be solved in time f_F(tw)n^{O(1)} on n-vertex graphs. Using and enhancing the machinery of boundaried graphs and small sets of representatives introduced by Bodlaender et al. [J ACM, 2016], we prove that when all the graphs in F are connected and at least one of them is planar, then f_F(w) = 2^{O(wlog w)}. When F is a singleton containing a clique, a cycle, or a path on i vertices, we prove the following asymptotically tight bounds: - f_{K_4}(w) = 2^{Theta(wlog w)}. - f_{C_i}(w) = 2^{Theta(w)} for every i4. - f_{P_i}(w) = 2^{Theta(w)} for every i5. The lower bounds hold unless the Exponential Time Hypothesis fails, and the superexponential ones are inspired by a reduction of Marcin Pilipczuk [Discrete Appl Math, 2016]. The single-exponential algorithms use, in particular, the rank-based approach introduced by Bodlaender et al. [Inform Comput, 2015]. We also consider the version of the problem where the graphs in F are forbidden as topological minors, and prove essentially the same set of results holds.
- Published
- 2017
14. HITTING MINORS ON BOUNDED TREEWIDTH GRAPHS. I. GENERAL UPPER BOUNDS.
- Author
-
BASTE, JULIEN, SAU, IGNASI, and THILIKOS, DIMITRIOS M.
- Subjects
- *
MINORS - Abstract
For a finite collection of graphs F, the F-M-DELETION problem consists in, given a graph G and an integer k, deciding whether there exists S ⊆ V (G) with |S| ≤ k such that G\S does not contain any of the graphs in F as a minor. We are interested in the parameterized complexity of F-M-Deletion when the parameter is the treewidth of G, denoted by tw. Our objective is to determine, for a fixed F, the smallest function fF such that F-M-DELETION can be solved in time fF(tw) . nO(1) on n-vertex graphs. We prove that fF(tw) = 2²O(tw.logtw) for every collection F, that fF(tw) = 2O(tw.log tw) if F contains a planar graph, and that fF(tw) = 2O(tw) if in addition the input graph G is planar or embedded in a surface. We also consider the version of the problem where the graphs in F are forbidden as topological minors, called F-TM-Deletion. We prove similar results for this problem, except that in the last two algorithms, instead of requiring F to contain a planar graph, we need it to contain a subcubic planar graph. This is the first of a series of articles on this topic. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
15. Hitting minors on bounded treewidth graphs. III. Lower bounds.
- Author
-
Baste, Julien, Sau, Ignasi, and Thilikos, Dimitrios M.
- Subjects
- *
MATROIDS , *GRAPH connectivity , *MINORS - Abstract
For a finite fixed collection of graphs F , the F -M-Deletion problem consists in, given a graph G and an integer k , decide whether there exists S ⊆ V (G) with | S | ≤ k such that G ∖ S does not contain any of the graphs in F as a minor. We provide lower bounds under the ETH on the smallest function f F such that F -M-Deletion can be solved in time f F (tw) ⋅ n O (1) on n -vertex graphs, where tw denotes the treewidth of G. We first prove that for any F containing connected graphs of size at least two, f F (tw) = 2 Ω (tw) , even if G is planar. Our main result is that if F contains a single connected graph H that is either P 5 or is not a minor of the b a n n e r , then f F (tw) = 2 Ω (tw ⋅ log tw). [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
16. Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms.
- Author
-
Baste, Julien, Sau, Ignasi, and Thilikos, Dimitrios M.
- Subjects
- *
MINORS , *MATROIDS , *ALGORITHMS , *PLANAR graphs - Abstract
For a finite collection of graphs F , the F -M-Deletion (resp. F -TM-Deletion) problem consists in, given a graph G and an integer k , decide whether there exists S ⊆ V (G) with | S | ≤ k such that G ∖ S does not contain any of the graphs in F as a minor (resp. topological minor). We are interested in the parameterized complexity of both problems when the parameter is the treewidth of G , denoted by tw , and specifically in the cases where F contains a single connected planar graph H. We present algorithms running in time 2 O (tw) ⋅ n O (1) , called single-exponential , when H is either P 3 , P 4 , C 4 , the paw , the chair , and the banner for both { H } -M-Deletion and { H } -TM-Deletion , and when H = K 1 , i , with i ≥ 1 , for { H } -TM-Deletion. Some of these algorithms use the rank-based approach introduced by Bodlaender et al. (2015) [7]. This is the second of a series of articles on this topic, and the results given here together with other ones allow us, in particular, to provide a tight dichotomy on the complexity of { H } -M-Deletion in terms of H. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
17. EXPLICIT LINEAR KERNELS VIA DYNAMIC PROGRAMMING.
- Author
-
GARNERO, VALENTIN, PAUL, CHRISTOPHE, SAU, IGNASI, and THILIKOS, DIMITRIOS M.
- Subjects
KERNEL (Mathematics) ,DYNAMIC programming ,GENERALIZATION ,POLYNOMIALS ,SPARSE graphs - Abstract
Several algorithmic meta-theorems on kernelization have appeared in the last years, starting with the result of Bodlaender et al. [(Meta) kernelization, in Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, 2009, pp. 629– 638] on graphs of bounded genus, then generalized by Fomin et al. [Bidimensionality and kernels, in Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadephia, 2010, pp. 503–510] to graphs excluding a fixed minor, and by Kim et al. [Linear kernels and single-exponential algorithms via protrusion decompositions, in Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Comput. Sci., 7965 (2013), pp. 613–624] to graphs excluding a fixed topological minor. Typically, these results guarantee the existence of linear or polynomial kernels on sparse graph classes for problems satisfying some generic conditions, but, mainly due to their generality, it is not clear how to derive from them constructive kernels with explicit constants. In this paper, we make a step toward a fully constructive meta-kernelization theory on sparse graphs. Our approach is based on a more explicit protrusion replacement machinery that, instead of expressibility in counting monadic second order logic, uses dynamic programming, which allows us to find an explicit upper bound on the size of the derived kernels. We demonstrate the usefulness of our techniques by providing the first explicit linear kernels for r-Dominating Set and r-Scattered Set on apex-minor-free graphs, and for PLANAR-F-DELETION on graphs excluding a fixed (topological) minor in the case where all the graphs in F are connected. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
18. HITTING AND HARVESTING PUMPKINS.
- Author
-
JORET, GWENAËL, PAUL, CHRISTOPHE, SAU, IGNASI, SAURABH, SAKET, and THOMASSÉ, STEPHAN
- Subjects
PARAMETERIZED family ,MATHEMATICAL functions ,PROBABILITY theory ,APPROXIMATION algorithms ,ITERATIVE methods (Mathematics) ,GRAPH theory - Abstract
The c-pumpkin is the graph with two vertices linked by c ≥ 1 parallel edges. A c-pumpkin-model in a graph G is a pair {A, B} of disjoint subsets of vertices of G, each inducing a connected subgraph of G, such that there are at least c edges in G between A and B. We focus on hitting and packing c-pumpkin-models in a given graph in the realm of approximation algorithms and parameterized algorithms. We give a fixed-parameter tractable (FPT) algorithm running in time 2
...(κ) (n...(1) deciding, for any fixed c ≥ 1, whether all c-pumpkin-models can be hit by at most k vertices. This generalizes known single-exponential FPT algorithms for Vertex Cover and Feedback Vertex SET, which correspond to the cases c = 1, 2 respectively. Finally, we present an ...(log n)-approximation algorithm for both the problems of hitting all c-pumpkin-models with a smallest number of vertices and packing a maximum number of vertex-disjoint c-pumpkin-models. [ABSTRACT FROM AUTHOR]- Published
- 2014
- Full Text
- View/download PDF
19. Fast Minor Testing in Planar Graphs.
- Author
-
Adler, Isolde, Dorn, Frederic, Fomin, Fedor, Sau, Ignasi, and Thilikos, Dimitrios
- Subjects
PLANAR graphs ,GRAPH theory ,COMPUTER algorithms ,DYNAMIC programming ,INFORMATION science ,COMPUTER science - Abstract
Minor Containment is a fundamental problem in Algorithmic Graph Theory used as a subroutine in numerous graph algorithms. A model of a graph H in a graph G is a set of disjoint connected subgraphs of G indexed by the vertices of H, such that if { u, v} is an edge of H, then there is an edge of G between components C and C. A graph H is a minor of G if G contains a model of H as a subgraph. We give an algorithm that, given a planar n-vertex graph G and an h-vertex graph H, either finds in time $\mathcal{O}(2^{\mathcal{O}(h)} \cdot n +n^{2}\cdot\log n)$ a model of H in G, or correctly concludes that G does not contain H as a minor. Our algorithm is the first single-exponential algorithm for this problem and improves all previous minor testing algorithms in planar graphs. Our technique is based on a novel approach called partially embedded dynamic programming. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
20. Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs.
- Author
-
Sau, Ignasi and Thilikos, Dimitrios M.
- Subjects
EXPONENTIAL functions ,GRAPH theory ,DIMENSIONAL analysis ,MATHEMATICAL decomposition ,COMPUTATIONAL complexity ,COMPUTER algorithms ,CATALAN numbers - Abstract
Abstract: We present subexponential parameterized algorithms on planar graphs for a family of problems of the following shape: given a graph, find a connected (induced) subgraph with bounded maximum degree and with maximum number of edges (or vertices). These problems are natural generalisations of the Longest Path problem. Our approach uses bidimensionality theory combined with novel dynamic programming techniques over branch decompositions of the input graph. These techniques can be applied to a more general family of problems that deal with finding connected subgraphs under certain degree constraints. [Copyright &y& Elsevier]
- Published
- 2010
- Full Text
- View/download PDF
21. Subexponential Parameterized Algorithms for Bounded-Degree Connected Subgraph Problems on Planar Graphs.
- Author
-
Sau, Ignasi and Thilikos, Dimitrios M.
- Subjects
GRAPH theory ,COMPUTATIONAL complexity ,COMPUTER algorithms ,SET theory ,GEOMETRIC connections ,PARAMETER estimation ,MAXIMA & minima ,EXPONENTIAL functions - Abstract
Abstract: We present subexponential parameterized algorithms on planar graphs for a family of problems that consist in, given a graph G, finding a connected (induced) subgraph H with bounded maximum degree, while maximising the number of edges (or vertices) of H. These problems are natural generalisations of Longest Path. Our approach uses bidimensionality theory combined with novel dynamic programming techniques over branch decompositions of the input graph. These techniques can be applied to a more general family of problems that deal with finding connected subgraphs under certain degree constraints. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
22. Faster parameterized algorithms for minor containment
- Author
-
Adler, Isolde, Dorn, Frederic, Fomin, Fedor V., Sau, Ignasi, and Thilikos, Dimitrios M.
- Subjects
- *
GRAPH theory , *COMPUTER algorithms , *COMPUTER programming , *POLYNOMIALS , *COMPUTER science , *COMBINATORICS - Abstract
Abstract: The -Minor containment problem asks whether a graph contains some fixed graph as a minor, that is, whether can be obtained by some subgraph of after contracting edges. The derivation of a polynomial-time algorithm for -Minor containment is one of the most important and technical parts of the Graph Minor Theory of Robertson and Seymour and it is a cornerstone for most of the algorithmic applications of this theory. -Minor containment for graphs of bounded branchwidth is a basic ingredient of this algorithm. The currently fastest solution to this problem, based on the ideas introduced by Robertson and Seymour, was given by Hicks in [I.V. Hicks, Branch decompositions and minor containment, Networks 43 (1) (2004) 1–9], providing an algorithm that in time decides if a graph with edges and branchwidth , contains a fixed graph on vertices as a minor. In this work we improve the dependence on of Hicks’ result by showing that checking if is a minor of can be done in time . We set up an approach based on a combinatorial object called rooted packing, which captures the properties of the subgraphs of that we seek in our dynamic programming algorithm. This formulation with rooted packings allows us to speed up the algorithm when is embedded in a fixed surface, obtaining the first algorithm for minor containment testing with single-exponential dependence on branchwidth. Namely, it runs in time , with . Finally, we show that slight modifications of our algorithm permit to solve some related problems within the same time bounds, like induced minor or contraction containment. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF
23. Faster parameterized algorithms for minor containment
- Author
-
Fedor V. Fomin, Frederic Dorn, Ignasi Sau, Isolde Adler, Dimitrios M. Thilikos, Sau, Ignasi, Department of Informatics [Bergen] (UiB), University of Bergen (UiB), 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), Department of Informatics and Telecomunications [Kapodistrian Univ] (DI NKUA), and National and Kapodistrian University of Athens (NKUA)
- Subjects
Speedup ,General Computer Science ,Branch-decomposition ,Minor (linear algebra) ,0211 other engineering and technologies ,Parameterized complexity ,Graphs on surfaces ,Parameterized algorithms ,0102 computer and information sciences ,02 engineering and technology ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,Dynamic programming ,01 natural sciences ,Theoretical Computer Science ,Combinatorics ,Branchwidth ,0103 physical sciences ,Graph minor ,Graph minor containment ,010306 general physics ,Contraction (operator theory) ,Complement graph ,Forbidden graph characterization ,Mathematics ,Discrete mathematics ,Containment (computer programming) ,021103 operations research ,Graph minors ,16. Peace & justice ,Graph ,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM] ,010201 computation theory & mathematics ,Bounded function ,Computer Science(all) - Abstract
International audience; The theory of Graph Minors by Robertson and Seymour is one of the deepest and significant theories in modern Combinatorics. This theory has also a strong impact on the recent development of Algorithms, and several areas, like Parameterized Complexity, have roots in Graph Minors. Until very recently it was a common belief that Graph Minors Theory is mainly of theoretical importance. However, it appears that many deep results from Robertson and Seymour's theory can be also used in the design of practical algorithms. Minor containment testing is one of algorithmically most important and technical parts of the theory, and minor containment in graphs of bounded branchwidth is a basic ingredient of this algorithm. In order to implement minor containment testing on graphs of bounded branchwidth, Hicks [NETWORKS 04] described an algorithm, that in time $\mathcal{O}(3^{k^2}\cdot (h+k-1)!\cdot m)$ decides if a graph G with m edges and branchwidth k, contains a fixed graph H on h vertices as a minor. That algorithm follows the ideas introduced by Robertson and Seymour in [J'CTSB 95]. In this work we improve the dependence on k of Hicks' result by showing that checking if H is a minor of G can be done in time $\mathcal{O}(2^{(2k +1 )\cdot \log k} \cdot h^{2k} \cdot 2^{2h^2} \cdot m)$. Our approach is based on a combinatorial object called rooted packing, which captures the properties of the potential models of subgraphs of H that we seek in our dynamic programming algorithm. This formulation with rooted packings allows us to speed up the algorithm when G is embedded in a fixed surface, obtaining the first single-exponential algorithm for minor containment testing. Namely, it runs in time $2^{\mathcal{O}(k)} \cdot h^{2k} \cdot 2^{\mathcal{O}(h)} \cdot n$, with n=|V(G)|. Finally, we show that slight modifications of our algorithm permit to solve some related problems within the same time bounds, like induced minor or contraction minor containment.
- Published
- 2011
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.