About my Math & CS scientific research

articles
Prof. RNDr. Petr Hliněný, Ph.D.

@ynenilhfi.muni.cz
FI research direction
Faculty of Informatics MU Brno, CZ

If you love discrete mathematics, computer science, and mainly graphs more than anything else, then ...  Welcome!

Scientific research collaboration

Local research team at Faculty of Informatics MU Brno, CZ:

Collaboration with other Czech universities:

  • Charles University, MFF (Prague)
    • Jan Kratochvíl, GraDR - EuroGIGA - read below..., Zdeněk Dvořák
    • Dan Kráľ (now Warwick) and
      collaborating on structural graph problems, and on crossing numbers.
  • West Bohemia University, FAV (Pilsen)
    • Tomáš Kaiser and Jakub Teska, GAČR P202/11/0196 - during 2011-2014.

Collaboration with foreign institutions:

  • University of Warwick, UK
  • RWTH Aachen University, Germany
    • Peter Rossmanith et al, Theoretical Computer Science,
      jointly working mainly on structural width parameters and parameterized algorithmics.
  • University of Bergen, Norway
    • Saket Saurabh, Daniel Lokshtanov, Informatics,
      algorithmic metatheorems and logic on graphs.
  • University Osnabrueck, Germany
  • Universidad Autonoma de San Luis Potosi, Mexico
Current research grants
  • Czech Science Foundation (GAČR):
    • 5 research grants successfully finished prior to 2015,
    • now investigating 17-00837S "Structural properties, parameterized tractability and hardness in combinatorial problems"
  • Institute of Theoretical Computer Science (ITI):
    • Czech national project 1M0545, 2005-2011,
    • now GAČR P202/12/G061, 2012-2018.

Research opportunities for students

Even if you are a young student at MU, you do not have to stay aside and may do something more than other students - say also with our research group...

The research group welcomes all students interested in a theoretical research, both from Informatics and Mathematics. See below for a research statement. And, especially for keen first year students, come to our FI:IV119 Seminar on Discrete Mathematical Methods in Spring.

  • See, e.g., the current Bc/Ms thesis topics for an inspiration,
  • or inquire about PhD study under my supervision at FI MU Brno, CZ  (with stipend, good foreign applicants welcome).
    • Generally speaking, any theoretical research into graphs (with emphasis on structural and topological graph theory) and into graph algorithms and logic on graphs (with emphasis on parameterized complexity) can be discussed for a PhD.
    • Refer to the general admission procedure and special PhD calls.
  • Young students may have a first taste of real scientific research at the Spring School on Combinatorics organized every year by KAM MFF UK, or at the SVOČ student scientific competition.

Formela Lab Seminar

Having multiple seminar groups every semester (with different teachers), choose your favourite topic from the list (hint: choose graphs/combinatorics/geometry...).

Students' FI:IV119 Seminar on Discrete Mathematical Methods

This is an informal Spring seminar for all students who like mathematics, and especially beatiful mathematical problems, solutions, and proofs - as presented to us by famous "Proofs from THE BOOK". If you have ever tried "Mathematical olympiad" or other math competitions at elementary and high schools, then drop by and see how easy is to get from math fun to serious real science. Especially first year students with interest in math are most warmly welcome!

  • For all young students who like nice clean mathematics, no prerequisites required.
    Official seminar entry in IS
  • Spring 2017 seminar: in C417, Wednesday 8-10 every week
    • So, which problems to deal with this year? We will (traditionally) begin with the number of primes, and we will also look this year at various proofs of Euler's formula... (see this) Then we will pick other nice problems (and their solutions) from number theory, discrete geometry, combinatorics and graphs...
    • For every interested students, think about the following already before the first seminar:
      What Euler's formula says for a polytope in 4D? How to prove it, knowing the 3D version?
      Alternatively: Imagine a simplex in 3D, and several (or many) points inside it. Can you now cut the big simplex into smaller simplices such that their vertices will be the original vertices or the given internal points, and that every two of these points will share an edge of some simplex? (I.e., the net of this complex shall be the complete graph.) How would you describe such a cutting?
    • Come and see us (even if you participated in 2016 - we will study different topics of The Book)...
  • See also a list of past 2016 topics here.

