×

Structural parameterizations for boxicity. (English) Zbl 1339.68200

Summary: The boxicity of a graph \(G\) is the least integer \(d\) such that \(G\) has an intersection model of axis-aligned \(d\)-dimensional boxes. Boxicity, the problem of deciding whether a given graph \(G\) has boxicity at most \(d\), is NP-complete for every fixed \(d \geq 2\). We show that Boxicity is fixed-parameter tractable when parameterized by the cluster vertex deletion number of the input graph. This generalizes the result of A. Adiga et al. [Lect. Notes Comput. Sci. 6506, 366–377 (2010; Zbl 1310.68154)], that Boxicity is fixed-parameter tractable in the vertex cover number. Moreover, we show that Boxicity admits an additive 1-approximation when parameterized by the pathwidth of the input graph. Finally, we provide evidence in favor of a conjecture of [loc. cit.] that Boxicity remains NP-complete even on graphs of constant treewidth.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C62 Graph representations (geometric and intersection representations, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity

Citations:

Zbl 1310.68154
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adiga, A., Babu, J., Chandran, L.S.: Polynomial time and parameterized approximation algorithms for boxicity. In: Proceedings of the 7th International Symposium on Algorithms and Computation (IPEC 2012), LNCS 7535, pp. 135-146 (2012) · Zbl 1335.68294
[2] Adiga, A., Bhowmick, D., Chandran, L.S.: The hardness of approximating the boxicity, cubicity and threshold dimension of a graph. Discrete Appl. Math. 158(16), 1719-1726 (2010) · Zbl 1208.05140 · doi:10.1016/j.dam.2010.06.017
[3] Adiga, A., Bhowmick, D., Chandran, L.S.: Boxicity and poset dimension. SIAM J. Discrete Math. 25(4), 1687-1698 (2011) · Zbl 1241.05098 · doi:10.1137/100786290
[4] Adiga, A., Chitnis, R., Saurabh, S.: Parameterized algorithms for boxicity. In: Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC 2010), LNCS 6506, pp. 366-377 (2010) · Zbl 1310.68154
[5] Asplund, E., Grünbaum, B.: On a coloring problem. Math. Scand 8, 181-188 (1960) · Zbl 0095.17002
[6] Bielecki, A.: Problem 56. Colloq. Math. 1, 333 (1948)
[7] Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305-1317 (1996) · Zbl 0864.68074 · doi:10.1137/S0097539793251219
[8] Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett. 58(4), 171-176 (1996) · Zbl 0875.68702 · doi:10.1016/0020-0190(96)00050-6
[9] Chalermsook, P., Laekhanukit, B., Nanongkai, D.: Graph products revisited: tight approximation hardness of induced matching, poset dimension and more. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), pp. 1557-1576 (2013) · Zbl 1423.05140
[10] Chandran, L.S., Sivadasan, N.: Boxicity and treewidth. J. Comb. Theory Ser. B 97(5), 733-744 (2007) · Zbl 1121.05091 · doi:10.1016/j.jctb.2006.12.004
[11] Courcelle, B.: The monadic second-order logic of graphs I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12-75 (1990) · Zbl 0722.03008
[12] Cozzens, M.: Higher and multi-dimensional analogues of interval graphs. Ph.d. thesis, Department of Mathematics, Rutgers University, New Brunswick (1981)
[13] Diestel, R.: Graph Theory, 4th edn. Springer, Berlin (2010) · Zbl 1204.05001 · doi:10.1007/978-3-642-14279-6
[14] Doucha, M., Kratochvíl, J.: Cluster vertex deletion: a parameterization between vertex cover and clique-width. In: Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS 2012), LNCS 7464, pp. 348-359 (2012) · Zbl 1365.68278
[15] Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, Berlin (2013) · Zbl 1358.68006 · doi:10.1007/978-1-4471-5559-1
[16] Fellows, M.R., Hermelin, D., Rosamond, F.A.: Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications. Algorithmica 64(1), 3-18 (2012) · Zbl 1264.05131 · doi:10.1007/s00453-011-9545-y
[17] Ganian, R.: Twin-cover: beyond vertex cover in parameterized algorithmics. In: Proceedings of the 6th International Symposium on Algorithms and Computation (IPEC 2011), LNCS 7112, pp. 259-271 (2011) · Zbl 1352.68105
[18] Kostochka, A.: Coloring intersection graphs of geometric figures with a given clique number. In: Pach, J, (ed.) Towards A Theory of Geometric Graphs, vol. 342 of Contemp. Math., pp. 127-138. Amer. Math. Soc. (2004) · Zbl 1064.05059
[19] Kratochvíl, J.: A special planar satisfiability problem and a consequence of its NP-completeness. Discrete Appl. Math. 52(3), 233-252 (1994) · Zbl 0810.68083 · doi:10.1016/0166-218X(94)90143-0
[20] Lekkerkerker, C., Boland, J.: Representation of a finite graph by a set of intervals on the real line. Fund. Math. 51(1), 45-64 (1962/1963) · Zbl 0105.17501
[21] Roberts, F.S.: On the boxicity and cubicity of a graph. In: Recent Progresses in Combinatorics, pp. 301-310. Academic Press (1969) · Zbl 0193.24301
[22] Scheinerman, E.: Intersection classes and multiple intersection parameters. Ph.D. thesis, Princeton University (1984)
[23] Spinrad, J.: Efficient Graph Representations. American Mathematical Society, Fields Institute monographs, Providence (2003) · Zbl 1033.05001
[24] Thomassen, C.: Interval representations of planar graphs. J. Comb. Theory Ser. B 40(1), 9-20 (1986) · Zbl 0595.05027 · doi:10.1016/0095-8956(86)90061-4
[25] Yannakakis, M.: The complexity of the partial order dimension problem. SIAM J. Algebr. Discrete Methods 3(3), 351-358 (1982) · Zbl 0516.06001 · doi:10.1137/0603036
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.