Author: "Thilikos, Dimitrios M." / Publisher: hal ccsd - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"Thilikos, Dimitrios M."' showing total 43 results

Start Over Author "Thilikos, Dimitrios M." Publisher hal ccsd

43 results on '"Thilikos, Dimitrios M."'

1. 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
Full Text: View/download PDF

2. Lean Tree-Cut Decompositions: Obstructions and Algorithms

Author: Giannopoulou, Archontia, Kwon, O-joung, Raymond, Jean-Florent, Thilikos, Dimitrios M., Department of Informatics and Telecomunications [Kapodistrian Univ] (DI NKUA), National and Kapodistrian University of Athens (NKUA), Computer and Automation Research Institute [Budapest] (MTA SZTAKI ), Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), University of Warsaw (UW), 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), Rolf Niedermeier, Christophe Paul, and Wagner, Michael
Subjects: 000 Computer science, knowledge, general works, Immersions, 010102 general mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Obstructions, 0102 computer and information sciences, Lean decompositions, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 16. Peace & justice, 01 natural sciences, Parameterized algorithms, 010201 computation theory & mathematics, Tree-cut width, Computer Science, 0101 mathematics
Abstract: International audience; The notion of tree-cut width has been introduced by Wollan in [The structure of graphs not admitting a fixed immersion, Journal of Combinatorial Theory, Series B, 110:47-66, 2015]. It is defined via tree-cut decompositions, which are tree-like decompositions that highlight small (edge) cuts in a graph. In that sense, tree-cut decompositions can be seen as an edge-version of tree-decompositions and have algorithmic applications on problems that remain intractable on graphs of bounded treewidth. In this paper, we prove that every graph admits an optimal tree-cut decomposition that satisfies a certain Menger-like condition similar to that of the lean tree decompositions of Thomas [A Menger-like property of tree-width: The finite case, Journal of Combinatorial Theory, Series B, 48(1):67-76, 1990]. This allows us to give, for every k ∈ N, an upper-bound on the number immersion-minimal graphs of tree-cut width k. Our results imply the constructive existence of a linear FPT-algorithm for tree-cut width.
Published: 2019
Full Text: View/download PDF

3. Data-compression for Parametrized Counting Problems on Sparse graphs

Author: Kim, Eun Jung, Serna, Maria, Thilikos, Dimitrios M., 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), Llenguatges i Sistemes Informàtics (LSI), Universitat Politècnica de Catalunya [Barcelona] (UPC), 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), Wen-Lian Hsu, Der-Tsai Lee, Chung-Shou Liao, ANR-17-CE23-0010,ESIGMA,Efficacité et structure pour les applications de la fouille de graphes(2017), and ANR-16-CE40-0028,DE-MO-GRAPH,Décomposition de Modèles Graphiques(2016)
Subjects: FOS: Computer and information sciences, 000 Computer science, knowledge, general works, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], G.2.2, F.2.2, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Parameterized counting, Computer Science, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Compactor, 68R10, 68W01, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], Combinatorics (math.CO), Protrusion decomposition
Abstract: We study the concept of \emph{compactor}, which may be seen as a counting-analogue of kernelization in counting parameterized complexity. For a function $F:\Sigma^*\to \Bbb{N}$ and a parameterization $\kappa: \Sigma^*\to \Bbb{N}$, a compactor $({\sf P},{\sf M})$ consists of a polynomial-time computable function ${\sf P}$, called \emph{condenser}, and a computable function ${\sf M}$, called \emph{extractor}, such that $F={\sf M}\circ {\sf P}$, and the condensing ${\sf P}(x)$ of $x$ has length at most $s(\kappa(x))$, for any input $x\in \Sigma^*.$ If $s$ is a polynomial function, then the compactor is said to be of polynomial-size. Although the study on counting-analogue of kernelization is not unprecedented, it has received little attention so far. We study a family of vertex-certified counting problems on graphs that are MSOL-expressible; that is, for an MSOL-formula $\phi$ with one free set variable to be interpreted as a vertex subset, we want to count all $A\subseteq V(G)$ where $|A|=k$ and $(G,A)\models \phi.$ In this paper, we prove that every vertex-certified counting problems on graphs that is \emph{MSOL-expressible} and \emph{treewidth modulable}, when parameterized by $k$, admits a polynomial-size compactor on $H$-topological-minor-free graphs with condensing time $O(k^2n^2)$ and decoding time $2^{O(k)}.$ This implies the existence of an {\sf FPT}-algorithm of running time $O(n^2k^2)+2^{O(k)}.$ All aforementioned complexities are under the Uniform Cost Measure (UCM) model where numbers can be stored in constant space and arithmetic operations can be done in constant time., Comment: An extended abstract of this paper was accepted to ISAAC 2018
Published: 2018
Full Text: View/download PDF

4. 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
Full Text: View/download PDF

5. Alternative proofs of the asymmetric Lovász local lemma and Shearer's lemma

Author: Giotis, Ioannis, Kirousis, Lefteris, Livieratos, John, Psaromiligkos, Kostas, Thilikos, Dimitrios M., Department of Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), 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-17-CE23-0010,ESIGMA,Efficacité et structure pour les applications de la fouille de graphes(2017)
Subjects: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract: International audience; We provide new algorithmic proofs for two forms of the Lovász Local Lemma: the Asymmetric version and Shearer's Lemma. Our proofs directly compute an upper bound for the probability that the corresponding Moser-type algorithms last for at least n steps. These algorithms iteratively sample the probability space; when and if they halt, a correct sampling, i.e. one where all undesirable events are avoided, is obtained. Our computation shows that this probability is exponentially small in n. In contrast most extant proofs for the Lovász Local Lemma and its variants use counting arguments that give estimates of only the expectation that the algorithm lasts for at least n steps. For the asymmetric version, we use the results of Bender and Richmond on the multivariable Lagrange inversion. For Shearer's Lemma, we follow the work of Kolipaka and Szegedy, combined with Gelfand's formula for the spectral radius of a matrix.
Published: 2018

