Jan Kratochvíl

MFCS Conference 2025 Conference Paper

Computational Complexity of Covering Regular Trees

• Jan Bok
• Jirí Fiala 0001
• Nikola Jedlicková
• Jan Kratochvíl

A graph covering projection, also referred to as a locally bijective homomorphism, is a mapping between the vertices and edges of two graphs that preserves incidences and is a local bijection. This concept originates in topological graph theory but has also found applications in combinatorics and theoretical computer science. In this paper we consider undirected graphs in the most general setting - graphs may contain multiple edges, loops, and semi-edges. This is in line with recent trends in topological graph theory and mathematical physics. We advance the study of the computational complexity of the H-Cover problem, which asks whether an input graph allows a covering projection onto a parameter graph H. The quest for a complete characterization started in 1990’s. Several results for simple graphs or graphs without semi-edges have been known, the role of semi-edges in the complexity setting has started to be investigated only recently. One of the most general known NP-hardness results states that H-Cover is NP-complete for every simple connected regular graph of valency greater than two. We complement this result by considering regular graphs H arising from connected acyclic graphs by adding semi-edges. Namely, we prove that any graph obtained by adding semi-edges to the vertices of a tree making it a d-regular graph with d ≥ 3, defines an NP-complete graph covering problem. In line with the so called Strong Dichotomy Conjecture, we prove that the NP-hardness holds even for simple graphs on input.

ICML Conference 2024 Conference Paper

On a Combinatorial Problem Arising in Machine Teaching

• Joakim Sunde
• Brigt Arve Toppe Håvardstun
• Jan Kratochvíl
• Jan Arne Telle

We study a model of machine teaching where the teacher mapping is constructed from a size function on both concepts and examples. The main question in machine teaching is the minimum number of examples needed for any concept, the so-called teaching dimension. A recent paper (Ferri et al. , 2024) conjectured that the worst case for this model, as a function of the size of the concept class, occurs when the consistency matrix contains the binary representations of numbers from zero and up. In this paper we prove their conjecture. The result can be seen as a generalization of a theorem resolving the edge isoperimetry problem for hypercubes (Hart, 1976), and our proof is based on a lemma of (Graham, 1970).

MFCS Conference 2023 Conference Paper

Recognizing H-Graphs - Beyond Circular-Arc Graphs

• Deniz Agaoglu Çagirici
• Onur Çagirici
• Jan Derbisz
• Tim A. Hartmann
• Petr Hlinený
• Jan Kratochvíl
• Tomasz Krawczyk
• Peter Zeman 0001

In 1992 Biró, Hujter and Tuza introduced, for every fixed connected graph H, the class of H-graphs, defined as the intersection graphs of connected subgraphs of some subdivision of H. Such classes of graphs are related to many known graph classes: for example, K₂-graphs coincide with interval graphs, K₃-graphs with circular-arc graphs, the union of T-graphs, where T ranges over all trees, coincides with chordal graphs. Recently, quite a lot of research has been devoted to understanding the tractability border for various computational problems, such as recognition or isomorphism testing, in classes of H-graphs for different graphs H. In this work we undertake this research topic, focusing on the recognition problem. Chaplick, Töpfer, Voborník, and Zeman showed an XP-algorithm testing whether a given graph is a T-graph, where the parameter is the size of the tree T. In particular, for every fixed tree T the recognition of T-graphs can be solved in polynomial time. Tucker showed a polynomial time algorithm recognizing K₃-graphs (circular-arc graphs). On the other hand, Chaplick et al. showed also that for every fixed graph H containing two distinct cycles sharing an edge, the recognition of H-graphs is NP-hard. The main two results of this work narrow the gap between the NP-hard and 𝖯 cases of H-graph recognition. First, we show that the recognition of H-graphs is NP-hard when H contains two distinct cycles. On the other hand, we show a polynomial-time algorithm recognizing L-graphs, where L is a graph containing a cycle and an edge attached to it (which we call lollipop graphs). Our work leaves open the recognition problems of M-graphs for every unicyclic graph M different from a cycle and a lollipop.

