BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Petr Hliněný

Petr Hliněný appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Discrete MathematicsData Structures and Algorithmsmath.COLogic in Computer ScienceComputational GeometryComputational ComplexityComputer Science and Game Theorymath.OC

Catalog footprint

What is connected

22works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

22 published item(s)

preprint2022arXiv

Automorphisms of Set Families and of Families of Cliques in an Interval Graph in FPT Time

We consider the following problem closely related to graph isomorphism. In a simplified version, the task is to compute the automorphism group of a given set family (or a hypergraph), that is, the group of all automorphisms of the given sets which are compatible with some permutation of their elements. In a general setting, the set family in question is a collection of cliques (called marked cliques) of a given interval graph, and the task is to compute the group of all permutations of the cliques which result from some automorpism of the underlying interval graph. This problem is obviously at least as hard as the graph isomorphism (GI-hard) already in the simplified version -- consider the set family of edges of a graph, and we give an FPT-time algorithm parameterized by the maximum number of sets in the family which are incomparable by inclusion (its antichain size). To our best knowledge, the general version of the problem has not been formulated in the literature so far. The problem has been inspired by the research of special cases of the isomorphism problem of chordal graphs; namely, the simplified set-family version is the core of our FPT algorithm for the isomorphism of so-called Sd-graphs [MFCS 2021], and the general version extends and improves a cumbersome technical step in our FPT algorithm for the isomorphism of chordal graphs of bounded leafage [WALCOM 2022]. The new algorithm combines two classical tools -- PQ-trees of interval graphs and Babai's tower-of-groups, in a nontrivial way.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Efficient Isomorphism for $S_d$-graphs and $T$-graphs

An $H$-graph is one representable as the intersection graph of connected subgraphs of a suitable subdivision of a fixed graph $H$, introduced by Biró, Hujter and Tuza (1992). An $H$-graph is proper if the representing subgraphs of $H$ can be chosen incomparable by the inclusion. In this paper, we focus on the isomorphism problem for $S_d$-graphs and $T$-graphs, where $S_d$ is the star with $d$ rays and $T$ is an arbitrary fixed tree. Answering an open problem of Chaplick, Töpfer, Voborn\'ık and Zeman (2016), we provide an FPT-time algorithm for testing isomorphism and computing the automorphism group of $S_d$-graphs when parameterized by~$d$, which involves the classical group-computing machinery by Furst, Hopcroft, and Luks (1980). We also show that the isomorphism problem of $S_d$-graphs is at least as hard as the isomorphism problem of posets of bounded width, for which no efficient combinatorial-only algorithm is known to date. Then we extend our approach to an XP-time algorithm for isomorphism of $T$-graphs when parameterized by the size of $T$. Lastly, we contribute a simple FPT-time combinatorial algorithm for isomorphism testing in the special case of proper $S_d$- and $T$-graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Graph Product Structure for h-Framed Graphs

Graph product structure theory expresses certain graphs as subgraphs of the strong product of much simpler graphs. In particular, an elegant formulation for the corresponding structural theorems involves the strong product of a path and of a bounded treewidth graph, and allows to lift combinatorial results for bounded treewidth graphs to graph classes for which the product structure holds, such as to planar graphs [Dujmović et al., J. ACM, 67(4), 22:1-38, 2020]. In this paper, we join the search for extensions of this powerful tool beyond planarity by considering the h-framed graphs, a graph class that includes 1-planar, optimal 2-planar, and k-map graphs (for appropriate values of h). We establish a graph product structure theorem for h-framed graphs stating that the graphs in this class are subgraphs of the strong product of a path, of a planar graph of treewidth at most 3, and of a clique of size $3\lfloor h/2 \rfloor +\lfloor h/3 \rfloor -1$. This allows us to improve over the previous structural theorems for 1-planar and k-map graphs. Our results constitute significant progress over the previous bounds on the queue number, non-repetitive chromatic number, and p-centered chromatic number of these graph classes, e.g., we lower the currently best upper bound on the queue number of 1-planar graphs and k-map graphs from 495 to 81 and from 32225k(k-3) to 61k, respectively. We also employ the product structure machinery to improve the current upper bounds of twin-width of planar and 1-planar graphs from 183 to 37, and from O(1) to 80, respectively. All our structural results are constructive and yield efficient algorithms to obtain the corresponding decompositions.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Isomorphism Testing for T-graphs in FPT

