zbMATH — the first resource for mathematics

Fixed parameter complexity of distance constrained labeling and uniform channel assignment problems. (extended abstract). (English) Zbl 06622020
Dinh, Thang N. (ed.) et al., Computing and combinatorics. 22nd international conference, COCOON 2016, Ho Chi Minh City, Vietnam, August 2–4, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-42633-4/pbk; 978-3-319-42634-1/ebook). Lecture Notes in Computer Science 9797, 67-78 (2016).
Summary: We study computational complexity of the class of distance-constrained graph labeling problems from the fixed parameter tractability point of view. The parameters studied are neighborhood diversity and clique width.
We rephrase the distance constrained graph labeling problem as a specific uniform variant of the Channel Assignment problem and show that this problem is fixed parameter tractable when parameterized by the neighborhood diversity together with the largest weight. Consequently, every \(L(p_1, p_2,\dots, p_k)\)-labeling problem is FPT when parameterized by the neighborhood diversity, the maximum \(p_i\) and \(k\).
Finally, we show that the uniform variant of the Channel Assignment problem becomes NP-complete when generalized to graphs of bounded clique width.
For the entire collection see [Zbl 1342.68014].
68Rxx Discrete mathematics in relation to computer science
Full Text: DOI
[1] Bodlaender, H.L., Kloks, T., Tan, R.B., van Leeuwen, J.: \[ \lambda \] -Coloring of graphs. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, pp. 395–406. Springer, Heidelberg (2000) · Zbl 0982.05050 · doi:10.1007/3-540-46541-3_33
[2] Chang, G.J., Kuo, D.: The \[ L(2,1) \] -labeling problem on graphs. SIAM J. Discret. Math. 9(2), 309–316 (1996) · Zbl 0860.05064 · doi:10.1137/S0895480193245339
[3] Corneil, D.C., Rotics, U.: On the relationship between clique-width and treewidth. SIAM J. Comput. 34(4), 825–847 (2005) · Zbl 1069.05067 · doi:10.1137/S0097539701385351
[4] Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discret. Appl. Math. 101(1–3), 77–114 (2000) · Zbl 0958.05105 · doi:10.1016/S0166-218X(99)00184-5
[5] Fiala, J., Golovach, P.A., Kratochvíl, J.: Distance constrained labelings of graphs of bounded treewidth. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 360–372. Springer, Heidelberg (2005) · Zbl 1082.68080 · doi:10.1007/11523468_30
[6] Fiala, J., Golovach, P.A., Kratochvíl, J.: Computational complexity of the distance constrained labeling problem for trees (extended abstract). In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 294–305. Springer, Heidelberg (2008) · Zbl 1153.68390 · doi:10.1007/978-3-540-70575-8_25
[7] Fiala, J., Golovach, P.A., Kratochvíl, J.: Parameterized complexity of coloring problems: treewidth versus vertex cover. Theor. Comput. Sci. 412(23), 2513–2523 (2011) · Zbl 1216.68127 · doi:10.1016/j.tcs.2010.10.043
[8] Fiala, J., Kratochvíl, J., Kloks, T.: Fixed-parameter complexity of \[ \lambda \] -labelings. Discret. Appl. Math. 113(1), 59–72 (2001) · Zbl 0982.05085 · doi:10.1016/S0166-218X(00)00387-5
[9] Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Intractability of clique-width parameterizations. SIAM J. Comput. 39(5), 1941–1956 (2010) · Zbl 1207.68161 · doi:10.1137/080742270
[10] Frank, A., Tardos, É.: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7(1), 49–65 (1987) · Zbl 0641.90067 · doi:10.1007/BF02579200
[11] Gajarský, J., Lampis, M., Ordyniak, S.: Parameterized algorithms for modular-width. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 163–176. Springer, Heidelberg (2013) · Zbl 1406.68080 · doi:10.1007/978-3-319-03898-8_15
[12] Ganian, R., Obdržálek, J.: Expanding the expressive power of monadic second-order logic on restricted graph classes. In: Lecroq, T., Mouchard, L. (eds.) IWOCA 2013. LNCS, vol. 8288, pp. 164–177. Springer, Heidelberg (2013) · Zbl 1284.68463 · doi:10.1007/978-3-642-45278-9_15
[13] Griggs, J.R., Yeh, R.K.: Labelling graphs with a condition at distance 2. SIAM J. Discret. Math. 5(4), 586–595 (1992) · Zbl 0767.05080 · doi:10.1137/0405048
[14] Gurski, F., Wanke, E.: The NLC-width and clique-width for powers of graphs of bounded tree-width. Discret. Appl. Math. 157(4), 583–595 (2009) · Zbl 1173.05342 · doi:10.1016/j.dam.2008.08.031
[15] Kobler, D., Rotics, U.: Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract). In: 12th ACM-SIAM of the Symposium on Discrete Algorithms, SODA 2001, Washington, pp. 468–476 (2001) · Zbl 0999.05092
[16] Král, D.: The channel assignment problem with variable weights. SIAM J. Discret. Math. 20(3), 690–704 (2006) · Zbl 1146.94003 · doi:10.1137/040619636
[17] Lampis, M.: Algorithmic meta-theorems for restrictions of treewidth. Algorithmica 64(1), 19–37 (2012) · Zbl 1252.68154 · doi:10.1007/s00453-011-9554-x
[18] Lenstra Jr., H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538–548 (1983) · Zbl 0524.90067 · doi:10.1287/moor.8.4.538
[19] McDiarmid, C., Reed, B.: Channel assignment on graphs of bounded treewidth. Discret. Math. 273(1–3), 183–192 (2003) · Zbl 1029.05150 · doi:10.1016/S0012-365X(03)00236-X
[20] Škvarek, M.: The channel assignment problem for series-parallel graphs. Bachelor’s thesis, Charles University, Prague (2010). (in Czech)
[21] Wanke, E.: \[ k \] -NLC graphs and polynomial algorithms. Discret. Appl. Math. 54(2–3), 251–266 (1994) · Zbl 0812.68106 · doi:10.1016/0166-218X(94)90026-4
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.