6. An $O(\log \mathrm {OPT})$-Approximation for Covering and Packing Minor Models of $\theta _r$

Author: Chatzidimitriou, Dimitris, Raymond, Jean-Florent, Sau Valls, Ignasi, Thilikos, Dimitrios M., Department of Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), 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), Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), University of Warsaw (UW), and This research have been supported by the Warsaw Centre of Mathematics and Computer Science (Jean-Florent Raymond), by the (Polish) National Science Centre Grant PRELUDIUM 2013/11/N/ST6/02706 (Jean-Florent Raymond), and by the E.U. (European Social Fund—ESF) and Greek national funds through the Operational Program 'Education and Lifelong Learning' of the National Strategic Reference Framework (NSRF)—Research Funding Program: 'Thales. Investing in knowledge society through the European Social Fund' (Dimitris Chatzidimitriou and Dimitrios M. Thilikos).
Subjects: Packings in graphs, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Erdős–Pósa property, Protrusion decomposition, Minor-models of θ, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Coverings in graph, ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory/G.2.2.0: Graph algorithms, Approximation algorithm, ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2018
Full Text: View/download PDF

7. Contraction-Bidimensionality of Geometric Intersection Graphs

Author: Baste, Julien, 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), Department of Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), and ANR-16-CE40-0028,DE-MO-GRAPH,Décomposition de Modèles Graphiques(2016)
Subjects: 000 Computer science, knowledge, general works, Geometric intersection graphs, 010201 computation theory & mathematics, Bidimensionality, Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, Grid exlusion theorem, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, String Graphs
Abstract: International audience; 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 general family of graph classes that satisfy the SQGC property and includes bounded-degree string graphs. This considerably extends the applicability of bidimensionality theory for several intersection graph classes of 2-dimensional geometrical objects.
Published: 2017
Full Text: View/download PDF

8. 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
Full Text: View/download PDF

9. Report on GRASTA 2017, 6th Workshop on GRAph Searching, Theory and Applications, Anogia, Crete, Greece, April 10 – April 13, 2017

Author: Angelopoulos, Spyros, Fraigniaud, Pierre, Fomin, Fedor V., Nisse, Nicolas, Thilikos, Dimitrios M., Recherche Opérationnelle (RO), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Department of Informatics, University of Bergen (UIB), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Nice Sophia Antipolis (... - 2019) (UNS), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS), 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), Department of Mathematics [Athens], National and Kapodistrian University of Athens = University of Athens (NKUA | UoA), LIP6, CNRS, Universit ́e Pierre et Marie Curie Paris, France, Department of Informatics, University of Bergen, Bergen, Norway, CNRS and Université Paris Diderot, France, Inria & Université Nice Sophia Antipolis, CNRS, I3S, Sophia Antipolis, France, AlGCo project team, CNRS, LIRMM, Montpellier, France, Department of Informatics [Bergen] (UiB), University of Bergen (UiB), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), 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), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract: Graph searching involves a team of mobile agents (called searchers or pursuers or cops) that aims at capturing a set of escaping agents (called evaders or fugitives or robbers) that hide in a network modeled by a graph. There are many variants of graph searching studied in the literature, often referred to as a pursuit-evasion game or cops and robbers game. These variants are either application driven, i.e. motivated by problems in practice, or are inspired by foundational issues at the intersection of Computer Science, Discrete Mathematics, and Artificial Inteligence. As a result, many researchers from different areas of Mathematics, Computer Science and Operations Research are interested in problems related to graph searching.GRASTA 2017 is the main forum on graph searching and was held at the Anogia Academic Village, Anogia, Crete, Greece.It gathered 39 researchers from diverse areas of Theoretical Computer Science and Discrete Mathematics related to Graph Searching Games and their Applications both from the applied and the theoretical point of view. The scientific program of the workshop consisted of 18 regular talks, and an open problem session.
Published: 2017

10. Editing to a planar graph of given degrees

Author: Dabrowski, Konrad Kazimierz, Golovach, Petr A., van 't Hof, Pim, Paulusma, Daniël, Thilikos, Dimitrios M., Beklemishev, Lev D., Musatov, Daniil V., School of Engineering and Computing Sciences, Durham University, Department of Informatics [Bergen] (UiB), University of Bergen (UiB), Department of Computer Science, Department of Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), 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), Discrete Mathematics and Mathematical Programming, Beklemishev, L.D., and Musatov, D.V.
Subjects: FOS: Computer and information sciences, Computer Networks and Communications, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Parameterized complexity, 0102 computer and information sciences, 02 engineering and technology, Computational Complexity (cs.CC), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, symbols.namesake, Computer Science - Data Structures and Algorithms, 0202 electrical engineering, electronic engineering, information engineering, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], Degree function, Mathematics, Discrete mathematics, Applied Mathematics, Planar graph, Vertex (geometry), Computer Science - Computational Complexity, Computational Theory and Mathematics, 010201 computation theory & mathematics, symbols, 020201 artificial intelligence & image processing
Abstract: We consider the following graph modification problem. Let the input consist of a graph $G=(V,E)$, a weight function $w:V\cup E\rightarrow \mathbb {N}$, a cost function $c:V\cup E\rightarrow \mathbb {N}$ and a degree function $\delta :V\rightarrow \mathbb {N}_0$, together with three integers $k_v$, $k_e$ and C. The question is whether we can delete a set of vertices of total weight at most $k_v$ and a set of edges of total weight at most $k_e$ so that the total cost of the deleted elements is at most C and every non-deleted vertex v has degree $\delta (v)$ in the resulting graph $G'$. We also consider the variant in which $G'$ must be connected. Both problems are known to be $\mathsf{NP}$-complete and $\mathsf{W}[1]$-hard when parameterized by $k_v+k_e$. We prove that, when restricted to planar graphs, they stay $\mathsf{NP}$-complete but have polynomial kernels when parameterized by $k_v+k_e$.
Published: 2017
Full Text: View/download PDF