A T-graph (a special case of a chordal graph) is the intersection graph of connected subtrees of a suitable subdivision of a fixed tree T . We deal with the isomorphism problem for T-graphs which is GI-complete in general - when T is a part of the input and even a star. We prove that the T-graph isomorphism problem is in FPT when T is the fixed parameter of the problem. This can equivalently be stated that isomorphism is in FPT for chordal graphs of (so-called) bounded leafage. While the recognition problem for T-graphs is not known to be in FPT wrt. T, we do not need a T-representation to be given (a promise is enough). To obtain the result, we combine a suitable isomorphism-invariant decomposition of T-graphs with the classical tower-of-groups algorithm of Babai, and reuse some of the ideas of our isomorphism algorithm for S_d-graphs [MFCS 2020].

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Parameterised Partially-Predrawn Crossing Number

Inspired by the increasingly popular research on extending partial graph drawings, we propose a new perspective on the traditional and arguably most important geometric graph parameter, the crossing number. Specifically, we define the partially predrawn crossing number to be the smallest number of crossings in any drawing of a graph, part of which is prescribed on the input (not counting the prescribed crossings). Our main result - an FPT-algorithm to compute the partially predrawn crossing number - combines advanced ideas from research on the classical crossing number and so called partial planarity in a very natural but intricate way. Not only do our techniques generalise the known FPT-algorithm by Grohe for computing the standard crossing number, they also allow us to substantially improve a number of recent parameterised results for various drawing extension problems.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Twin-width and Limits of Tractability of FO Model Checking on Geometric Graphs

The complexity of the problem of deciding properties expressible in FO logic on graphs -- the FO model checking problem (parameterized by the respective FO formula), is well-understood on so-called sparse graph classes, but much less understood on hereditary dense graph classes. Regarding the latter, a recent concept of twin-width [Bonnet et al., FOCS 2020] appears to be very useful. For instance, the question of these authors [CGTA 2019] about where is the exact limit of fixed-parameter tractability of FO model checking on permutation graphs has been answered by Bonnet et al. in 2020 quite easily, using the newly introduced twin-width. We prove that such exact characterization of hereditary subclasses with tractable FO model checking naturally extends from permutation to circle graphs (the intersection graphs of chords in a circle). Namely, we prove that under usual complexity assumptions, FO model checking of a hereditary class of circle graphs is in FPT if and only if the class excludes some permutation graph. We also prove a similar excluded-subgraphs characterization for hereditary classes of interval graphs with FO model checking in FPT, which concludes the line a research of interval classes with tractable FO model checking started in [Ganian et al., ICALP 2013]. The mathematical side of the presented characterizations -- about when subclasses of the classes of circle and permutation graphs have bounded twin-width, moreover extends to so-called bounded perturbations of these classes.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Twin-width of Planar Graphs is at most 9, and at most 6 when Bipartite Planar

The structural parameter twin-width was introduced by Bonnet et al. in [FOCS 2020], and already this first paper included an asymptotic argument bounding the twin-width of planar graphs by a non-explicit constant. Quite recently, we have seen first small explicit upper bounds of 183 by Jacob and Pilipczuk [arXiv, January 2022], 583 by Bonnet et al. [arXiv, February 2022], and of 37 by Bekos et al. [arXiv, April 2022]. We prove that the twin-width of planar graphs is at most 9. Furthermore, if a planar graph is also bipartite, then its twin-width is at most 6.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Clique-Width of Point Configurations

While structural width parameters (of the input) belong to the standard toolbox of graph algorithms, it is not the usual case in computational geometry. As a case study we propose a natural extension of the structural graph parameter of clique-width to geometric point configurations represented by their order type. We study basic properties of this clique-width notion, and relate it to the monadic second-order logic of point configurations. As an application, we provide several linear FPT time algorithms for geometric point problems which are NP-hard in general, in the special case that the input point set is of bounded clique-width and the clique-width expression is also given.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On conflict-free chromatic guarding of simple polygons

