An algorithm for Independent Set and $k$-Path Vertex Cover in $P_t$-free graphs

Christoph Brause
TU Bergakademie Freiberg

PDF

Minisymposium: VERTEX COLOURINGS AND FORBIDDEN SUBGRAPHS

Content: The Maximum Independent Set Problem (MISP for short) and the Minimum $k$-Path Vertex Cover Problem (M$k$PVCP for short) are known to be NP-hard [2,1]. For the first problem, there exists lots of graph classes in terms of forbidden subgraphs, where polynomial algorithms compute optimal solutions. A celebrated result of Lokshtanov et al. [3] states that we can solve the MISP for $P_5$-free graphs in polynomial time. Unfortunately, for larger forbidden paths, the complexity is unknown. In this talk we will analyze an algorithm computing a maximum independent set in $P_t$-free graphs for $t\geq 6$. Furthermore, we will consider relations between the MISP and the M$k$PVCP, which gives nearly identical results for the solvability of both problems. \vspace{5mm} \noindent{\bf References:} \begin{itemize} \item[{[1]}] B.~Bresar, F.~Kardos, J.~Katrenic, and G.~Semanisin. \newblock Minimum k-path vertex cover. \newblock {\em Discrete Applied Mathematics}, 159(12):1189--1195, 2011. \item[{[2]}] M.~R. Garey and D.~S. Johnson. \newblock ``{S}trong'' {NP}-{C}ompleteness {R}esults: {M}otivation, {E}xamples, and {I}mplications. \newblock {\em J. ACM}, 25(3):499--508, July 1978. \item[{[3]}] D.~Lokshtanov, M.~Vatshelle, and Y.~Villanger. \newblock Independent set in {P}5-{F}ree {G}raphs in {P}olynomial {T}ime. \newblock accepted for publication. \end{itemize}

Back to all abstracts