TY - GEN
T1 - A linear fixed parameter tractable algorithm for connected pathwidth
AU - Kanté, Mamadou Moustapha
AU - Paul, Christophe
AU - Thilikos, Dimitrios M.
N1 - Publisher Copyright:
© Mamadou Moustapha Kanté, Christophe Paul, and Dimitrios M. Thilikos.
PY - 2020/8/1
Y1 - 2020/8/1
N2 - The graph parameter of pathwidth can be seen as a measure of the topological resemblance of a graph to a path. A popular definition of pathwidth is given in terms of node search where we are given a system of tunnels (represented by a graph) that is contaminated by some infectious substance and we are looking for a search strategy that, at each step, either places a searcher on a vertex or removes a searcher from a vertex and where an edge is cleaned when both endpoints are simultaneously occupied by searchers. It was proved that the minimum number of searchers required for a successful cleaning strategy is equal to the pathwidth of the graph plus one. Two desired characteristics for a cleaning strategy is to be monotone (no recontamination occurs) and connected (clean territories always remain connected). Under these two demands, the number of searchers is equivalent to a variant of pathwidth called connected pathwidth. We prove that connected pathwidth is fixed parameter tractable, in particular we design a 2O(k2) · n time algorithm that checks whether the connected pathwidth of G is at most k. This resolves an open question by [Dereniowski, Osula, and Rzążewski, Finding small-width connected path-decompositions in polynomial time. Theor. Comput. Sci., 794:85–100, 2019]. For our algorithm, we enrich the typical sequence technique that is able to deal with the connectivity demand. Typical sequences have been introduced in [Bodlaender and Kloks. Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms, 21(2):358–402, 1996] for the design of linear parameterized algorithms for treewidth and pathwidth. While this technique has been later applied to other parameters, none of its advancements was able to deal with the connectivity demand, as it is a “global” demand that concerns an unbounded number of parts of the graph of unbounded size. The proposed extension is based on an encoding of the connectivity property that is quite versatile and may be adapted so to deliver linear parameterized algorithms for the connected variants of other width parameters as well. An immediate consequence of our result is a 2O(k2) · n time algorithm for the monotone and connected version of the edge search number.
AB - The graph parameter of pathwidth can be seen as a measure of the topological resemblance of a graph to a path. A popular definition of pathwidth is given in terms of node search where we are given a system of tunnels (represented by a graph) that is contaminated by some infectious substance and we are looking for a search strategy that, at each step, either places a searcher on a vertex or removes a searcher from a vertex and where an edge is cleaned when both endpoints are simultaneously occupied by searchers. It was proved that the minimum number of searchers required for a successful cleaning strategy is equal to the pathwidth of the graph plus one. Two desired characteristics for a cleaning strategy is to be monotone (no recontamination occurs) and connected (clean territories always remain connected). Under these two demands, the number of searchers is equivalent to a variant of pathwidth called connected pathwidth. We prove that connected pathwidth is fixed parameter tractable, in particular we design a 2O(k2) · n time algorithm that checks whether the connected pathwidth of G is at most k. This resolves an open question by [Dereniowski, Osula, and Rzążewski, Finding small-width connected path-decompositions in polynomial time. Theor. Comput. Sci., 794:85–100, 2019]. For our algorithm, we enrich the typical sequence technique that is able to deal with the connectivity demand. Typical sequences have been introduced in [Bodlaender and Kloks. Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms, 21(2):358–402, 1996] for the design of linear parameterized algorithms for treewidth and pathwidth. While this technique has been later applied to other parameters, none of its advancements was able to deal with the connectivity demand, as it is a “global” demand that concerns an unbounded number of parts of the graph of unbounded size. The proposed extension is based on an encoding of the connectivity property that is quite versatile and may be adapted so to deliver linear parameterized algorithms for the connected variants of other width parameters as well. An immediate consequence of our result is a 2O(k2) · n time algorithm for the monotone and connected version of the edge search number.
KW - Graph decompositions
KW - Graph searching
KW - Parameterized algorithms
KW - Pathwidth
KW - Typical sequences
UR - http://www.scopus.com/inward/record.url?scp=85092454927&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85092454927&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ESA.2020.64
DO - 10.4230/LIPIcs.ESA.2020.64
M3 - Conference contribution
AN - SCOPUS:85092454927
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 28th Annual European Symposium on Algorithms, ESA 2020
A2 - Grandoni, Fabrizio
A2 - Herman, Grzegorz
A2 - Sanders, Peter
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 28th Annual European Symposium on Algorithms, ESA 2020
Y2 - 7 September 2020 through 9 September 2020
ER -