We study the problem of colouring the vertices of a polygon, such that every viewer in it can see a unique colour. The goal is to minimise the number of colours used. This is also known as the conflict-free chromatic guarding problem with vertex guards, and is motivated, e.g., by the problem of radio frequency assignment to sensors placed at the polygon vertices. We first study the scenario in which viewers can be all points of the polygon (such as a mobile robot which moves in the interior of the polygon). We efficiently solve the related problem of minimising the number of guards and approximate (up to only an additive error) the number of colours required in the special case of polygons called funnels. Then we give an upper bound of O(log^2 n) colours on n-vertex weak visibility polygons, by decomposing the problem into sub-funnels. This bound generalises to all simple polygons. We briefly look also at the second scenario, in which the viewers are only the vertices of the polygon. We show a lower bound of 3 colours in the general case of simple polygons and conjecture that this is tight. We also prove that already deciding whether 1 or 2 colours are enough is NP-complete.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Parameterized Shifted Combinatorial Optimization

Shifted combinatorial optimization is a new nonlinear optimization framework which is a broad extension of standard combinatorial optimization, involving the choice of several feasible solutions at a time. This framework captures well studied and diverse problems ranging from so-called vulnerability problems to sharing and partitioning problems. In particular, every standard combinatorial optimization problem has its shifted counterpart, which is typically much harder. Already with explicitly given input set the shifted problem may be NP-hard. In this article we initiate a study of the parameterized complexity of this framework. First we show that shifting over an explicitly given set with its cardinality as the parameter may be in XP, FPT or P, depending on the objective function. Second, we study the shifted problem over sets definable in MSO logic (which includes, e.g., the well known MSO partitioning problems). Our main results here are that shifted combinatorial optimization over MSO definable sets is in XP with respect to the MSO formula and the treewidth (or more generally clique-width) of the input graph, and is W[1]-hard even under further severe restrictions.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Crossing Number is Hard for Kernelization

The graph crossing number problem, cr(G)<=k, asks for a drawing of a graph G in the plane with at most k edge crossings. Although this problem is in general notoriously difficult, it is fixed- parameter tractable for the parameter k [Grohe]. This suggests a closely related question of whether this problem has a polynomial kernel, meaning whether every instance of cr(G)<=k can be in polynomial time reduced to an equivalent instance of size polynomial in k (and independent of |G|). We answer this question in the negative. Along the proof we show that the tile crossing number problem of twisted planar tiles is NP-hard, which has been an open problem for some time, too, and then employ the complexity technique of cross-composition. Our result holds already for the special case of graphs obtained from planar graphs by adding one edge.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

FO Model Checking on Posets of Bounded Width

Over the past two decades the main focus of research into first-order (FO) model checking algorithms have been sparse relational structures-culminating in the FPT-algorithm by Grohe, Kreutzer and Siebertz for FO model checking of nowhere dense classes of graphs [STOC'14], with dense structures starting to attract attention only recently. Bova, Ganian and Szeider [LICS'14] initiated the study of the complexity of FO model checking on partially ordered sets (posets). Bova, Ganian and Szeider showed that model checking existential FO logic is fixed-parameter tractable (FPT) on posets of bounded width, where the width of a poset is the size of the largest antichain in the poset. The existence of an FPT algorithm for general FO model checking on posets of bounded width, however, remained open. We resolve this question in the positive by giving an algorithm that takes as its input an $n$-element poset $\cal P$ of width $w$ and an FO logic formula $ϕ$, and determines whether $ϕ$ holds on $\cal P$ in time $f(ϕ,w)\cdot n^2$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Inserting Multiple Edges into a Planar Graph

Let $G$ be a connected planar (but not yet embedded) graph and $F$ a set of additional edges not yet in $G$. The {multiple edge insertion} problem (MEI) asks for a drawing of $G+F$ with the minimum number of pairwise edge crossings, such that the subdrawing of $G$ is plane. An optimal solution to this problem approximates the crossing number of the graph $G+F$. Finding an exact solution to MEI is NP-hard for general $F$, but linear time solvable for the special case of $|F|=1$ (SODA01, Algorithmica) or when all of $F$ are incident to a new vertex (SODA09). The complexity for general $F$ but with constant $k=|F|$ was open, but algorithms both with relative and absolute approximation guarantees have been presented (SODA11, ICALP11). We show that the problem is fixed parameter tractable (FPT) in $k$ for biconnected $G$, or if the cut vertices of $G$ have degrees bounded by a constant. We give the first exact algorithm for this problem; it requires only $O(|V(G)|)$ time for any constant $k$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Kernelization Using Structural Parameters on Sparse Graph Classes