MFCS Conference 2021 Conference Paper

Computational Complexity of Covering Multigraphs with Semi-Edges: Small Cases

• Jan Bok
• Jirí Fiala 0001
• Petr Hlinený
• Nikola Jedlicková
• Jan Kratochvíl

We initiate the study of computational complexity of graph coverings, aka locally bijective graph homomorphisms, for graphs with semi-edges. The notion of graph covering is a discretization of coverings between surfaces or topological spaces, a notion well known and deeply studied in classical topology. Graph covers have found applications in discrete mathematics for constructing highly symmetric graphs, and in computer science in the theory of local computations. In 1991, Abello et al. asked for a classification of the computational complexity of deciding if an input graph covers a fixed target graph, in the ordinary setting (of graphs with only edges). Although many general results are known, the full classification is still open. In spite of that, we propose to study the more general case of covering graphs composed of normal edges (including multiedges and loops) and so-called semi-edges. Semi-edges are becoming increasingly popular in modern topological graph theory, as well as in mathematical physics. They also naturally occur in the local computation setting, since they are lifted to matchings in the covering graph. We show that the presence of semi-edges makes the covering problem considerably harder; e. g. , it is no longer sufficient to specify the vertex mapping induced by the covering, but one necessarily has to deal with the edge mapping as well. We show some solvable cases and, in particular, completely characterize the complexity of the already very nontrivial problem of covering one- and two-vertex (multi)graphs with semi-edges. Our NP-hardness results are proven for simple input graphs, and in the case of regular two-vertex target graphs, even for bipartite ones. We remark that our new characterization results also strengthen previously known results for covering graphs without semi-edges, and they in turn apply to an infinite class of simple target graphs with at most two vertices of degree more than two. Some of the results are moreover proven in a more general setting (e. g. , finding k-tuples of pairwise disjoint perfect matchings in regular graphs, or finding equitable partitions of regular bipartite graphs).

MFCS Conference 2020 Conference Paper

U-Bubble Model for Mixed Unit Interval Graphs and Its Applications: The MaxCut Problem Revisited

• Jan Kratochvíl
• Tomás Masarík
• Jana Masaríková

Interval graphs, intersection graphs of segments on a real line (intervals), play a key role in the study of algorithms and special structural properties. Unit interval graphs, their proper subclass, where each interval has a unit length, has also been extensively studied. We study mixed unit interval graphs - a generalization of unit interval graphs where each interval has still a unit length, but intervals of more than one type (open, closed, semi-closed) are allowed. This small modification captures a much richer class of graphs. In particular, mixed unit interval graphs are not claw-free, compared to unit interval graphs. Heggernes, Meister, and Papadopoulos defined a representation of unit interval graphs called the bubble model which turned out to be useful in algorithm design. We extend this model to the class of mixed unit interval graphs and demonstrate the advantages of this generalized model by providing a subexponential-time algorithm for solving the MaxCut problem on mixed unit interval graphs. In addition, we derive a polynomial-time algorithm for certain subclasses of mixed unit interval graphs. We point out a substantial mistake in the proof of the polynomiality of the MaxCut problem on unit interval graphs by Boyaci, Ekim, and Shalom (2017). Hence, the time complexity of this problem on unit interval graphs remains open. We further provide a better algorithmic upper-bound on the clique-width of mixed unit interval graphs.

TCS Journal 2019 Journal Article

Cops, a fast robber and defensive domination on interval graphs

• Dariusz Dereniowski
• Tomáš Gavenčiak
• Jan Kratochvíl

The game of Cops and ∞-fast Robber is played by two players, one controlling c cops, the other one robber. The players alternate in turns: all the cops move at once to distance at most one each, the robber moves along any cop-free path. Cops win by sharing a vertex with the robber, the robber by avoiding capture indefinitely. The game was proposed with bounded robber speed by Fomin et al. in “Pursuing a fast robber on a graph”, generalizing a well-known game of Cops and Robber which has robber speed 1. We answer their open question about the computational complexity of the game on interval graphs with ∞-fast robber, showing it to be polynomially decidable. We also generalize the concept of k-defensive domination introduced by Farley and Proskurowski in “Defensive Domination” to A -defensive domination and use it as a main tool in our proof. The generalization allows specifying arbitrary attacks and limiting the number of defenders of each vertex. While this problem is NP-complete even for split graphs, we show that A -defensive domination is decidable in polynomial time on interval graphs.

