10 papers
Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds
Sujoy Bhore, Liana Khazaliya, Fionn Mc Inerney
Kirkpatrick et al. [ALT 2019] and Fallat et al. [JMLR 2023] introduced non-clashing teaching and proved that it is the most efficient batch machine teaching model satisfying the co…
The Computational Complexity of Positive Non-Clashing Teaching in Graphs
Robert Ganian, Liana Khazaliya, Fionn Mc Inerney +1
We study the classical and parameterized complexity of computing the positive non-clashing teaching dimension of a set of concepts, that is, the smallest number of examples per con…
Crossing Number is NP-hard for Constant Path-width (and Tree-width)
Petr Hliněný, Liana Khazaliya
The crossing number of a graph is the minimum number of edge crossings that a graph can have when drawn in the plane. Determining this number, known as the Crossing Number problem,…
Metric Dimension and Geodetic Set Parameterized by Vertex Cover
Florent Foucaud, Esther Galby, Liana Khazaliya +4
For a graph , a subset is called a resolving set of if, for any two vertices , there exists a vertex such that . T…
The -Planar Edge Completion Problem is Fixed-Parameter Tractable
Liana Khazaliya, Philipp Kindermann, Giuseppe Liotta +2
The problem of deciding whether a biconnected planar digraph can be augmented to become an -planar graph by adding a set of oriented edges i…
Upward and Orthogonal Planarity are W[1]-hard Parameterized by Treewidth
Bart M. P. Jansen, Liana Khazaliya, Philipp Kindermann +3
Upward planarity testing and Rectilinear planarity testing are central problems in graph drawing. It is known that they are both NP-complete, but XP when parameterized by treewidth…
Consistency-Checking Problems: A Gateway to Parameterized Sample Complexity
Robert Ganian, Liana Khazaliya, Kirill Simonov
Recently, Brand, Ganian and Simonov introduced a parameterized refinement of the classical PAC-learning sample complexity framework. A crucial outcome of their investigation is tha…
Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
Florent Foucaud, Esther Galby, Liana Khazaliya +4
Treewidth (tw) is an important parameter that, when bounded, yields tractability for many problems. For example, graph problems expressible in Monadic Second Order (MSO) logic and…
Extending Orthogonal Planar Graph Drawings is Fixed-Parameter Tractable
Sujoy Bhore, Robert Ganian, Liana Khazaliya +2
The task of finding an extension to a given partial drawing of a graph while adhering to constraints on the representation has been extensively studied in the literature, with well…
Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
Esther Galby, Liana Khazaliya, Fionn Mc Inerney +2
For a graph , a subset is called a \emph{resolving set} if for any two vertices , there exists a vertex such that …