Structural Parameterizations for Boxicity
Tóm tắt
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 \ge 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 Adiga et al. (2010), 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 Adiga et al. (2010) that Boxicity remains NP-complete even on graphs of constant treewidth.
Tài liệu tham khảo
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)
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)
Adiga, A., Bhowmick, D., Chandran, L.S.: Boxicity and poset dimension. SIAM J. Discrete Math. 25(4), 1687–1698 (2011)
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)
Asplund, E., Grünbaum, B.: On a coloring problem. Math. Scand 8, 181–188 (1960)
Bielecki, A.: Problem 56. Colloq. Math. 1, 333 (1948)
Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305–1317 (1996)
Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett. 58(4), 171–176 (1996)
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)
Chandran, L.S., Sivadasan, N.: Boxicity and treewidth. J. Comb. Theory Ser. B 97(5), 733–744 (2007)
Courcelle, B.: The monadic second-order logic of graphs I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12–75 (1990)
Cozzens, M.: Higher and multi-dimensional analogues of interval graphs. Ph.d. thesis, Department of Mathematics, Rutgers University, New Brunswick (1981)
Diestel, R.: Graph Theory, 4th edn. Springer, Berlin (2010)
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)
Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, Berlin (2013)
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)
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)
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)
Kratochvíl, J.: A special planar satisfiability problem and a consequence of its NP-completeness. Discrete Appl. Math. 52(3), 233–252 (1994)
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)
Roberts, F.S.: On the boxicity and cubicity of a graph. In: Recent Progresses in Combinatorics, pp. 301–310. Academic Press (1969)
Scheinerman, E.: Intersection classes and multiple intersection parameters. Ph.D. thesis, Princeton University (1984)
Spinrad, J.: Efficient Graph Representations. American Mathematical Society, Fields Institute monographs, Providence (2003)
Thomassen, C.: Interval representations of planar graphs. J. Comb. Theory Ser. B 40(1), 9–20 (1986)
Yannakakis, M.: The complexity of the partial order dimension problem. SIAM J. Algebr. Discrete Methods 3(3), 351–358 (1982)