Recent results and ongoing research (2015-7)

  • Another approach to MSO definability of path- and branch-decompositions of graphs and matroids (avoiding "guidance systems")... With E. Kim and J. Obdržálek.
  • Finally, finishing a full asymptotic characterization of k-crossing-critical graphs for fixed k>2. Joint work with Z. Dvořák and B. Mohar.
  • A short new proof of Euler-Poincare Formula in every dimension, not using shellability of polytopes.
  • Algorithmic metatheorems for FO logic on dense structures - an FPT m.c. algorithm on posets of bounded width (FOCS2015), a new perspective on interpretation of dense classes into sparse classes (LICS2016), sample applications to geometric graphs (IPEC 2017); with local Brno collaborators and people from Bergen. See below.
  • A self-reduction FPT algorithm for matroid path-decomposition, linear rank-decomposition of a graph, and Trellis decomposition of a linear code. Simpler than the SODA2016 algorithm of Oum et al.
  • New hardness results for the graph crossing number problems - hardness of joint embedding in genus 6, hardness of the crossing number for almost-planar graphs even if no more than 16 vertices have degree >3 (both ISAAC2015, with G. Salazar), no polynomial kernel for crossing number (SoCG2016, with M. Dernar), hard to determine the parity of the crossing number (2017 with C. Thomassen)...
  • The multiple-edge insertion problem in planar graphs is solvable exactly in parameterized linear time (before, only constant additive factor approximation known in full linear time). With M. Chimani (SoCG2016).
  • See also the publication list for the recent (submitted) entries.
Research topics: Structural width parameters in algorithms

In this area we study traditional as well as some new parameters describing the "width" of combinatorial objects - in the sense of complexity, how much they "resemble" trivial input structures like trees; tree-width, branch-width, rank-width, DAG-width, or DAG-depth, to mention just a few. The expected outcome is that on input objects of low width, many otherwise hard algorithmic problems become tractable (giving so called FPT or XP algorithms), as for instance various MSO-definable properties. The question of how to obtain such low degree structural decompositions is also studied, e.g. obtaining matroid branch-decomposition and graph rank-decomposition in FPT.

Our research directions include special emphasis on directed graph width measures, on getting complexity lower bounds on tractability wrt. width parameters, and most recently, on measuring "depth" of a graph and on kernelization results using new structural parameters.

Key recent publications:
Research topics: MSO / FO logic and algorithms

Following on the previous topic, we particularly focus on algorithmic metatheorems which express a whole class of problems by means of a logical language, and then provide general (parameterized) algorithms for solving them. Prime role is played here by the new depth measures (shrub-depth) and their properties, and by a general question of how high is "logical/descriptive complexity" of a graph or graph class. The question of what are the limits (lower bounds) of this approach, is also considered.

Recent important results have been obtained for FO properties on posets of bounded width (meaning the size of a largest antichain).