11. Low Polynomial Exclusion of Planar Graph Patterns

Author: Raymond, Jean-Florent, 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), Department of Mathematics [Athens], and National and Kapodistrian University of Athens (NKUA)
Subjects: FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Treewidth, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Combinatorics, Graph minors, Combinatorics (math.CO), G.2.2, 05C83, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], ComputingMilieux_MISCELLANEOUS, Computer Science - Discrete Mathematics
Abstract: The celebrated grid exclusion theorem states that for every $h$-vertex planar graph $H$, there is a constant $c_{h}$ such that if a graph $G$ does not contain $H$ as a minor then $G$ has treewidth at most $c_{h}$. We are looking for patterns of $H$ where this bound can become a low degree polynomial. We provide such bounds for the following parameterized graphs: the wheel ($c_{h}=O(h)$), the double wheel ($c_{h}=O(h^2\cdot \log^{2} h)$), any graph of pathwidth at most 2 ($c_{h}=O(h^{2})$), and the yurt graph ($c_{h}=O(h^{4})$).
Published: 2017
Full Text: View/download PDF

12. (Meta) Kernelization

Author: Bodlaender, Hans L., Fomin, Fedor V., Lokshtanov, Daniel, Penninkx, Eelko, Saurabh, Saket, Thilikos, Dimitrios M., Sub Algorithms and Complexity, Sub Algorithmic Systems begr. 01-01-2013, Algorithmic Systems, Department of Computer Science [Utrecht], Utrecht University [Utrecht], Department of Informatics [Bergen] (UiB), University of Bergen (UiB), Institute of Mathematical Sciences [Chennai] (IMSc), Department of Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), 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 Algorithms, Geometry and Applications
Subjects: Polynomial, Treewidth, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Parameterized complexity, Embedded graphs, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Combinatorics, symbols.namesake, Artificial Intelligence, Polynomial kernel, Genus (mathematics), 0101 mathematics, Graph algorithms, Finite, Preprocessing, Mathematics, Discrete mathematics, Integer index, Protrusions, Computer Science::Information Retrieval, 010102 general mathematics, finite integer index, 16. Peace & justice, Planar graph, 010201 computation theory & mathematics, Hardware and Architecture, Control and Systems Engineering, Kernelization, Bounded function, counting monadic second order logic, symbols, Monadic second-order logic, Software, Information Systems
Abstract: In a parameterized problem, every instance I comes with a positive integer k . The problem is said to admit a polynomial kernel if, in polynomial time, one can reduce the size of the instance I to a polynomial in k while preserving the answer. In this work, we give two meta-theorems on kernelization. The first theorem says that all problems expressible in counting monadic second-order logic and satisfying a coverability property admit a polynomial kernel on graphs of bounded genus. Our second result is that all problems that have finite integer index and satisfy a weaker coverability property admit a linear kernel on graphs of bounded genus. These theorems unify and extend all previously known kernelization results for planar graph problems.
Published: 2016
Full Text: View/download PDF

13. Forewords: Special issue on Theory and Applications of Graph Searching Problems

Author: Fomin, Fedor V., Fraigniaud, Pierre, Nisse, Nicolas, Thilikos, Dimitrios M., Department of Informatics [Bergen] (UiB), University of Bergen (UiB), Networks, Graphs and Algorithms (GANG), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Department of Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), 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, University of Bergen (UIB), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Nice Sophia Antipolis (... - 2019) (UNS), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS), National and Kapodistrian University of Athens = University of Athens (NKUA | UoA), and Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)
Subjects: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2016
Full Text: View/download PDF

14. Bidimensionality

Author: Fomin, Fedor V., Demaine, Erik D., Hajiaghayi, Mohammed Taghi, Thilikos, Dimitrios M., Department of Informatics [Bergen] (UiB), University of Bergen (UiB), Computer Science and Artificial Intelligence Laboratory [Cambridge] (CSAIL), Massachusetts Institute of Technology (MIT), University of Maryland [College Park], University of Maryland System, Department of Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), 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: 010201 computation theory & mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Subexponential algorithms, 01 natural sciences, ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2016
Full Text: View/download PDF

15. Foreword: Sixth Workshop on Graph Classes, Optimization, and Width Parameters, Santorini, Greece, October 2013

Author: Heggernes, Pinar, Proskurowski, Andrzej, Thilikos, Dimitrios M., Department of Informatics [Bergen] (UiB), University of Bergen (UiB), Computer Science Department [Oregon], University of Oregon [Eugene], 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 Mathematics [Athens], and National and Kapodistrian University of Athens (NKUA)
Subjects: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2016
Full Text: View/download PDF

16. An $O(log OPT)$-Approximation for Covering/Packing Minor Models of $θ _r$

