Jana Novotná
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Jana Novotná has a total of 30 co-authors. Here are the top co-authors by number of shared publications:
- Tomáš Masařík
University of Warsaw, Warsaw, Poland
6 shared publications - Martin Töpfer
Charles University
4 shared publications - Matěj Konečný
Charles University
4 shared publications - Daniël Paulusma
Durham University, Durham, UK
3 shared publications Jakub Pekárek
Charles University
3 shared publications- Karolina Okrasa
Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Warsaw, Poland
3 shared publications
Latest Publications
- Open Access
- 10 July 2023
- Published by Wiley in Journal of Graph Theory
- Vol. 104 (4) , 769-810
Clique‐width: Harnessing the power of atoms
Many NP‐complete graph problems are polynomial‐time solvable on graph classes of bounded clique‐width. Several of these problems are polynomial‐time solvable on a hereditary graph class if they are so on the atoms (graphs with no clique cut‐set) of . Hence, we initiate a systematic study into boundedness of clique‐width of atoms of hereditary graph classes. A graph is ‐free if is not an induced subgraph of , and it is ‐free if it is both ‐free and ‐free. A class of ‐free graphs has bounded clique‐width if and only if its atoms have this property. This is no longer true for ‐free graphs, as evidenced by one known example. We prove the existence of another such pair and classify the boundedness of clique‐width on ‐free atoms for all but 18 cases.
- 10 July 2023
- Published by Wiley in Journal of Graph Theory
- Vol. 104 (4) , 769-810
Open AccessClique‐width: Harnessing the power of atoms
Many NP‐complete graph problems are polynomial‐time solvable on graph classes of bounded clique‐width. Several of these problems are polynomial‐time solvable on a hereditary graph class if they are so on the atoms (graphs with no clique cut‐set) of . Hence, we initiate a systematic study into boundedness of clique‐width of atoms of hereditary graph classes. A graph is ‐free if is not an induced subgraph of , and it is ‐free if it is both ‐free and ‐free. A class of ‐free graphs has bounded clique‐width if and only if its atoms have this property. This is no longer true for ‐free graphs, as evidenced by one known example. We prove the existence of another such pair and classify the boundedness of clique‐width on ‐free atoms for all but 18 cases.
- Open Access
- 15 February 2022
- Published by Springer Nature in Algorithmica
- Vol. 84 (6) , 1526-1547
On 3-Coloring of ($2P_4,C_5$)-Free GraphsThe 3-coloring of hereditary graph classes has been a deeply-researched problem in the last decade. A hereditary graph class is characterized by a (possibly infinite) list of minimal forbidden induced subgraphs $$H_1,H_2,\ldots $$ ; the graphs in the class are called $$(H_1,H_2,\ldots )$$ -free. The complexity of 3-coloring is far from being understood, even for classes defined by a few small forbidden induced subgraphs. For H-free graphs, the complexity is settled for any H on up to seven vertices. There are only two unsolved cases on eight vertices, namely $$2P_4$$ and $$P_8$$ . For $$P_8$$ -free graphs, some partial results are known, but to the best of our knowledge, $$2P_4$$ -free graphs have not been explored yet. In this paper, we show that the 3-coloring problem is polynomial-time solvable on $$(2P_4,C_5)$$ -free graphs.- 15 February 2022
- Published by Springer Nature in Algorithmica
- Vol. 84 (6) , 1526-1547
Open AccessOn 3-Coloring of ($2P_4,C_5$)-Free GraphsThe 3-coloring of hereditary graph classes has been a deeply-researched problem in the last decade. A hereditary graph class is characterized by a (possibly infinite) list of minimal forbidden induced subgraphs $$H_1,H_2,\ldots $$ ; the graphs in the class are called $$(H_1,H_2,\ldots )$$ -free. The complexity of 3-coloring is far from being understood, even for classes defined by a few small forbidden induced subgraphs. For H-free graphs, the complexity is settled for any H on up to seven vertices. There are only two unsolved cases on eight vertices, namely $$2P_4$$ and $$P_8$$ . For $$P_8$$ -free graphs, some partial results are known, but to the best of our knowledge, $$2P_4$$ -free graphs have not been explored yet. In this paper, we show that the 3-coloring problem is polynomial-time solvable on $$(2P_4,C_5)$$ -free graphs. - Open Access
- 1 February 2022
- Published by Springer Nature in Algorithmica
- Vol. 84 (8) , 2271-2291
Vertex Deletion into Bipartite Permutation Graphs
A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines $$\ell _1$$ and $$\ell _2$$ , one on each. A bipartite permutation graph is a permutation graph which is bipartite. In this paper we study the parameterized complexity of the bipartite permutation vertex deletion problem, which asks, for a given n-vertex graph, whether we can remove at most k vertices to obtain a bipartite permutation graph. This problem is $$\mathsf {NP}$$ -complete by the classical result of Lewis and Yannakakis [20]. We analyze the structure of the so-called almost bipartite permutation graphs which may contain holes (large induced cycles) in contrast to bipartite permutation graphs. We exploit the structural properties of the shortest hole in a such graph. We use it to obtain an algorithm for the bipartite permutation vertex deletion problem with running time $${\mathcal {O}}(9^k \cdot n^9)$$ , and also give a polynomial-time 9-approximation algorithm.- 1 February 2022
- Published by Springer Nature in Algorithmica
- Vol. 84 (8) , 2271-2291
Open AccessVertex Deletion into Bipartite Permutation Graphs
A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines $$\ell _1$$ and $$\ell _2$$ , one on each. A bipartite permutation graph is a permutation graph which is bipartite. In this paper we study the parameterized complexity of the bipartite permutation vertex deletion problem, which asks, for a given n-vertex graph, whether we can remove at most k vertices to obtain a bipartite permutation graph. This problem is $$\mathsf {NP}$$ -complete by the classical result of Lewis and Yannakakis [20]. We analyze the structure of the so-called almost bipartite permutation graphs which may contain holes (large induced cycles) in contrast to bipartite permutation graphs. We exploit the structural properties of the shortest hole in a such graph. We use it to obtain an algorithm for the bipartite permutation vertex deletion problem with running time $${\mathcal {O}}(9^k \cdot n^9)$$ , and also give a polynomial-time 9-approximation algorithm. - Open Access
- 2 September 2021
- Published by Springer Nature in Algorithmica
- Vol. 83 (12) , 3649-3680
${\mathcal {U}}$-Bubble Model for Mixed Unit Interval Graphs and Its Applications: The MaxCut Problem RevisitedInterval 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 richer class of graphs. In particular, mixed unit interval graphs may contain a claw as an induced subgraph, as opposed 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 Boyacı et al. (Inf Process Lett 121:29–33, 2017. 10.1016/j.ipl.2017.01.007). 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.
- 2 September 2021
- Published by Springer Nature in Algorithmica
- Vol. 83 (12) , 3649-3680
Open Access${\mathcal {U}}$-Bubble Model for Mixed Unit Interval Graphs and Its Applications: The MaxCut Problem RevisitedInterval 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 richer class of graphs. In particular, mixed unit interval graphs may contain a claw as an induced subgraph, as opposed 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 Boyacı et al. (Inf Process Lett 121:29–33, 2017. 10.1016/j.ipl.2017.01.007). 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.
- Open Access
Vertex deletion into bipartite permutation graphs
A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines $l_1$ and $l_2$, one on each. A bipartite permutation graph is a permutation graph which is bipartite. In this paper we study the parameterized complexity of the bipartite permutation vertex deletion problem, which asks, for a given n-vertex graph, whether we can remove at most k vertices to obtain a bipartite permutation graph. This problem is NP-complete by the classical result of Lewis and Yannakakis. We analyze the structure of the so-called almost bipartite permutation graphs which may contain holes (large induced cycles) in contrast to bipartite permutation graphs. We exploit the structural properties of the shortest hole in a such graph. We use it to obtain an algorithm for the bipartite permutation vertex deletion problem with running time $O(9^k\cdot n^9)$, and also give a polynomial-time 9-approximation algorithm.Open AccessVertex deletion into bipartite permutation graphs
A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines $l_1$ and $l_2$, one on each. A bipartite permutation graph is a permutation graph which is bipartite. In this paper we study the parameterized complexity of the bipartite permutation vertex deletion problem, which asks, for a given n-vertex graph, whether we can remove at most k vertices to obtain a bipartite permutation graph. This problem is NP-complete by the classical result of Lewis and Yannakakis. We analyze the structure of the so-called almost bipartite permutation graphs which may contain holes (large induced cycles) in contrast to bipartite permutation graphs. We exploit the structural properties of the shortest hole in a such graph. We use it to obtain an algorithm for the bipartite permutation vertex deletion problem with running time $O(9^k\cdot n^9)$, and also give a polynomial-time 9-approximation algorithm. - Open Access
- 31 July 2020
- Published by Springer Nature in Algorithmica
- Vol. 83 (8) , 2634-2650
Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs
Let $${\mathcal {C}}$$ and $${\mathcal {D}}$$ be hereditary graph classes. Consider the following problem: given a graph $$G\in {\mathcal {D}}$$ , find a largest, in terms of the number of vertices, induced subgraph ofGthat belongs to $${\mathcal {C}}$$ . We prove that it can be solved in $$2^{o(n)}$$ time, wherenis the number of vertices ofG, if the following conditions are satisfied: the graphs in $${\mathcal {C}}$$ are sparse, i.e., they have linearly many edges in terms of the number of vertices; the graphs in $${\mathcal {D}}$$ admit balanced separators of size governed by their density, e.g., $${\mathcal {O}}(\varDelta )$$ or $${\mathcal {O}}(\sqrt{m})$$ , where $$\varDelta$$ andmdenote the maximum degree and the number of edges, respectively; and the considered problem admits a single-exponential fixed-parameter algorithm when parameterized by the treewidth of the input graph. This leads, for example, to the following corollaries for specific classes $${\mathcal {C}}$$ and $${\mathcal {D}}$$ : a largest induced forest in a $$P_t$$ -free graph can be found in $$2^{\tilde{{\mathcal {O}}}(n^{2/3})}$$ time, for every fixedt; and a largest induced planar graph in a string graph can be found in $$2^{\tilde{{\mathcal {O}}}(n^{2/3})}$$ time.- 31 July 2020
- Published by Springer Nature in Algorithmica
- Vol. 83 (8) , 2634-2650
Open AccessSubexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs
Let $${\mathcal {C}}$$ and $${\mathcal {D}}$$ be hereditary graph classes. Consider the following problem: given a graph $$G\in {\mathcal {D}}$$ , find a largest, in terms of the number of vertices, induced subgraph ofGthat belongs to $${\mathcal {C}}$$ . We prove that it can be solved in $$2^{o(n)}$$ time, wherenis the number of vertices ofG, if the following conditions are satisfied: the graphs in $${\mathcal {C}}$$ are sparse, i.e., they have linearly many edges in terms of the number of vertices; the graphs in $${\mathcal {D}}$$ admit balanced separators of size governed by their density, e.g., $${\mathcal {O}}(\varDelta )$$ or $${\mathcal {O}}(\sqrt{m})$$ , where $$\varDelta$$ andmdenote the maximum degree and the number of edges, respectively; and the considered problem admits a single-exponential fixed-parameter algorithm when parameterized by the treewidth of the input graph. This leads, for example, to the following corollaries for specific classes $${\mathcal {C}}$$ and $${\mathcal {D}}$$ : a largest induced forest in a $$P_t$$ -free graph can be found in $$2^{\tilde{{\mathcal {O}}}(n^{2/3})}$$ time, for every fixedt; and a largest induced planar graph in a string graph can be found in $$2^{\tilde{{\mathcal {O}}}(n^{2/3})}$$ time. - Open Access
- 25 January 2020
- Published by Springer Nature in Algorithmica
- Vol. 82 (7) , 1833-1858
Colouring (Pr + Ps)-Free Graphs
The k-Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for a fixed integer k such that no two adjacent vertices are coloured alike. If each vertex u must be assigned a colour from a prescribed list $$L(u)\subseteq \{1,\ldots ,k\},$$ then we obtain the List k-Colouring problem. A graph G is H-free if G does not contain H as an induced subgraph. We continue an extensive study into the complexity of these two problems for H-free graphs. The graph $$P_r+P_s$$ is the disjoint union of the r-vertex path $$P_r$$ and the s-vertex path $$P_s.$$ We prove that List 3-Colouring is polynomial-time solvable for $$(P_2+P_5)$$ -free graphs and for $$(P_3+P_4)$$ -free graphs. Combining our results with known results yields complete complexity classifications of 3-Colouring and List 3-Colouring on H-free graphs for all graphs H up to seven vertices.- 25 January 2020
- Published by Springer Nature in Algorithmica
- Vol. 82 (7) , 1833-1858
Open AccessColouring (Pr + Ps)-Free Graphs
The k-Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for a fixed integer k such that no two adjacent vertices are coloured alike. If each vertex u must be assigned a colour from a prescribed list $$L(u)\subseteq \{1,\ldots ,k\},$$ then we obtain the List k-Colouring problem. A graph G is H-free if G does not contain H as an induced subgraph. We continue an extensive study into the complexity of these two problems for H-free graphs. The graph $$P_r+P_s$$ is the disjoint union of the r-vertex path $$P_r$$ and the s-vertex path $$P_s.$$ We prove that List 3-Colouring is polynomial-time solvable for $$(P_2+P_5)$$ -free graphs and for $$(P_3+P_4)$$ -free graphs. Combining our results with known results yields complete complexity classifications of 3-Colouring and List 3-Colouring on H-free graphs for all graphs H up to seven vertices. - 9 December 2019
- Published by Springer Nature in Journal of Optimization Theory and Applications
- Vol. 184 (2) , 565-580
Duality Gap in Interval Linear Programming
- 9 December 2019
- Published by Springer Nature in Journal of Optimization Theory and Applications
- Vol. 184 (2) , 565-580
Duality Gap in Interval Linear Programming
- 1 September 2018
- Published by Elsevier in Journal of Discrete Algorithms
- Vol. 52-53, 29-37
Minimal sum labeling of graphs
- 1 September 2018
- Published by Elsevier in Journal of Discrete Algorithms
- Vol. 52-53, 29-37
Minimal sum labeling of graphs