TCS Journal 2017 Journal Article

MSOL restricted contractibility to planar graphs

• James Abello
• Pavel Klavík
• Jan Kratochvíl
• Tomáš Vyskočil

We study the computational complexity of graph planarization via edge contraction. The problem Contract asks whether there exists a set S of at most k edges that when contracted produces a planar graph. We work with a more general problem called P-RestrictedContract in which S, in addition, is required to satisfy a fixed MSOL formula P ( S, G ). We give an FPT algorithm in time O ( n 2 f ( k ) ) which solves P-RestrictedContract, where n is number of vertices of the graph and P ( S, G ) is (i) inclusion-closed and (ii) inert contraction-closed (where inert edges are the edges non-incident to any inclusion-minimal solution S). As a specific example, we can solve the ℓ-subgraph contractibility problem in which the edges of the set S are required to form disjoint connected subgraphs of size at most ℓ. This problem can be solved in time O ( n 2 f ′ ( k, ℓ ) ) using the general algorithm. We also show that for ℓ ≥ 2 the problem is NP -complete.

TCS Journal 2016 Journal Article

Computational complexity of covering three-vertex multigraphs

• Jan Kratochvíl
• Jan Arne Telle
• Marek Tesař

A covering projection from a graph G onto a graph H is a mapping of the vertices of G onto the vertices of H such that, for every vertex v of G, the neighborhood of v is mapped bijectively onto the neighborhood of its image. Moreover, if G and H are multigraphs, then this local bijection has to preserve multiplicities of the neighbors as well. The notion of covering projection stems from topology, but has found applications in areas such as the theory of local computation and construction of highly symmetric graphs. It provides a restrictive variant of the constraint satisfaction problem with additional symmetry constraints on the behavior of the homomorphisms of the structures involved. We investigate the computational complexity of the problem of deciding the existence of a covering projection from an input graph G to a fixed target graph H. Among other partial results this problem has been shown NP-hard for simple regular graphs H of valency greater than 2, and a full characterization of computational complexity has been shown for target multigraphs with 2 vertices. We extend the previously known results to the ternary case, i. e. , we give a full characterization of the computational complexity in the case of multigraphs with 3 vertices. We show that even in this case a P/NP-completeness dichotomy holds.

TCS Journal 2015 Journal Article

Extending partial representations of subclasses of chordal graphs

• Pavel Klavík
• Jan Kratochvíl
• Yota Otachi
• Toshiki Saitoh

Chordal graphs are intersection graphs of subtrees of a tree T. We investigate the complexity of the partial representation extension problem for chordal graphs. A partial representation specifies a tree T ′ and some pre-drawn subtrees of T ′. It asks whether it is possible to construct a representation inside a modified tree T which extends the partial representation (i. e. , keeps the pre-drawn subtrees unchanged). We consider four modifications of T ′ leading to vastly different problems: (i) T = T ′, (ii) T is a subdivision of T ′, (iii) T is a supergraph of T ′, and (iv) T ′ is a topological minor of T. In some cases, it is interesting to consider the complexity even when just T ′ is given and no subtree is pre-drawn. Also, we consider three well-known subclasses of chordal graphs: Proper interval graphs, interval graphs and path graphs. We give an almost complete complexity characterization. We further study the parametrized complexity of the problems when parametrized by the number of pre-drawn subtrees, the number of components of the input graph G and the size of the tree T ′. We describe an interesting relation with integer partition problems. The problem 3-Partition is used for all NP -completeness reductions. When the space in T ′ is limited, partial representation extension of proper interval graphs is “equivalent” to the BinPacking problem.

TCS Journal 2013 Journal Article

