Fixed-Parameter Tractability for Directed Graph Treewidth
Abstract
The tree-width of an undirected graph G is a measure of how similar G is to a tree. An analogous definition is also known for directed graphs. For constant k, we improve on a known result and show an FPT algorithm that decides whether the tree-width of a directed graph D is at most 3k − 2 or if it admits a haven of order k.
References
Chen, J., Liu, Y., and Lu, S. (2007). Directed feedback vertex set problem is fpt. In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs, number 07281 in Dagstuhl Seminar Proceedings. Internationales Begegnungsund Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany.
Chitnis, R., Hajiaghayi, M., and Marx, D. (2011). Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. abs/1110.0259.
Cook, W. and Seymour, P. (2003). Tour merging via branch-decompositions. J. on Computing, 15:233–248.
Courcelle, B. (1990). The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Information and Computation, 85(1):12 – 75.
Demaine, D., Fomin, V., Hajiaghayi, M., and Thilikos, M. (2005). Subexponential parameterized algorithms on bounded-genus graphs and h-minor-free graphs. J. ACM, 52(6):866–893.
Demaine, E. and Hajiaghayi, M. (2004). Fast algorithms for hard graph problems: Bidimensionality, minors, and local treewidth. Graph drawing, pages 517–533.
Erbacher, R., Jaeger, T., Talele, N., and Teutsch, J. (2014). Directed multicut with linearly ordered terminals. CoRR, abs/1407.7498.
Fomin, F., Lokshtanov, D., Raman, V., and Surabh, S. (2011). Bidimensionality and eptas. ACM-SIAM Symposium on discrete algorithms (SODA), pages 748–759.
Fomin, F., Lokshtanov, D., Surabh, S., and Thilikos, D. (2010). Bidimensionality and kernels. ACM-SIAM Symposium on discrete algorithms (SODA), pages 503–510.
Johnson, T., Robertson, N., Seymour, P., and Thomas, R. (2001). Directed tree-width. Journal of combinatorial theory, series B, 82(01):138–154.
Kawarabayashi, K. and Kreutzer, S. (2015). The directed grid theorem. In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC ’15, pages 655–664, New York, NY, USA. ACM.
Koster, A., van Hoesel, S., and Kolen, A. (1999). Solving frequency assignment problems via tree-decomposition. Broersma, H.J. et al 6th Twente workshop on graphs and combinatorial optimization. Univ. of Twente, Enschede, Netherlands, 3.
Reed, B. (1997). Tree width and tangles: A new connectivity measure and some applications. R. Bailey, editor, Surveys in Combinatorics, pages 87–162.
Reed, B. (1999). Introducing directed tree-width. Electronic notes in discrete mathematics, 03:222–229.
Robertson, N. and Seymour, P. (1986). Graph minors v. excluding a planar graph. Journal of combinatorial theory, series B, 41(01):92–114.
Chitnis, R., Hajiaghayi, M., and Marx, D. (2011). Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. abs/1110.0259.
Cook, W. and Seymour, P. (2003). Tour merging via branch-decompositions. J. on Computing, 15:233–248.
Courcelle, B. (1990). The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Information and Computation, 85(1):12 – 75.
Demaine, D., Fomin, V., Hajiaghayi, M., and Thilikos, M. (2005). Subexponential parameterized algorithms on bounded-genus graphs and h-minor-free graphs. J. ACM, 52(6):866–893.
Demaine, E. and Hajiaghayi, M. (2004). Fast algorithms for hard graph problems: Bidimensionality, minors, and local treewidth. Graph drawing, pages 517–533.
Erbacher, R., Jaeger, T., Talele, N., and Teutsch, J. (2014). Directed multicut with linearly ordered terminals. CoRR, abs/1407.7498.
Fomin, F., Lokshtanov, D., Raman, V., and Surabh, S. (2011). Bidimensionality and eptas. ACM-SIAM Symposium on discrete algorithms (SODA), pages 748–759.
Fomin, F., Lokshtanov, D., Surabh, S., and Thilikos, D. (2010). Bidimensionality and kernels. ACM-SIAM Symposium on discrete algorithms (SODA), pages 503–510.
Johnson, T., Robertson, N., Seymour, P., and Thomas, R. (2001). Directed tree-width. Journal of combinatorial theory, series B, 82(01):138–154.
Kawarabayashi, K. and Kreutzer, S. (2015). The directed grid theorem. In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC ’15, pages 655–664, New York, NY, USA. ACM.
Koster, A., van Hoesel, S., and Kolen, A. (1999). Solving frequency assignment problems via tree-decomposition. Broersma, H.J. et al 6th Twente workshop on graphs and combinatorial optimization. Univ. of Twente, Enschede, Netherlands, 3.
Reed, B. (1997). Tree width and tangles: A new connectivity measure and some applications. R. Bailey, editor, Surveys in Combinatorics, pages 87–162.
Reed, B. (1999). Introducing directed tree-width. Electronic notes in discrete mathematics, 03:222–229.
Robertson, N. and Seymour, P. (1986). Graph minors v. excluding a planar graph. Journal of combinatorial theory, series B, 41(01):92–114.
Published
2018-07-26
How to Cite
MAIA, A. Karolinna; LOPES, Raul; CAMPOS, Victor.
Fixed-Parameter Tractability for Directed Graph Treewidth. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (ETC), 3. , 2018, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2018
.
p. 105-108.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2018.3163.