Author: Chatzidimitriou, Dimitris, Raymond, Jean-Florent, Sau Valls, Ignasi, Thilikos, Dimitrios M., Department of Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), 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), Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), University of Warsaw (UW), and The second author has been partially supported by the Warsaw Centre of Mathematics and Computer Science and by the (Polish) National Science Centre grant PRELUDIUM 2013/11/N/ST6/02706. The first and the last authors were co-financed by the E.U. (European Social Fund - ESF) and Greek national funds through the Operational Program ``Education and Lifelong Learning' of the National Strategic Reference Framework (NSRF) - Research Funding Program: ``Thales. Investing in knowledge society through the European Social Fund'.
Subjects: Packings in graphs, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], 2000MSC: 05C70, Erdős-Pósa property, Protrusion decomposition, Approximation algorithms, Coverings in graphs
Abstract: International audience; Given two graphs $G$ and $H$, we define $\mathrm{vcover}_{H}(G)$ (resp. $\mathrm{ecover}_{H}(G)$) as the minimum number of vertices (resp. edges) whose removal from $G$ produces a graph without any minor isomorphic to ${H}$. Also $\mathrm{vpack}_{H}(G)$ (resp. $\mathrm{epack}_{H}(G)$) is the maximum number of vertex- (resp. edge-) disjoint subgraphs of $G$ that contain a minor isomorphic to $H$. We denote by $\theta_{r}$ the graph with two vertices and $r$ parallel edges between them. When $H=\theta_{r}$, the parameters $\mathrm{vcover}_{H}$, $\mathrm{ecover}_{H}$, $\mathrm{vpack}_{H}$, and $\mathrm{epack}_{H}$ are {\sf NP}-hard to compute (for sufficiently big values of $r$). Drawing upon combinatorial results in \cite{ChatzidimitriouRST15mino}, we give an algorithmic proof that if $\mathrm{vpack}_{{\theta_{r}}}(G)\leq k$, then $\mathrm{vcover}_{\theta_{r}}(G) = O(k\log k)$, and similarly for $\mathrm{epack}_{\theta_{r}}$ and $\mathrm{ecover}_{\theta_{r}}$. In other words, the class of graphs containing ${\theta_{r}}$ as a minor has the vertex/edge Erdős-Pósa property, for every positive integer $r$. Using the algorithmic machinery of our proofs we introduce a unified approach for the design of an $O(\log {\rm OPT})$-approximation algorithm for $\mathrm{vpack}_{\theta_r}$, $\mathrm{vcover}_{\theta_r}$, $\mathrm{epack}_{\theta_r}$, and $\mathrm{ecover}_{\theta_r}$ that runs in $O(n\cdot \log(n)\cdot m)$ steps.Also, we derive several new Erdős-Pósa-type results from the techniques that we introduce.
Published: 2015
Full Text: View/download PDF

17. 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
Full Text: View/download PDF

18. Algorithms and Combinatorics on the Erdős–Pósa property

Author: 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), Department of Mathematics [Athens], and National and Kapodistrian University of Athens (NKUA)
Subjects: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], ComputingMilieux_MISCELLANEOUS
Abstract: International audience; Some (basic and necessary) definitions
Published: 2015

19. A Fixed Parameter Algorithm for Plane Subgraph Completion

Author: Chatzidimitriou, Dimitris, Giannopoulou, Archontia C., Requilé, Clément, Thilikos, Dimitrios M., Zoros, Dimitris, Department of Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), University of Warsaw (UW), Universitat Politècnica de Catalunya [Barcelona] (UPC), 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: TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; The Plane Subgraph Completion problem asks, given a (possibly disconnected) plane graph Γ and a connected plane graph ∆, whether it is possible to add edges in Γ such that the resulting graph remains planar and contains some subgraph that is topologically isomorphic to ∆. We give an algorithm that solves this problem in 2 O(k log k) · n 2 steps where k and n are the number of vertices of ∆ and Γ respectively.
Published: 2015

20. An alternative proof for the constructive Asymmetric Lovász Local Lemma

Author: Giotis, Ioannis, Kirousis, Lefteris, Psaromiligkos, Kostas I., Thilikos, Dimitrios M., Computer Technology Institute and Press 'Diophantus', University of Patras [Greece], Department of Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), 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 LIRMM
Subjects: Mathematics::Combinatorics, Computer Science::Discrete Mathematics, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Computer Science::Data Structures and Algorithms
Abstract: International audience; We provide an alternative constructive proof of the Asymmetric Lovász Local Lemma. Our proof uses the classic algorithmic framework of Moser and the analysis introduced by Giotis, Kirousis, Psaromiligkos, and Thilikos in " On the algorithmic Lovász Local Lemma and acyclic edge coloring " , combined with the work of Bender and Richmond on the multivariable Lagrange Inversion formula.
Published: 2015

21. CORECLUSTER: A Degeneracy Based Graph Clustering Framework

Author: Giatsidis, Christos, Malliaros, Fragkiskos, Thilikos, Dimitrios M., Vazirgiannis, Michalis, Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), 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 Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), and Athens University of Economics and Business (AUEB)
Subjects: General Medicine, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract: Graph clustering or community detection constitutes an important task forinvestigating the internal structure of graphs, with a plethora of applications in several domains. Traditional tools for graph clustering, such asspectral methods, typically suffer from high time and space complexity. In thisarticle, we present CoreCluster, an efficient graph clusteringframework based on the concept of graph degeneracy, that can be used along withany known graph clustering algorithm. Our approach capitalizes on processing thegraph in a hierarchical manner provided by its core expansion sequence, anordered partition of the graph into different levels according to the k-coredecomposition. Such a partition provides a way to process the graph inan incremental manner that preserves its clustering structure, whilemaking the execution of the chosen clustering algorithm much faster due to thesmaller size of the graph's partitions onto which the algorithm operates.
Published: 2014

22. Covering and packing pumpkin models

Author: Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau, Thilikos, Dimitrios M., Department of Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), University of Warsaw (UW), 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: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract: International audience; Let θr (the r-pumpkin) be the multi-graph containing two vertices and r parallel edges between them. We say that a graph is a a θr-model if it can be transformed into θr after a (possibly empty) sequence of contractions. We prove that there is a function g : N → N such that, for every two positive integers k and q, if G is a Kq-minor-free graph, then either G contains a set of k vertex-disjoint subgraphs (a θr-model-vertex-packing) each isomorphic to a θr-model or a set of g(r)·log q ·k vertices (a θr-model-vertex-cover) meeting all subgraphs of G that are isomorphic to a θr-model. Our results imply a O(log OP T)-approximation for the maximum (minimum) size of a θr-model packing (θr-model covering) of a graph G.
Published: 2014

