DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2010.2459

Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs

Authors: Frederic Dorn, Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract

In this paper we make the first step beyond bidimensionality by obtaining subexponential time algorithms for problems on directed graphs. We develop two different methods to achieve subexponential time parameterized algorithms for problems on sparse directed graphs. We exemplify our approaches with two well studied problems. For the first problem, $k$-Leaf Out-Branching, which is to find an oriented spanning tree with at least $k$ leaves, we obtain an algorithm solving the problem in time $2^{\cO(\sqrt{k} \log k)} n+ n^{\cO(1)}$ on directed graphs whose underlying undirected graph excludes some fixed graph $H$ as a minor. For the special case when the input directed graph is planar, the running time can be improved to $2^{\cO(\sqrt{k} )}n + n^{\cO(1)}$. The second example is a generalization of the {\sc Directed Hamiltonian Path} problem, namely $k$-Internal Out-Branching, which is to find an oriented spanning tree with at least $k$ internal vertices. We obtain an algorithm solving the problem in time $2^{\cO(\sqrt{k} \log k)} + n^{\cO(1)}$ on directed graphs whose underlying undirected graph excludes some fixed apex graph $H$ as a minor. Finally, we observe that for any $\ve>0$, the $k$-Directed Path problem is solvable in time $\cO((1+\ve)^k n^{f(\ve)})$, where $f$ is some function of $\ve$. Our methods are based on non-trivial combinations of obstruction theorems for undirected graphs, kernelization, problem specific combinatorial structures and a layering technique similar to the one employed by Baker to obtain PTAS for planar graphs.

Cite as

Frederic Dorn, Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh. Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 251-262, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{dorn_et_al:LIPIcs.STACS.2010.2459,
  author =	{Dorn, Frederic and Fomin, Fedor V. and Lokshtanov, Daniel and Raman, Venkatesh and Saurabh, Saket},
  title =	{{Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{251--262},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2459},
  URN =		{urn:nbn:de:0030-drops-24599},
  doi =		{10.4230/LIPIcs.STACS.2010.2459},
  annote =	{Keywords: Parameterized Subexponential Algorithms, Directed Graphs, Out-Branching, Internal Out-Branching}
}

Document

DOI: 10.4230/LIPIcs.STACS.2010.2460

Planar Subgraph Isomorphism Revisited

Authors: Frederic Dorn

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract

The problem of {\sc Subgraph Isomorphism} is defined as follows: Given a \emph{pattern} $H$ and a \emph{host graph} $G$ on $n$ vertices, does $G$ contain a subgraph that is isomorphic to $H$? Eppstein [SODA 95, J'GAA 99] gives the first linear time algorithm for subgraph isomorphism for a fixed-size pattern, say of order $k$, and arbitrary planar host graph, improving upon the $O(n^{\sqrt{k}})$-time algorithm when using the ``Color-coding'' technique of Alon et al [J'ACM 95]. Eppstein's algorithm runs in time $k^{O(k)} n$, that is, the dependency on $k$ is superexponential. We improve the running time to $2^{O(k)} n$, that is, single exponential in $k$ while keeping the term in $n$ linear. Next to deciding subgraph isomorphism, we can construct a solution and count all solutions in the same asymptotic running time. We may enumerate $\omega$ subgraphs with an additive term $O(\omega k)$ in the running time of our algorithm. We introduce the technique of ``embedded dynamic programming'' on a suitably structured graph decomposition, which exploits the number and topology of the underlying drawings of the subgraph pattern (rather than of the host graph).

Cite as

Frederic Dorn. Planar Subgraph Isomorphism Revisited. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 263-274, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{dorn:LIPIcs.STACS.2010.2460,
  author =	{Dorn, Frederic},
  title =	{{Planar Subgraph Isomorphism Revisited}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{263--274},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2460},
  URN =		{urn:nbn:de:0030-drops-24605},
  doi =		{10.4230/LIPIcs.STACS.2010.2460},
  annote =	{Keywords: Graph algorithms, Subgraph Isomorphism, NP-hard problems, Dynamic programming, Topological graph theory}
}

Search Results

Documents authored by Dorn, Frederic

Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs

Abstract

Cite as

Planar Subgraph Isomorphism Revisited

Abstract

Cite as

Thanks for your feedback!

Could not send message