Publications (22)
Recognition and Isomorphism of Proper -graphs in FPT-time
Deniz AÄaoÄlu ÃaÄırıcı, Peter Zeman
An -graph is an intersection graph of connected subgraphs of a suitable subdivision of a fixed graph . Many important classes of graphs, including interval graphs, circular-a…
Beyond circular-arc graphs -- recognizing lollipop graphs and medusa graphs
Deniz AÄaoÄlu ÃaÄırıcı, Onur ÃaÄırıcı, Jan Derbisz +5
In 1992 Biró, Hujter and Tuza introduced, for every fixed connected graph , the class of -graphs, defined as the intersection graphs of connected subgraphs of some subdivisi…
Extending Partial Representations of Unit Circular-arc Graphs
Peter Zeman
The partial representation extension problem, introduced by KlavÃk et al. (2011), generalizes the recognition problem. In this short note we show that this problem is NP-complete…
Automorphism Groups of Comparability Graphs
Pavel KlavÃk, Peter Zeman
Comparability graphs are graphs which have transitive orientations. The dimension of a poset is the least number of linear orders whose intersection gives this poset. The dimension…
Free Inhomogeneous Wreath Product of Quantum Groups
Josse van Dobben de Bruyn, Amaury Freslon, Prem Nigam Kar +2
We introduce the free inhomogeneous wreath product of compact matrix quantum groups, which generalizes the free wreath product (Bichon 2004). We use this to present a general techn…
Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable
Vikraman Arvind, Roman Nedela, Ilia Ponomarenko +1
The computational complexity of the graph isomorphism problem is considered to be a major open problem in theoretical computer science. It is known that testing isomorphism of chor…
Extending Partial Representations of Circular-Arc Graphs
JiÅÃ Fiala, Ignaz Rutter, Peter Stumpf +1
The partial representation extension problem generalizes the recognition problem for classes of graphs defined in terms of vertex representations. We exhibit circular-arc graphs as…
Existence and nonexistence of commutativity gadgets for entangled CSPs
Eric Culf, Josse van Dobben de Bruyn, Matthijs Vernooij +1
Commutativity gadgets allow NP-hardness proofs for classical constraint satisfaction problems (CSPs) to be carried over to undecidability proofs for the corresponding entangled CSP…
Quantum Sabidussi's Theorem
Arnbjörg SoffÃa Ãrnadóttir, Josse van Dobben de Bruyn, Prem Nigam Kar +2
Sabidussi's theorem [Duke Math. J. 28, 1961] gives necessary and sufficient conditions under which the automorphism group of a lexicographic product of two graphs is a wreath produ…
Discrete and Fast Fourier Transform Made Clear
Peter Zeman
Fast Fourier transform was included in the Top 10 Algorithms of 20th Century by Computing in Science & Engineering. In this paper, we provide a new simple derivation of both the di…
On -Topological Intersection Graphs
Steven Chaplick, Martin Töpfer, Jan VobornÃk +1
Biró et al. (1992) introduced -graphs, intersection graphs of connected subgraphs of a subdivision of a graph . They are related to many classes of geometric intersection gr…
Testing isomorphism of circular-arc graphs in polynomial time
Roman Nedela, Ilia Ponomarenko, Peter Zeman
A graph is said to be circular-arc if the vertices can be associated with arcs of a circle so that two vertices are adjacent if and only if the corresponding arcs overlap. It is pr…
Automorphism Groups of Geometrically Represented Graphs
Pavel KlavÃk, Peter Zeman
We describe a technique to determine the automorphism group of a geometrically represented graph, by understanding the structure of the induced action on all geometric representati…
Automorphism groups of maps in linear time
Ken-ichi Kawarabayashi, Bojan Mohar, Roman Nedela +1
By a map we mean a -cell decomposition of a closed compact surface, i.e., an embedding of a graph such that every face is homeomorphic to an open disc. Automorphism of a map can…
Circle Graph Isomorphism in Almost Linear Time
VÃt Kalisz, Pavel KlavÃk, Peter Zeman
Circle graphs are intersection graphs of chords of a circle. In this paper, we present a new algorithm for the circle graph isomorphism problem running in time wh…
On the Weisfeiler-Leman dimension of some polyhedral graphs
Haiyan Li, Ilia Ponomarenko, Peter Zeman
Let be a positive integer, a graph with vertex set , and the coloring of the Cartesian -power , obtained by the -dimensional Weisfeiler-Lema…
Quantum polymorphism characterisation of commutativity gadgets in all quantum models
Eric Culf, Josse van Dobben de Bruyn, Peter Zeman
Commutativity gadgets provide a technique for lifting classical reductions between constraint satisfaction problems to quantum-sound reductions between the corresponding nonlocal g…
Jordan-like characterization of automorphism groups of planar graphs
Pavel KlavÃk, Roman Nedela, Peter Zeman
We investigate automorphism groups of planar graphs. The main result is a complete recursive description of all abstract groups that can be realized as automorphism groups of plana…
NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability
Prem Nigam Kar, David E. Roberson, Tim Seppelt +1
ManÄinska and Roberson [FOCS'20] showed that two graphs are quantum isomorphic if and only if they admit the same number of homomorphisms from any planar graph. Atserias et al. [J…
Quantum automorphism groups of trees
Josse van Dobben de Bruyn, Prem Nigam Kar, David E. Roberson +2
We give a characterisation of quantum automorphism groups of trees. In particular, for every tree, we show how to iteratively construct its quantum automorphism group using free pr…
Graph Isomorphism Restricted by Lists
Pavel Klavik, Dušan Knop, Peter Zeman
The complexity of graph isomorphism (GraphIso) is a famous unresolved problem in theoretical computer science. For graphs and , it asks whether they are the same up to a rel…
Combinatorial Problems on -graphs
Steven Chaplick, Peter Zeman
Biró, Hujter, and Tuza introduced the concept of -graphs (1992), intersection graphs of connected subgraphs of a subdivision of a graph . They naturally generalize many impo…