Fast exact algorithm for L ( 2, 1 ) -labeling of graphs

• Konstanty Junosza-Szaniawski
• Jan Kratochvíl
• Mathieu Liedloff
• Peter Rossmanith
• Paweł Rzążewski

An L ( 2, 1 ) -labeling of a graph is a mapping from its vertex set into nonnegative integers such that the labels assigned to adjacent vertices differ by at least 2, and labels assigned to vertices of distance 2 are different. The span of such a labeling is the maximum label used, and the L ( 2, 1 ) -span of a graph is the minimum possible span of its L ( 2, 1 ) -labelings. We show how to compute the L ( 2, 1 ) -span of a connected graph in time O ∗ ( 2. 648 8 n ). Previously published exact exponential time algorithms were gradually improving the base of the exponential function from 4 to the so far best known 3, with 3 itself seemingly having been the Holy Grail for quite a while. As concerns special graph classes, we are able to solve the problem in time O ∗ ( 2. 594 4 n ) for claw-free graphs, and in time O ∗ ( 2 n − r ( 2 + n r ) r ) for graphs having a dominating set of size r.

TCS Journal 2013 Journal Article

Preface

• Jiří Fiala
• Jan Kratochvíl
• Angsheng Li

MFCS Conference 2012 Conference Paper

Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width

• Martin Doucha
• Jan Kratochvíl

Abstract The cluster vertex deletion number of a graph is the minimum number of its vertices whose deletion results in a disjoint union of complete graphs. This generalizes the vertex cover number, provides an upper bound to the clique-width and is related to the previously studied notion of the twin cover of the graph under consideration. We study the fixed parameter tractability of basic graph theoretic problems related to coloring and Hamiltonicity parameterized by cluster vertex deletion number. Our results show that most of these problems remain fixed parameter tractable as well, and thus we push the borderline between tractability and intractability towards the clique-width parameter.

TCS Journal 2011 Journal Article

Parameterized complexity of coloring problems: Treewidth versus vertex cover

• Jiří Fiala
• Petr A. Golovach
• Jan Kratochvíl

We compare the fixed parameter complexity of various variants of coloring problems (including List Coloring, Precoloring Extension, Equitable Coloring, L ( p, 1 ) -Labeling and Channel Assignment) when parameterized by treewidth and by vertex cover number. In most (but not all) cases we conclude that parametrization by the vertex cover number provides a significant drop in the complexity of the problems.

TCS Journal 2010 Journal Article

Pursuing a fast robber on a graph

• Fedor V. Fomin
• Petr A. Golovach
• Jan Kratochvíl
• Nicolas Nisse
• Karol Suchan

The Cops and Robbers game as originally defined independently by Quilliot and by Nowakowski and Winkler in the 1980s has been much studied, but very few results pertain to the algorithmic and complexity aspects of it. In this paper we prove that computing the minimum number of cops that are guaranteed to catch a robber on a given graph is NP-hard and that the parameterized version of the problem is W[2]-hard; the proof extends to the case where the robber moves s time faster than the cops. We show that on split graphs, the problem is polynomially solvable if s = 1 but is NP-hard if s = 2. We further prove that on graphs of bounded cliquewidth the problem is polynomially solvable for s ≤ 2. Finally, we show that for planar graphs the minimum number of cops is unbounded if the robber is faster than the cops.

SODA Conference 2010 Conference Paper

Testing Planarity of Partially Embedded Graphs

• Patrizio Angelini
• Giuseppe Di Battista
• Fabrizio Frati
• Vít Jelínek
• Jan Kratochvíl
• Maurizio Patrignani
• Ignaz Rutter

MFCS Conference 2007 Conference Paper

Exact Algorithms for L (2, 1)-Labeling of Graphs

• Jan Kratochvíl
• Dieter Kratsch
• Mathieu Liedloff

