Algorithms for Partition of Some Class of Graphs under Compaction and Vertex-Compaction
Tóm tắt
The compaction problem is to partition the vertices of an input graph G onto the vertices of a fixed target graph H, such that adjacent vertices of G remain adjacent in H, and every vertex and non-loop edge of H is covered by some vertex and edge of G respectively, i.e., the partition is a homomorphism of G
onto
H (except the loop edges). Various computational complexity results, including both NP-completeness and polynomial time solvability, have been presented earlier for this problem for various classes of target graphs H. In this paper, we pay attention to the input graphs G, and present polynomial time algorithms for the problem for some class of input graphs, keeping the target graph H general as any reflexive or irreflexive graph. Our algorithms also give insight as for which instances of the input graphs, the problem could possibly be NP-complete for certain target graphs. With the help of our results, we are able to further refine the structure of the input graph that would be necessary for the problem to be possibly NP-complete, when the target graph is a cycle. Thus, when the target graph is a cycle, we enhance the class of input graphs for which the problem is polynomial time solvable. We also present analogous results for a variation of the compaction problem, which we call the vertex-compaction problem. Using our results, we also provide important relationships between compaction, retraction, and vertex-compaction to cycles.
Tài liệu tham khảo
Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. MIT Press/McGraw-Hill, Cambridge/New York (1990)
Feder, T., Hell, P.: List homomorphisms to reflexive graphs. J. Comb. Theory, Ser. B 72, 236–250 (1998)
Feder, T., Hell, P., Huang, J.: List homomorphisms and circular arc graphs. Combinatorica 19, 487–505 (1999)
Feder, T., Hell, P., Klein, S., Motwani, R.: Complexity of graph partition problems. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), Atlanta, Georgia (1999)
Feder, T., Hell, P., Klein, S., Motwani, R.: List partitions. SIAM J. Discrete Math. 16, 449–478 (2003)
Gutjahr, W., Welzl, E., Woeginger, G.: Polynomial graph-colorings. Discrete Appl. Math. 35, 29–45 (1992)
Harary, F.: Graph Theory. Addison-Wesley, Reading (1969)
Hell, P., Nesetril, J.: On the complexity of H-colouring. J. Comb. Theory, Ser. B 48, 92–110 (1990)
Hell, P., Nesetril, J., Zhu, X.: Duality and polynomial testing of tree homomorphisms. Trans. Am. Math. Soc. 348, 1281–1297 (1996)
Mackworth, A.K.: Consistency in networks of relations. Artif. Intell. 8, 99–118 (1977)
Mackworth, A.K., Freuder, E.C.: The complexity of some polynomial network consistency algorithms for constraint satisfaction problems. Artif. Intell. 25, 65–74 (1985)
Montanari, U.: In: Networks of constraints: fundamental properties and applications to picture processing. Information Sciences, vol. 7, pp. 95–132 (1974)
Vikas, N.: Computational complexity of compaction to cycles. In: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Baltimore, Maryland (1999)
Vikas, N.: Connected and loosely connected list homomorphisms. In: 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Cesky Krumlov, Czech Republic. Lecture Notes in Computer Science, vol. 2573, pp. 399–412. Springer, Heidelberg (2002)
Vikas, N.: Computational complexity of compaction to reflexive cycles. SIAM J. Comput. 32, 253–280 (2003)
Vikas, N.: Computational complexity of compaction to irreflexive cycles. J. Comput. Syst. Sci. 68, 473–496 (2004)
Vikas, N.: Compaction, retraction, and constraint satisfaction. SIAM J. Comput. 33, 761–782 (2004)
Vikas, N.: Computational complexity classification of partition under compaction and retraction. In: Tenth Annual International Computing and Combinatorics Conference (COCOON), Jeju Island, Korea. Lecture Notes in Computer Science, vol. 3106, pp. 380–391. Springer, Heidelberg (2004)
Vikas, N.: A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices. J. Comput. Syst. Sci. 71, 406–439 (2005)
Vikas, N.: Computational complexity of partition of graphs under vertex-compaction. Manuscript (2009)
Vikas, N.: Algorithms for partition of some class of graphs under compaction. In: Seventeenth Annual International Computing and Combinatorics Conference (COCOON 2011), Dallas, Texas, USA, August 14–16, 2011. Lecture Notes in Computer Science, vol. 6842, pp. 319–330. Springer, Heidelberg (2011)