Thumbnail
Access Restriction
Open

Author Chitnis, Rajesh ♦ Hajiaghayi, Mohammadtaghi ♦ Marx, Daniel
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Description In SODA
Given a vertex-weighted directed graph G = (V,E) and a set T = {t1, t2,... tk} of k terminals, the objective of the STRONGLY CONNECTED STEINER SUBGRAPH (SCSS) problem is to find a vertex set H ⊆V of minimum weight such that G[H] contains a ti → t j path for each i 6 = j. The problem is NP-hard, but Feldman and Ruhl (FOCS ’99; SICOMP ’06) gave a novel nO(k) algorithm for the SCSS problem, where n is the number of vertices in the graph and k is the number of terminals. We explore how much easier the problem becomes on planar directed graphs. • Our main algorithmic result is a 2O(k logk) ·nO( k) al-gorithm for planar SCSS, which is an improvement of a factor of O( k) in the exponent over the algo-rithm of Feldman and Ruhl. • Our main hardness result is a matching lower bound for our algorithm: we show that planar SCSS does not have an f (k) · no( k) algorithm for any com-putable function f, unless the Exponential Time Hy-pothesis (ETH) fails. The algorithm eventually relies on the excluded grid theorem for planar graphs, but we stress that it is not simply a straightforward application of treewidth-based techniques: we need several layers of abstraction to arrive to a problem formulation where the speedup due to planarity can be exploited. To obtain the lower bound matching the algorithm, we need a delicate construction of gadgets arranged in a grid-like fashion to tightly control the number of terminals in the created instance.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2014-01-01