Meta-theorems for polynomial (linear) kernels have been the subject of intensive research in parameterized complexity. Heretofore, meta-theorems for linear kernels exist on graphs of bounded genus, $H$-minor-free graphs, and $H$-topological-minor-free graphs. To the best of our knowledge, no meta-theorems for polynomial kernels are known for any larger sparse graph classes; e.g., for classes of bounded expansion or for nowhere dense ones. In this paper we prove such meta-theorems for the two latter cases. More specifically, we show that graph problems that have finite integer index (FII) have linear kernels on graphs of bounded expansion when parameterized by the size of a modulator to constant-treedepth graphs. For nowhere dense graph classes, our result yields almost-linear kernels. While our parameter may seem rather strong, we argue that a linear kernelization result on graphs of bounded expansion with a weaker parameter (than treedepth modulator) would fail to include some of the problems covered by our framework. Moreover, we only require the problems to have FII on graphs of constant treedepth. This allows us to prove linear kernels for problems such as Longest Path/Cycle, Exact $s,t$-Path, Treewidth, and Pathwidth, which do not have FII on general graphs (and the first two not even on bounded treewidth graphs).

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On Hardness of the Joint Crossing Number

The Joint Crossing Number problem asks for a simultaneous embedding of two disjoint graphs into one surface such that the number of edge crossings (between the two graphs) is minimized. It was introduced by Negami in 2001 in connection with diagonal flips in triangulations of surfaces, and subsequently investigated in a general form for small-genus surfaces. We prove that all of the commonly considered variants of this problem are NP-hard already in the orientable surface of genus 6, by a reduction from a special variant of the anchored crossing number problem of Cabello and Mohar.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Strategy Synthesis in Adversarial Patrolling Games