Key publications:
  • 2017 (co-authors R. Ganian, J. Nešetřil, J. Obdržálek, P. Ossona de Mendez):   Shrub-depth: Capturing Height of Dense Graphs.  Submitted (2017), 26 p.   URL: arxiv.org/abs/1707.00359.
  • 2017 (co-authors F. Pokrývka, B. Roy):   FO model checking of geometric graphs.  In: IPEC 2017 (2017), to appear.   URL: arxiv.org/abs/1709.03701.
  • 2017 (co-authors J. Gajarský, T. Kaiser, D. Král', M. Kupec, J. Obdržálek, S. Ordyniak, V. Tuma):   First order limits of sparse graphs: Plane trees and path-width.  Random Structures & Algorithms 50 (2017), 612-635.   URL: arxiv.org/abs/1504.08122. DOI 10.1002/rsa.20676. © John Wiley & Sons, Inc.
  • 2016 (co-authors J. Gajarský, D. Lokshtanov, J. Obdržálek, M.S. Ramanujan):   A New Perspective on FO Model Checking of Dense Graph Classes.  In: LICS 2016, ACM (2016), 176-184.   DOI 10.1145/2933575.2935314. Preprint/file.
  • 2015 (co-authors J. Gajarský, D. Lokshtanov, J. Obdržálek, S. Ordyniak, M.S. Ramanujan, S. Saurabh):   FO Model Checking on Posets of Bounded Width.  In: IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, IEEE (2015), 963-974.   URL: arxiv.org/abs/1504.04115. DOI 10.1109/FOCS.2015.63.
  • 2015 (co-authors J. Gajarský, J. Obdržálek, S. Ordyniak):   Faster Existential FO Model Checking on Posets.  Logical Methods in Computer Science 11(4) (2015), paper 8.   URL: arxiv.org/abs/1409.4433. DOI 10.2168/LMCS-11(4:8)2015.
  • 2015 (co-authors R. Ganian, D. Král', J. Obdržálek, J. Schwartz, J. Teska):   FO Model Checking of Interval Graphs.  Logical Methods in Computer Science 11(4) (2015), paper 11.   URL: arxiv.org/abs/1302.6043. DOI 10.2168/LMCS-11(4:11)2015.
  • 2015 (co-author J. Gajarský):   Kernelizing MSO Properties of Trees of Fixed Height, and Some Consequences.  Logical Methods in Computer Science 11(1) (2015), paper 19.   URL: arxiv.org/abs/1204.5194. DOI 10.2168/LMCS-11(1:19)2015.
  • 2012 (co-authors R. Ganian, J. Nešetřil, J. Obdržálek, P. Ossona de Mendez, R. Ramadurai):   When Trees Grow Low: Shrubs and Fast MSO1.  In: Math Foundations of Computer Science MFCS 2012, Lecture Notes in Computer Science 7464, Springer (2012), 419-430.   DOI 10.1007/978-3-642-32589-2_38. © Springer-Verlag. Preprint/file.
  • 2006:   Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids.  J. of Combinatorial Theory ser. B 96 (2006), 325-351.   DOI 10.1016/j.jctb.2005.08.005. © Elsevier B.V. Preprint/file.
Research topics: Graph crossing number, structural and algorithmic

This research direction copes with the problem to draw a graph with the least possible number of edge crossings, which appears to be an unusually difficult algorithmic task. Our first interest is in finding good efficient approximation algorithms of the crossing number (some of which are even practically implementable, a quite rare case in this area). Besides that we deal with theoretical research of crossing-critical graphs, and with computational hardness questions related to this problem. We are now particularly looking at an approximate structural description of crossing-critical graphs, and on strengthening known hardness results on very special classes of graphs.

Key publications:
Research topics: Planar covers and emulators

This last research direction deals with just a small mathematical puzzle - the questions about which nonplanar graphs have finite planar covers (Negami's conjecture) and emulators (initiated by old Fellows' work). Briefly describing, a graph G has a planar cover (emulator) of there is a planar graph H and a locally bijective (surjective) homomorphism from H to G. On the one hand, Negami's conjecture states that finite planar covers exist exactly for projective-planar graphs. On the other hand, analogical conjecture about planar emulators was disproved in 2008 by Rieck-Yamashita, and now we have got many more strange counterexamples to that. Both these problems are still wide open.

Key publications:
Research topics: Route planning in huge graphs (road networks)

We are also investigating some new directions in the route planning problem (as e.g. in GPS navigations), both on theoretical and experimental sides. The particular emphasis of our approach is on two points - to get "reasonable" routes, and to make the preprocessed data for fast queries as small as possible (currently below 1% of the map size). We approach both objectives with a newly suggested notion of "scope".

Key publications: