1 Search Results for "Ogasawara, Tomoaki"

Document

DOI: 10.4230/LIPIcs.STACS.2018.41

On the Power of Tree-Depth for Fully Polynomial FPT Algorithms

Authors: Yoichi Iwata, Tomoaki Ogasawara, and Naoto Ohsaka

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract

There are many classical problems in P whose time complexities have not been improved over the past decades. Recent studies of "Hardness in P" have revealed that, for several of such problems, the current fastest algorithm is the best possible under some complexity assumptions. To bypass this difficulty, the concept of "FPT inside P" has been introduced. For a problem with the current best time complexity O(n^c), the goal is to design an algorithm running in k^{O(1)}n^{c'} time for a parameter k and a constant c'<c. In this paper, we investigate the complexity of graph problems in P parameterized by tree-depth, a graph parameter related to tree-width. We show that a simple divide-and-conquer method can solve many graph problems, including Weighted Matching, Negative Cycle Detection, Minimum Weight Cycle, Replacement Paths, and 2-hop Cover, in O(td m) time or O(td (m+nlog n)) time, where td is the tree-depth of the input graph. Because any graph of tree-width tw has tree-depth at most (tw+1)log_2 n, our algorithms also run in O(tw mlog n) time or O(tw (m+nlog n)log n) time. These results match or improve the previous best algorithms parameterized by tree-width. Especially, we solve an open problem of fully polynomial FPT algorithm for Weighted Matching parameterized by tree-width posed by Fomin et al. (SODA 2017).

Cite as

Yoichi Iwata, Tomoaki Ogasawara, and Naoto Ohsaka. On the Power of Tree-Depth for Fully Polynomial FPT Algorithms. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{iwata_et_al:LIPIcs.STACS.2018.41,
  author =	{Iwata, Yoichi and Ogasawara, Tomoaki and Ohsaka, Naoto},
  title =	{{On the Power of Tree-Depth for Fully Polynomial FPT Algorithms}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{41:1--41:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.41},
  URN =		{urn:nbn:de:0030-drops-85255},
  doi =		{10.4230/LIPIcs.STACS.2018.41},
  annote =	{Keywords: Fully Polynomial FPT Algorithm, Tree-Depth, Divide-and-Conquer}
}

Refine by Author
1 Iwata, Yoichi
1 Ogasawara, Tomoaki
1 Ohsaka, Naoto

Refine by Classification

Refine by Keyword
1 Divide-and-Conquer
1 Fully Polynomial FPT Algorithm
1 Tree-Depth

Refine by Type
1 document

Refine by Publication Year
1 2018

1 Search Results for "Ogasawara, Tomoaki"

On the Power of Tree-Depth for Fully Polynomial FPT Algorithms

Abstract

Cite as

Thanks for your feedback!

Could not send message