Search

In 1992 Bir\'{o}, 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$. 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\"{o}pfer, Voborn\'{\i}k, and Zeman showed, for every fixed tree $T$, a polynomial-time algorithm recognizing $T$-graphs. Tucker showed a polynomial time algorithm recognizing $K_3$-graphs (circular-arc graphs). On the other hand, Chaplick at al. showed that recognition of $H$-graphs is $NP$-hard if $H$ contains two different cycles sharing an edge. The main two results of this work narrow the gap between the $NP$-hard and $P$ cases of $H$-graphs recognition. First, we show that recognition of $H$-graphs is $NP$-hard when $H$ contains two different 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 ($L$-graphs are called lollipop graphs). Our work leaves open the recognition problems of $M$-graphs for every unicyclic graph $M$ different from a cycle and a lollipop. Other results of this work, which shed some light on the cases that remain open, are as follows. Firstly, the recognition of $M$-graphs, where $M$ is a fixed unicyclic graph, admits a polynomial time algorithm if we restrict the input to graphs containing particular holes (hence recognition of $M$-graphs is probably most difficult for chordal graphs). Secondly, the recognition of medusa graphs, which are defined as the union of $M$-graphs, where $M$ runs over all unicyclic graphs, is $NP$-complete.

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 the the bipartite permutation vertex deletion problem we ask 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 but it does admit an FPT algorithm parameterized by $k$. In this paper we study the kernelization of this problem and show that it admits a polynomial kernel with $O(k^{99})$ vertices.

A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines 𝓁₁ and 𝓁₂, 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 [John M. Lewis and Mihalis Yannakakis, 1980]. 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 f(k)n^O(1), and also give a polynomial-time 9-approximation algorithm., LIPIcs, Vol. 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020), pages 5:1-5:16