23. Geometric Extensions of Cutwidth in any Dimension

Author: Karavelas, Menelaos, Zoros, Dimitris, Maniatis, Spyridon, Thilikos, Dimitrios M., Department of Applied Mathematics [Heraklion], University of Crete [Heraklion] (UOC), Department of Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), 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: Computer Science::Discrete Mathematics, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Computer Science::Data Structures and Algorithms
Abstract: International audience; We define a multi-dimensional geometric extension of cutwidth. A graph has d-cutwidth at most k if it can be embedded in the d-dimensional euclidean space so that no hyperplane can intersect more than k of its edges. We prove a series of combinatorial results on d-cutwidth which imply that for every d and k, there is a linear time algorithm checking whether the d-cutwidth of a graph G is at most k.
Published: 2014

24. Structure of W_4 -immersion free graphs

Author: Belmonte, Rémy, Giannopoulou, Archontia C., Lokshtanov, Daniel, Thilikos, Dimitrios M., University of Bergen (UiB), Department of Computer Science, Durham University, Department of Informatics [Bergen] (UiB), Department of Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), 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: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract: International audience; We study the structure of graphs that do not contain the wheel on 5 vertices W 4 as an immersion, and show that these graphs can be constructed via 1, 2, and 3-edge-sums from subcubic graphs and graphs of bounded treewidth.
Published: 2014

25. An edge variant of the Erdős-Pósa property

Author: Jean-Florent Raymond, Ignasi Sau, 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), Department of Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), and Thilikos, Dimitrios
Subjects: [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract: International audience; For every r∈N, we denote by θr the multigraph with two vertices and r parallel edges. Given a graph G, we say that a subgraph H of G is a model of θr in G if H contains θr as a contraction. We prove that the following edge variant of the Erd{\H o}s-P{\'o}sa property holds for every r≥2: if G is a graph and k is a positive integer, then either G contains a packing of k mutually edge-disjoint models of θr, or it contains a set S of fr(k) edges meeting all models of θr in G, for both fr(k)=O(k2r3polylog kr) and fr(k)=O(k4r2polylog kr).
Published: 2014

26. 6th Workshop on GRAph Searching, Theory and Applications, GRASTA 2014

Author: Fomin, Fedor V., Fraigniaud, Pierre, Nisse, Nicolas, Thilikos, Dimitrios M., Department of Informatics [Bergen] (UiB), University of Bergen (UiB), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA), Department of Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), 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), AlGCo project team, CNRS, LIRMM, Montpellier, France, Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), and Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)
Subjects: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract: Graph searching involves a team of mobile agents (called searchers or pursuers or cops) that aims at cap- turing a set of escaping agents (called evaders or fugitives or robbers) that hide in a network modeled by a graph. There are many variants of graph searching studied in the literature, often referred to as a pursuit- evasion game or cops and robbers game. These variants are either application driven, i.e. motivated by problems in practice, or are inspired by foundational issues in Computer Science, Discrete Mathematics, and Artificial Intelligence. Thus many researchers from different areas of Mathematics, Computer Science and Operations Research are interested in quite similar problems around graph searching.
Published: 2014

27. Report on GRASTA 2014

Author: Fomin, Fedor V., Fraigniaud, Pierre, Nisse, Nicolas, Thilikos, Dimitrios M., Department of Informatics [Bergen] (UiB), University of Bergen (UiB), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA), Department of Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), 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 AlGCo project team, CNRS, LIRMM, Montpellier, France
Subjects: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract: Graph searching involves a team of mobile agents (called searchers or pursuers or cops) that aims at cap- turing a set of escaping agents (called evaders or fugitives or robbers) that hide in a network modeled by a graph. There are many variants of graph searching studied in the literature, often referred to as a pursuit- evasion game or cops and robbers game. These variants are either application driven, i.e. motivated by problems in practice, or are inspired by foundational issues in Computer Science, Discrete Mathematics, and Artificial Intelligence. Thus many researchers from different areas of Mathematics, Computer Science and Operations Research are interested in quite similar problems around graph searching.
Published: 2014

28. Theory and Applications of Bidimensionality

Author: 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), Department of Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), and This work was co-financed by the European Union (European Social Fund - ESF) and Greek national funds through the Operational Program 'Education and Lifelong Learning' of the Na- tional Strategic Reference Framework (NSRF) - Research Funding Program: 'Thales. Investing in knowledge society through the European Social Fund.
Subjects: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; Bidimensionality Theory is a meta-algorithmic theory whose main ingredients are the Grid Exclusion Theorem of the Graph Minors series of Robertson and Seymour and the celebrated Courcelle’s Theorem. The grid exclusion theorem states that if a graph excludes a bidimensional grid as a minor (a graph H is a minor of a graph G if H can be obtained by some subgraph of G by con- tracting edges) then its structure topologically resembles the structure of a tree (in technical terms, it has small treewidth). Intuitively, this result says that the absence of the bidimensional structure of a grid implies that a graph has the “mono-dimensional” structure of a tree. On the other side, Courcelle’s theorem states that if a problem on graphs is expressible in Monadic Second Order Logic (MSOL), then it is possible to solve it in linear time when the treewidth of their input graphs is fixed. Intuitively, this theorem expresses the fact that the mono- dimensional structure of a tree (i.e., small treewidth) makes it possible to treat a graph as the input string of a finite-state tree automaton, where the finiteness of its states is guaranteed by the MSOL-expressibility of the problem. Combin- ing these two results together, we derive that the absence of the bidimensional structure of a grid, enables the applicability of the “divide-and-conquer” tech- nique for problems of certain descriptive complexity. It appears that for many graph theoretic problems the existence of a grid-minor (or other bidimensional strucures) on the input graph provides a certificate for an immediate negative (or positive) answer and, for the remaining instances, a dynamic programming approach on graphs of bounded treewidth may give an answer to the problem. This phenomenon reveals fruitful interleave between graph structure and logic in graph algorithms. Bidimensionality Theory aims at systematizing this idea and extending its applicability in diverse paradigms of algorithm design.
Published: 2013
Full Text: View/download PDF

