# 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}