Abstract The notion of distance constrained graph labelings, motivated by the Frequency Assignment Problem, reads as follows: A mapping from the vertex set of a graph G = ( V, E ) into an interval of integers [0. . k ] is an L (2, 1)-labeling of G of span k if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbor are mapped onto distinct integers. It is known that for any fixed k ≥ 4, deciding the existence of such a labeling is an NP-complete problem. We present exact exponential time algorithms that are faster than the naive O (( k + 1) n ) algorithm that would try all possible mappings. The improvement is best seen in the first NP-complete case of k = 4 – here the running time of our algorithm is O (1. 3161 n ).

SODA Conference 2006 Conference Paper

Max-tolerance graphs as intersection graphs: cliques, cycles, and recognition

• Michael Kaufmann 0001
• Jan Kratochvíl
• Katharina Anna Lehmann
• Amarendran Ramaswami Subramanian

TCS Journal 2003 Journal Article

Mixed hypergraphs with bounded degree: edge-coloring of mixed multigraphs

• Daniel Král’
• Jan Kratochvíl
• Heinz-Jürgen Voss

A mixed hypergraph H is a triple (V, C, D) where V is its vertex set and C and D are families of subsets of V (C-edges and D-edges). The degree of a vertex is the number of edges in which it is contained. A vertex coloring of H is proper if each C-edge contains two vertices with the same color and each D-edge contains two vertices with different colors. The feasible set of H is the set of all k's such that there exists a proper coloring using exactly k colors. The lower (upper) chromatic number of H is the minimum (maximum) number in the feasible set. We restrict our attention to mixed hypergraphs with maximum degree two; those with maximum degree three are not simpler than general ones. Mixed hypergraphs with maximum degree two were suggested as an interesting subclass of mixed hypergraphs in Voloshin (Austral. J. Combin. 11 (1995) 25–45). We prove that feasible sets of mixed hypergraphs with maximum degree two are intervals. We present a linear time algorithm for determining the lower chromatic number, a linear 5 3 -approximation algorithm and a polynomial 3 2 -approximation algorithm for the upper chromatic number. We prove that there is no PTAS for the upper chromatic number unless P=NP.

MFCS Conference 2001 Conference Paper

Complexity Note on Mixed Hypergraphs

• Daniel Král'
• Jan Kratochvíl
• Heinz-Jürgen Voss

Abstract A mixed hypergraph H is a triple ( V, \( \mathcal{C} \), \( \mathcal{D} \) ) where V is its vertex set and \( \mathcal{C} \) and \( \mathcal{D} \) are families of subsets of V, \( \mathcal{C} \) -edges and \( \mathcal{D} \) -edges. The degree of a vertex is the number of edges in which it is contained. A vertex coloring of H is proper if each \( \mathcal{C} \) -edge contains two vertices with the same color and each \( \mathcal{D} \) -edge contains two vertices with different colors. The feasible set of H is the set of all k ’s such that there exists a proper coloring using exactly k colors. The lower (upper) chromatic number of H is the minimum (maximum) number in the feasible set. We prove that it is NP-complete to decide whether the upper chromatic number of mixed hypergraphs with maximum degree two is at least a given k. We present polynomial time algorithms for mixed hypergraphs with maximum degree two to decide their colorability, to find a coloring using the number of colors equal to the lower chromatic number and we present a 5/3-aproximation algorithm for the upper chromatic number. We further prove that it is coNP-hard to decide whether the feasible set of a given general mixed hypergraph is an interval of integers.

SODA Conference 2000 Conference Paper

On the complexity of bicoloring clique hypergraphs of graphs (extended abstract)

• Jan Kratochvíl
• Zsolt Tuza

MFCS Conference 1988 Conference Paper

On the Computational Complexity of Codes in Graphs

• Jan Kratochvíl
• Mirko Krivánek

Abstract This paper linke to continuing research of the first author on codes in graphs [7–11]. Here codes are studied from the point of view of their computational complexity. It is shown that the problem of perfect code recognition is NP -complete even when resiricted to k-regular graphs (k≥4) or to 3-regular planar graphs. On the other hand in the case of trees and graphs of bounded tree-width an optimal ϑ(n) algorithm is developed. Some optimization problems are also investigated.