29. Nearly Planar Graphs and {\lambda}-flat Graphs

Author: Grigoriev, Alexander, Koutsonas, Athanassios, Thilikos, Dimitrios M., Amsterdam School of Economics (ASE), University of Amsterdam [Amsterdam] (UvA), 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 Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), and Thilikos, Dimitrios
Subjects: [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Mathematics - Combinatorics, G.2.2, 05C10
Abstract: A graph G is {\xi}-nearly planar if it can be embedded in the sphere so that each of its edges is crossed at most {\xi} times. The family of {\xi}-nearly planar graphs is widely extending the notion of planarity. We introduce an alternative parameterized graph family extending the notion of planarity, the {\lambda}-flat graphs, this time defined as powers of plane graphs in regard to a novel notion of distance, the wall-by-wall distance. We show that the two parameterized graph classes are parametrically equivalent.
Published: 2013

30. Evaluating Cooperation in coauthorship graphs with degeneracy

Author: Giatsidis, Christos, Vazirgiannis, Michalis, Thilikos, Dimitrios M., Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Athens University of Economics and Business (AUEB), Department of Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), 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: [INFO.INFO-IR]Computer Science [cs]/Information Retrieval [cs.IR], graph degeneracy, fractional cores, Collaboration networks
Abstract: National audience; We demonstrate a system that supports the visual explo- ration of collaboration networks. The system leverages the notion of fractional cores introduced in earlier work to rank vertices in a collaboration network and filter vertices' neigh- borhoods. Fractional cores build on the idea of graph degen- eracy as captured by the notion of k-cores in graph theory and extend it to undirected edge-weighted graphs. In a co- authorship network, for instance, the fractional core index of an author intuitively reflects the degree of collaboration with equally or higher-ranked authors. Our system has been deployed on a real-world co-authorship network derived from DBLP, demonstrating that the idea of fractional cores can be applied even to large-scale networks. The system provides an easy-to-use interface to query for the fractional core index of an author, to see who the closest equally or higher-ranked co-authors are, and explore the entire co-authorship network in an incremental manner.
Published: 2013

31. 6th Workshop on Graph Classes, Width Parameters and Optimization (GROW 2013)

Author: Thilikos, Dimitrios M., Department of Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), 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: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract: International audience; Santorini Island, October 09-11, 2013, Greece.
Published: 2013

32. (Meta) Kernelization

Author: Bodlaender, Hans L., Fomin, Fedor V., Lokshtanov, Daniel, Penninkx, Eelko, Saurabh, Saket, Thilikos, Dimitrios M., Department of Information and Computing Sciences [Utrecht], Utrecht University [Utrecht], Department of Informatics [Bergen] (UiB), University of Bergen (UiB), 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: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract: Complete version of the paper of FOCS 2009; In a parameterized problem, every instance I comes with a positive integer k. The problem is said to admit a polynomial kernel if, in polynomial time, one can reduce the size of the instance I to a polynomial in k, while preserving the answer. In this work we give two meta-theorems on kernelzation. The first theorem says that all problems expressible in Counting Monadic Second Order Logic and satisfying a coverability property admit a polynomial kernel on graphs of bounded genus. Our second result is that all problems that have finite integer index and satisfy a weaker coverability property admit a linear kernel on graphs of bounded genus. These theorems unify and extend all previously known kernelization results for planar graph problems.
Published: 2013

33. Bidimensional Structures: Algorithms, Combinatorics and Logic (Dagstuhl Seminar 13121)

Author: Demaine, Erik D., Fomin, Fedor V., Hajiaghayi, Mohammadtaghi, Thilikos, Dimitrios M., Computer Science and Artificial Intelligence Laboratory [Cambridge] (CSAIL), Massachusetts Institute of Technology (MIT), Department of Informatics [Bergen] (UiB), University of Bergen (UiB), AT&T Laboratories, Department of Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), 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: Parameterized Algorithms, Treewidth, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Graph Minors, Graph algorithms
Abstract: International audience; We provide a report on the Dagstuhl Seminar 13121: Bidimensional Structures: Algorithms, Combinatorics and Logic held at Schloss Dagstuhl in Wadern, Germany between Monday 18 and Friday 22 of March 2013. The report contains the motivation of the seminar, the abstracts of the talks given during the seminar, and the list of open problems.
Published: 2013
Full Text: View/download PDF

34. A linear kernel for planar red-blue dominating set

Author: Valentin Garnero, Ignasi Sau, 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), Department of Mathematics [Athens], and National and Kapodistrian University of Athens (NKUA)
Subjects: FOS: Computer and information sciences, 05C85, 05C10, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], G.2.2, Astrophysics::Cosmology and Extragalactic Astrophysics, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], planar graphs, linear kernels, Computer Science - Data Structures and Algorithms, Astrophysics::Solar and Stellar Astrophysics, Data Structures and Algorithms (cs.DS), Astrophysics::Galaxy Astrophysics, domination, parameterized complexity
Abstract: In the Red-Blue Dominating Set problem, we are given a bipartite graph $G = (V_B \cup V_R,E)$ and an integer $k$, and asked whether $G$ has a subset $D \subseteq V_B$ of at most $k$ "blue" vertices such that each "red" vertex from $V_R$ is adjacent to a vertex in $D$. We provide the first explicit linear kernel for this problem on planar graphs, of size at most $43k$., 20 pages, 5 figures
Published: 2013

