About my Math & CS scientific research
Prof. RNDr. Petr Hliněný, Ph.D.
@ynenilhfi.muni.cz
FI research direction
Faculty of Informatics MU Brno, CZ
- Research contacs, collaborators, and grants.
- Recent results (obtained by our group).
- Research opportunities for students in our group.
- Research topics: width params, logic alg, crossing number, route planning, planar cover.
- MACEK - practical structural computation with matroids.
- See also the complete publication and conference lists.
If you love discrete mathematics, computer science, and mainly graphs more than anything else, then ... Welcome!
Scientific research network
Local research team at Faculty of Informatics MU Brno, CZ:
- Petr Hliněný (team head),
- Jan Obdržálek,
Bodhayan Roy (postdoc researcher 2017-2019), Michał Dębski (postdoc researcher 2018- ). -
Marek Derňár,
Onur Çağırıcı,
Deniz Agaoglu, Filip Pokrývka
(Ph.D. students).
New doctoral applicants are welcome, refer particularly to the current PhD calls with additional funding. - Michal Korbela (Master students).
- Jan Obdržálek,
- See also the FMDSA working seminar, and the DIMEA lab (in past the Formela lab).
Collaboration with members of institutions:
- Charles University, Prague CZ; University of Warwick, UK; University Osnabrueck, Germany; RWTH Aachen University, Germany; University of Bergen, Norway; Universidad Autonoma de San Luis Potosi, Mexico; ...
Current research grants
- PI - 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"
- Member - 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...
Our 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 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 2018 seminar: in C417, Tuesday 10-12 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...
- Come and see us (even if you participated in 2017 - we will study different topics of The Book)...
- See also a list of past 2017 topics here.
Recent results and ongoing research (2016-8)
- Finally, finishing a full asymptotic characterization of k-crossing-critical graphs for fixed k>2. Joint work with Z. Dvořák and B. Mohar (SoCG2018).
- Another approach to MSO definability of path- and branch-decompositions of graphs and matroids (avoiding "guidance systems")... With E. Kim and J. Obdržálek.
- Complexity of colouring on polygon visibility graphs - hard from 6 colours (FSTTCS2017, with Cagirici and Roy).
- 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. (SIDMA).
- 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:- 2018 (co-authors J. Gajarský, H.R. Tiwary): Parameterized Extension Complexity of Independent Set and Related Problems. Discrete Applied Mathematics 248 (2018), 56--67. URL: arxiv.org/abs/1511.08841. DOI 10.1016/j.dam.2017.04.042. © Elsevier B.V.
- 2017 (co-authors J. Gajarský, M. Koutecký, S. Onn): Parameterized Shifted Combinatorial Optimization. In: COCOON 2017, Lecture Notes in Computer Science 10392, Springer (2017), 224--236. URL: arxiv.org/abs/1702.06844. DOI 10.1007/978-3-319-62389-4_19. © Springer-Verlag.
- 2017 (co-authors J. Gajarský, J. Obdržálek, S. Ordyniak, F. Reidl, P. Rossmanith, F. Sánchez Villaamil, S. Sikdar): Kernelization Using Structural Parameters on Sparse Graph Classes. Journal of Computer and System Sciences 84 (2017), 219--242. URL: arxiv.org/abs/1302.6863. DOI 10.1016/j.jcss.2016.09.002. © Elsevier B.V.
- 2016 (co-authors R. Ganian, J. Kneis, D. Meister, J. Obdržálek, P. Rossmanith, S. Sikdar): Are there any good digraph width measures?. J. of Combinatorial Theory ser. B 116 (2016), 250--286. URL: arxiv.org/abs/1004.1485. DOI 10.1016/j.jctb.2015.09.001. © Elsevier B.V.
- 2014 (co-authors R. Ganian, A. Langer, J. Obdržálek, P. Rossmanith, S. Sikdar): Lower Bounds on the Complexity of MSO1 Model-Checking. Journal of Computer and System Sciences 80 (2014), 180--194. URL: arxiv.org/abs/1109.5804. DOI 10.1016/j.jcss.2013.07.005. © Elsevier B.V.
- 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.
- 2011 (co-authors R. Ganian, J. Obdržálek): Clique-width: When Hard Does Not Mean Impossible. In: Symposium on Theoretical Aspects of Computer Science STACS 2011, Leibniz International Proceedings in Informatics LIPIcs Vol 9, Dagstuhl (2011), 404--415. URL: drops.dagstuhl.de/opus/volltexte/2011/3030. DOI 10.4230/LIPIcs.STACS.2011.404.
- 2008 (co-author S. Oum): Finding Branch-decompositions and Rank-decompositions. SIAM J. Computing 38 (2008), 1012--1032. DOI 10.1137/070685920. © Society for Industrial and Applied Mathematics. Preprint/file.
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:- 2018 (co-authors F. Pokrývka, B. Roy): FO model checking of geometric graphs. In: IPEC 2017, LIPIcs Vol. 89, Dagstuhl (2018), 19:1--19:12. URL: arxiv.org/abs/1709.03701. DOI 10.4230/LIPIcs.IPEC.2017.19.
- 2019 (co-authors R. Ganian, J. Nešetřil, J. Obdržálek, P. Ossona de Mendez): Shrub-depth: Capturing Height of Dense Graphs. Logical Methods in Computer Science 15 (2019), 7:1--7:25. URL: arxiv.org/abs/1707.00359. DOI 10.23638/LMCS-15(1:7)2019.
- 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 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.
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:- 2018 (co-authors Z. Dvořák, B. Mohar): Structure and generation of crossing-critical graphs. In: SoCG 2018, LIPIcs Vol. 99, Dagstuhl (2018), 33:1--33:14. URL: arxiv.org/abs/1803.01931. DOI 10.4230/LIPIcs.SoCG.2018.33.
- 2019 (co-authors M.Bračič, D. Bokal, M. Derňár): On Degree Properties of Crossing-critical Families of Graphs. Electr. Journal of Combinatorics 26 (2019), #P1.53. URL: www.combinatorics.org/ojs/index.php/eljc/article/view/v26i1p53/7812.
- 2018 (co-author C. Thomassen): Deciding Parity of Graph Crossing Number. SIAM J. Discrete Mathematics 32-3 (2018), 1962--1965. DOI 10.1137/17M1137231. © Society for Industrial and Applied Mathematics. Preprint/file.
- 2017 (co-author M. Chimani): A Tighter Insertion-based Approximation of the Crossing Number. Journal of Combinatorial Optimization 33 (2017), 1183--1225. URL: arxiv.org/abs/1104.5039. DOI 10.1007/s10878-016-0030-z. © Elsevier B.V.
- 2016 (co-author M. Derňár): Crossing Number is Hard for Kernelization. In: SoCG 2016, LIPIcs Vol. 51, Dagstuhl (2016), 42:1--42:10. URL: arxiv.org/abs/1512.02379. DOI 10.4230/LIPIcs.SoCG.2016.42.
- 2016 (co-author M. Chimani): Inserting Multiple Edges into a Planar Graph. In: SoCG 2016, LIPIcs Vol. 51, Dagstuhl (2016), 30:1--30:15. URL: arxiv.org/abs/1509.07952. DOI 10.4230/LIPIcs.SoCG.2016.30.
- 2015 (co-author G. Salazar): On Hardness of the Joint Crossing Number. In: ISAAC 2015, Lecture Notes in Computer Science 9472, Springer (2015), 603--613. URL: arxiv.org/abs/1509.01787. DOI 10.1007/978-3-662-48971-0_51. © Springer-Verlag.
- 2019 (co-authors M. Chimani, G. Salazar): Toroidal Grid Minors and Stretch in Embedded Graphs. J. of Combinatorial Theory ser. B (2019), to appear. URL: arxiv.org/abs/1403.1273. DOI 10.1016/j.jctb.2019.05.009. © Elsevier B.V.
- 2010 (co-author M. Chimani): Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface. In: Symposium on Discrete Algorithms SODA 2010, ACM--SIAM (2010), 918--927. URL: www.siam.org/proceedings/soda/2010/soda10.php. © Society for Industrial and Applied Mathematics. Preprint/file.
- 2010 (co-author G. Salazar): Stars and Bonds in Crossing-Critical Graphs. Journal of Graph Theory 65 (2010), 198--215. DOI 10.1002/jgt.20473. © John Wiley & Sons, Inc. Preprint/file.
- 2006: Crossing Number is Hard for Cubic Graphs. J. of Combinatorial Theory ser. B 96 (2006), 455--471. DOI 10.1016/j.jctb.2005.09.009. © Elsevier B.V. Preprint/file.
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:- 2015 (co-author M. Derka): Planar Emulators Conjecture Is Nearly True for Cubic Graphs. European J. Combinatorics 48 (2015), 63--70. DOI 10.1016/j.ejc.2015.02.009. © Elsevier B.V. Preprint/file.
- 2013 (co-authors M. Chimani, M. Derka, M. Klusáček): How Not to Characterize Planar-emulable Graphs. Advances in Applied Mathematics 50 (2013), 46--68. URL: arxiv.org/abs/1107.0176. DOI 10.1016/j.aam.2012.06.004. © Elsevier B.V. Addendum.
- 2010: 20 Years of Negami's Planar Cover Conjecture. Graphs and Combinatorics 26 (2010), 525--536. DOI 10.1007/s00373-010-0934-9. © Springer-Verlag. Preprint/file. Addendum.
- 2004 (co-author R. Thomas): On possible counterexamples to Negami's planar cover conjecture. Journal of Graph Theory 46 (2004), 183--206. DOI 10.1002/jgt.10177. © John Wiley & Sons, Inc. Preprint/file. Addendum.
- 1999: Planar covers of graphs: Negami's conjecture. PhD. Dissertation, School of Math., Georgia Institute of Technology (1999), 132 p. Preprint/file.
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:- 2012 (co-author O. Moriš): Generalized Maneuvers in Route Planning. Computing and Informatics 31 (2012), 531--549. URL: www.cai.sk/ojs/index.php/cai/article/view/1007.
- 2011 (co-author O. Moriš): Scope-based route planning. In: ESA 2011, Lecture Notes in Computer Science 6942, Springer (2011), 445--456. URL: arxiv.org/abs/1101.3182. DOI 10.1007/978-3-642-23719-5_38. © Springer-Verlag.