Patrolling is one of the central problems in operational security. Formally, a patrolling problem is specified by a set $U$ of nodes (admissible defender's positions), a set $T \subseteq U$ of vulnerable targets, an admissible defender's moves over $U$, and a function which to every target assigns the time needed to complete an intrusion at it. The goal is to design an optimal strategy for a defender who is moving from node to node and aims at detecting possible intrusions at the targets. The goal of the attacker is to maximize the probability of a successful attack. We assume that the attacker is adversarial, i.e., he knows the strategy of the defender and can observe her moves. We prove that the defender has an optimal strategy for every patrolling problem. Further, we show that for every $\varepsilon$ > 0, there exists a finite-memory $\varepsilon$-optimal strategy for the defender constructible in exponential time, and we observe that such a strategy cannot be computed in polynomial time unless P=NP. Then we focus ourselves to unrestricted defender's moves. Here, a patrolling problem is fully determined by its signature, the number of targets of each attack length. We bound the maximal probability of successfully defended attacks. Then, we introduce a decomposition method which allows to split a given patrolling problem $G$ into smaller subproblems and construct a defender's strategy for $G$ by "composing" the strategies constructed for these subproblems. Finally, for patrolling problems with $T = U$ and a well-formed signature, we give an exact classification of all sufficiently connected environments where the defender can achieve the same value as in the fully connected uniform environment. This result is useful for designing "good" environments where the defender can act optimally.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Tree-depth and Vertex-minors

In a recent paper, Kwon and Oum claim that every graph of bounded rank-width is a pivot-minor of a graph of bounded tree-width (while the converse has been known true already before). We study the analogous questions for "depth" parameters of graphs, namely for the tree-depth and related new shrub-depth. We show that shrub-depth is monotone under taking vertex-minors, and that every graph class of bounded shrub-depth can be obtained via vertex-minors of graphs of bounded tree-depth. We also consider the same questions for bipartite graphs and pivot-minors.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Detours in Scope-Based Route Planning

We study a dynamic scenario of the static route planning problem in road networks. Particularly, we put accent on the most practical dynamic case - increased edge weights (up to infinity). We show how to enhance the scope-based route planning approach presented at ESA'11 to intuitively by-pass closures by detours. Three variants of a detour "admissibility" are presented - from a simple one with straightforward implementation through its enhanced version to a full and very complex variant variant which always returns an optimal detour.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Lower Bounds on the Complexity of MSO1 Model-Checking

One of the most important algorithmic meta-theorems is a famous result by Courcelle, which states that any graph problem definable in monadic second-order logic with edge-set quantifications (i.e., MSO2 model-checking) is decidable in linear time on any class of graphs of bounded tree-width. Recently, Kreutzer and Tazari proved a corresponding complexity lower-bound - that MSO2 model-checking is not even in XP wrt. the formula size as parameter for graph classes that are subgraph-closed and whose tree-width is poly-logarithmically unbounded. Of course, this is not an unconditional result but holds modulo a certain complexity-theoretic assumption, namely, the Exponential Time Hypothesis (ETH). In this paper we present a closely related result. We show that even MSO1 model-checking with a fixed set of vertex labels, but without edge-set quantifications, is not in XP wrt. the formula size as parameter for graph classes which are subgraph-closed and whose tree-width is poly-logarithmically unbounded unless the non-uniform ETH fails. In comparison to Kreutzer and Tazari; $(1)$ we use a stronger prerequisite, namely non-uniform instead of uniform ETH, to avoid the effectiveness assumption and the construction of certain obstructions used in their proofs; and $(2)$ we assume a different set of problems to be efficiently decidable, namely MSO1-definable properties on vertex labeled graphs instead of MSO2-definable properties on unlabeled graphs. Our result has an interesting consequence in the realm of digraph width measures: Strengthening the recent result, we show that no subdigraph-monotone measure can be "algorithmically useful", unless it is within a poly-logarithmic factor of undirected tree-width.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

How Not to Characterize Planar-emulable Graphs

We investigate the question of which graphs have planar emulators (a locally-surjective homomorphism from some finite planar graph) -- a problem raised already in Fellows' thesis (1985) and conceptually related to the better known planar cover conjecture by Negami (1986). For over two decades, the planar emulator problem lived poorly in a shadow of Negami's conjecture--which is still open--as the two were considered equivalent. But, in the end of 2008, a surprising construction by Rieck and Yamashita falsified the natural "planar emulator conjecture", and thus opened a whole new research field. We present further results and constructions which show how far the planar-emulability concept is from planar-coverability, and that the traditional idea of likening it to projective embeddability is actually very out-of-place. We also present several positive partial characterizations of planar-emulable graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Are there any good digraph width measures?

Several different measures for digraph width have appeared in the last few years. However, none of them shares all the "nice" properties of treewidth: First, being \emph{algorithmically useful} i.e. admitting polynomial-time algorithms for all $\MS1$-definable problems on digraphs of bounded width. And, second, having nice \emph{structural properties} i.e. being monotone under taking subdigraphs and some form of arc contractions. As for the former, (undirected) $\MS1$ seems to be the least common denominator of all reasonably expressive logical languages on digraphs that can speak about the edge/arc relation on the vertex set.The latter property is a necessary condition for a width measure to be characterizable by some version of the cops-and-robber game characterizing the ordinary treewidth. Our main result is that \emph{any reasonable} algorithmically useful and structurally nice digraph measure cannot be substantially different from the treewidth of the underlying undirected graph. Moreover, we introduce \emph{directed topological minors} and argue that they are the weakest useful notion of minors for digraphs.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Better algorithms for satisfiability problems for formulas of bounded rank-width

We provide a parameterized polynomial algorithm for the propositional model counting problem #SAT, the runtime of which is single-exponential in the rank-width of a formula. Previously, analogous algorithms have been known -- e.g.~[Fischer, Makowsky, and Ravve] -- with a single-exponential dependency on the clique-width of a formula. Our algorithm thus presents an exponential runtime improvement (since clique-width reaches up to exponentially higher values than rank-width), and can be of practical interest for small values of rank-width. We also provide an algorithm for the MAX-SAT problem along the same lines.

0 citations0 reviewsNo code linkedOpen access