35. NII Shonan Meeting on: Parameterized Complexity and the Understanding, Design and Analysis of Heuristics

Author: Gutin, Gregory, Iwama, Kazuo, Thilikos, Dimitrios M., Department of Computer Science, Royal Holloway [University of London] (RHUL), Department of Mathematics [Kyoto], Kyoto University [Kyoto], Department of Informatics and Telecomunications [Kapodistrian Univ] (DI NKUA), National and Kapodistrian University of Athens (NKUA), 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 Thilikos, Dimitrios
Subjects: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract: International audience; National Institute of Informatics Shonan Village Center 2-1-2 Hitotsubashi, Chiyoda-Ku, Tokyo, Japan May 06-11, 2013
Published: 2013

36. (Meta) Kernelization

Author: Bodlaender, Hans L., Fomin, Fedor V., Lokshtanov, Daniel, Penninkx, Eelko, Saurabh, Saket, Thilikos, Dimitrios M., and Thilikos, Dimitrios
Subjects: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Abstract: In a parameterized problem, every instance I comes with a positive integer k. The problem is said to admit a polynomial kernel if, in polynomial time, one can reduce the size of the instance I to a polynomial in k, while preserving the answer. In this work we give two meta-theorems on kernelzation. The first theorem says that all problems expressible in Counting Monadic Second Order Logic and satisfying a coverability property admit a polynomial kernel on graphs of bounded genus. Our second result is that all problems that have finite integer index and satisfy a weaker coverability property admit a linear kernel on graphs of bounded genus. These theorems unify and extend all previously known kernelization results for planar graph problems.
Published: 2013

37. Foreword: Special Issue on Theory and Applications of Graph Searching Problems

Author: Thilikos, Dimitrios M., Fraigniaud, Pierre, Fomin, Fedor V., Kreutzer, Stephan, 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 Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Department of Informatics [Bergen] (UiB), University of Bergen (UiB), and Technische Universität Berlin (TU)
Subjects: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract: International audience; In a Graph Searching Game, one part is a set of escaping mobile entities, called evaders (or fugitives), that hide in a graph representing a network, and the other part is a number of chasing agents, called searchers (or pursuers), that move systematically in the graph. The game may vary significantly according to the capabilities of the evaders and the pursuers in terms of relative speed, sensor capabilities, visibility, etc. The objective of the game is to capture the evaders in an optimal way, where the notion of optimality itself admits varying interpretations. Alternatively, such games are known as pursuit- evasion games or cops and robbers games. Graph searching revealed the need to express in a formal mathematical way intuitive concepts such as avoidance, surrounding, sense of direction, hiding, persecution, threatening, collaboration, and coalition. There are many variants of graph searching studied in the literature, which are either application driven, i.e. motivated by problems in practice, or are inspired by foundational issues in Computer Science, Discrete Mathematics, and Artificial Intelligence. They are related to diverse topics such as Information Seeking, Robot motion planning, Database Theory, Logic, Distributed Computing, Models of computation, and Network security. The workshop series GRASTA, GRAph Searching, Theory and Applications was established as the main forum on the area of Graph Searching and gathers the widest possible variety of related disciplines. It has already held in Anogia, Crete, Greece (2006), Praia de Redonda, Ceara, Brazil (2008), and Valtice chateau, Valtice, Czech Republic (2009). This volume is a follow up of the fourth event of the series, namely, the 4th Workshop on GRAph Searching, Theory and Applications (GRASTA 2011) that took place during Dagstuhl Seminar 11071, from February 13, 2011 to February 18, 2012. While most of the submissions came from the participants of the workshop, there were also many from other contributors. There were, 19 submissions in total. All papers have been carefully reviewed according to the highest standards of Theoretical Computer Science and, among them, 11 have finally been accepted. The material appearing in this issue comprises a wide variety of topics including, Parity games, (hyper)Graph parameters, Graph exploration, Online algorithms, Competitive analysis, Sensor networks, Cleaning games, Chip firing problems, and Random walks. Finally, we are in the happy position to dedicate this issue to the 60th birthday of Professor Lefteris M. Kirousis. His insight and early vision on Graph Searching has been a source of inspiration for many of us!
Published: 2012
Full Text: View/download PDF

38. 5th Workshop on GRAph Searching, Theory and Applications (GRASTA 2012)

Author: Fomin, Fedor V., Nowakowski, Richard J., Pralat, Pawel, Thilikos, Dimitrios M., Department of Informatics [Bergen] (UiB), University of Bergen (UiB), Department of Mathematics and Statistics [Canada], Dalhousie University [Halifax], Department of Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), 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: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract: International audience; Banff International Research Station for Mathematical Innovation and Discovery, October 7-12, 2012, Banff, Alberta Canada.
Published: 2012

39. Parameterized and Exact Computation

Author: Woeginger, Gerhard J., Thilikos, Dimitrios M., Department of mathematics and computing science [Eindhoven], Eindhoven University of Technology [Eindhoven] (TU/e), Department of Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), 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), Dimitrios M. Thilikos, and Gerhard J. Woeginger
Subjects: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract: International audience; 7th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12-14, 2012. Proceedings
Published: 2012
Full Text: View/download PDF

40. Contraction checking in graphs on surfaces

