On the vertex cover $$P_3$$ P 3 problem parameterized by treewidth

Jianhua Tu (), Lidong Wu (), Jing Yuan () and Lei Cui ()
Additional contact information
Jianhua Tu: Beijing University of Chemical Technology
Lidong Wu: The University of Texas at Tyler
Jing Yuan: The University of Texas at Dallas
Lei Cui: The University of Texas at Dallas

Journal of Combinatorial Optimization, 2017, vol. 34, issue 2, No 7, 414-425

Abstract: Abstract Consider a graph G. A subset of vertices, F, is called a vertex cover $$P_t$$ P t ( $$VCP_t$$ V C P t ) set if every path of order t contains at least one vertex in F. Finding a minimum $$VCP_t$$ V C P t set in a graph is is NP-hard for any integer $$t\ge 2$$ t ≥ 2 and is called the $$MVCP_3$$ M V C P 3 problem. In this paper, we study the parameterized algorithms for the $$MVCP_3$$ M V C P 3 problem when the underlying graph G is parameterized by the treewidth. Given an n-vertex graph together with its tree decomposition of width at most p, we present an algorithm running in time $$4^{p}\cdot n^{O(1)}$$ 4 p · n O ( 1 ) for the $$MVCP_3$$ M V C P 3 problem. Moreover, we show that for the $$MVCP_3$$ M V C P 3 problem on planar graphs, there is a subexponential parameterized algorithm running in time $$2^{O(\sqrt{k})}\cdot n^{O(1)}$$ 2 O ( k ) · n O ( 1 ) where k is the size of the optimal solution.

Keywords: Graph algorithms; Parameterized complexity; Vertex cover $$P_3$$ P 3 problem; Tree decomposition; Treewidth (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-016-9999-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:34:y:2017:i:2:d:10.1007_s10878-016-9999-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-016-9999-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().