Author: Kaminski, Marcin, Thilikos, Dimitrios M., Dürr, Christoph, Christoph Dürr, Thomas Wilke, Département d'Informatique [Bruxelles] (ULB), Faculté des Sciences [Bruxelles] (ULB), Université libre de Bruxelles (ULB)-Université libre de Bruxelles (ULB), Department of Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), 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: [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], Linkages, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Topological Minors, Surfaces, Parameterized algorithms, 010201 computation theory & mathematics, Computer Science, 0202 electrical engineering, electronic engineering, information engineering, Contractions, 020201 artificial intelligence & image processing, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC]
Abstract: International audience; The Contraction Checking problem asks, given two graphs H and G as input, whether H can be obtained from G by a sequence of edge contractions. Contraction Checking remains NP-complete, even when H is fixed. We show that this is not the case when G is embeddable in a surface of fixed Euler genus. In particular, we give an algorithm that solves Contraction Checking in f(h,g)*|V(G)|^3 steps, where h is the size of H and g is the Euler genus of the input graph G.
Published: 2012

41. Approximating Acyclicity Parameters of Sparse Hypergraphs

Author: Fomin, Fedor V., Golovach, Petr A., Thilikos, Dimitrios M., Department of Informatics [Bergen] (UiB), University of Bergen (UiB), Department of Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), Susanne Albers and Jean-Yves Marion, and Loria, Publications
Subjects: FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Treewidth, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], hypergraph, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, Computational Complexity (cs.CC), Computer Science::Computational Complexity, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Matematikk og naturvitenskap: 400::Matematikk: 410 [VDP], Computer Science::Discrete Mathematics, Computer Science - Data Structures and Algorithms, treewidth, Data Structures and Algorithms (cs.DS), Mathematics and natural scienses: 400::Mathematics: 410 [VDP], 0101 mathematics, Computer Science::Data Structures and Algorithms, 000 Computer science, knowledge, general works, Mathematics::Combinatorics, Hypertree width, 010102 general mathematics, hypertree width, Computer Science - Computational Complexity, ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY/F.2.2: Nonnumerical Algorithms and Problems, 010201 computation theory & mathematics, Hypergraph, Computer Science, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC]
Abstract: http://arxiv.org/abs/0809.3646; International audience; The notions of hypertree width and generalized hypertree width were introduced by Gottlob, Leone, and Scarcello (PODS'99, PODS'01) in order to extend the concept of hypergraph acyclicity. These notions were further generalized by Grohe and Marx in SODA'06, who introduced the fractional hypertree width of a hypergraph. All these width parameters on hypergraphs are useful for extending tractability of many problems in database theory and artificial intelligence. Computing each of these width parameters is known to be an NP-hard problem. Moreover, the (generalized) hypertree width of an n-vertex hypergraph cannot be approximated within a logarithmic factor unless P=NP. In this paper, we study the approximability of (generalized, fractional) hyper treewidth of sparse hypergraphs where the criterion of sparsity reflects the sparsity of their incidence graphs. Our first step is to prove that the (generalized, fractional) hypertree width of a hypergraph is constant-factor sandwiched by the treewidth of its incidence graph, when the incidence graph belongs to some apex-minor-free graph class (the family of apex-minor-free graph classes includes planar graphs and graphs of bounded genus). This determines the combinatorial borderline above which the notion of (generalized, fractional) hypertree width becomes essentially more general than treewidth, justifying that way its functionality as a hypergraph acyclicity measure. While for more general sparse families of hypergraphs treewidth of incidence graphs and all hypertree width parameters may differ arbitrarily, there are sparse families where a constant factor approximation algorithm is possible. In particular, we give a constant factor approximation polynomial time algorithm for (generalized, fractional) hypertree width on hypergraphs whose incidence graphs belong to some H-minor-free graph class. This extends the results of Feige, Hajiaghayi, and Lee from STOC'05 on approximating treewidth of H-minor-free graphs.
Published: 2009

42. On Self-Duality of Branchwidth in Graphs of Bounded Genus

Author: Thilikos, Dimitrios M., Monteil, Alain, Department of Mathematics [Athens], and National and Kapodistrian University of Athens (NKUA)
Subjects: [INFO.INFO-OH] Computer Science [cs]/Other [cs.OH], [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH]
Abstract: International audience; A graph parameter is self-dual in some class of graphs embeddable in some surface if its value does not change in the dual graph more than a constant factor. Self-duality has been examined for several width-parameters, such as branchwidth in graphs in some surface. In this direction, we prove that $\\mathbf bw(G^*) \\leq 6\\times \\mathbf bw(G) +2g-4$ for any graph $G$ embedded in a surface of Euler genus $g$.
Published: 2009

43. Subexponential Parameterized Algorithms for Bounded-Degree Connected Subgraph Problems on Planar Graphs

Author: Thilikos, Dimitrios M., Monteil, Alain, Department of Mathematics [Athens], and National and Kapodistrian University of Athens (NKUA)
Subjects: [INFO.INFO-MC]Computer Science [cs]/Mobile Computing, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-MC] Computer Science [cs]/Mobile Computing, [INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI], MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; We present subexponential parameterized algorithms on planar graphs for a family of problems that consist in, given a graph $G$, finding a connected subgraph $H$ with bounded maximum degree, while maximising the number of edges (or vertices) of $H$. These problems are natural generalisations of the \\textscLongest Path problem. Our approach uses bidimensionality theory to obtain combinatorial bounds, combined with dynamic programming techniques over a branch decomposition of the input graph. These techniques need to be able to keep track of the connected components of the partial solutions over the branch decomposition, and can be seen as an \\emphalgorithmic tensor that can be applied to a wide family of problems that deal with finding connected subgraphs under certain constraints.
Published: 2009

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

Select search scope, currently: Articles Catalog books, media & more in Jio Institute collections Articles journal articles & other e-resources

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Database

43 results on '"Thilikos, Dimitrios M."'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources