क्लिक-चौड़ाई

असंयुक्त संघों, रीलेबलिंग और लेबल-जॉइन्स द्वारा क्लिक-चौड़ाई 3 के दूरी-वंशानुगत ग्राफ का निर्माण। वर्टेक्स लेबल को रंगों के रूप में दिखाया गया है।

ग्राफ़ सिद्धांत में, ग्राफ़ की क्लिक-चौड़ाई (अलग गणित) G एक पैरामीटर है जो ग्राफ़ की संरचनात्मक जटिलता का वर्णन करता है; इसका वृक्ष चौड़ाई से गहरा संबंध है, लेकिन ट्रीविड्थ के विपरीत यह घने ग्राफ़ के लिए छोटा हो सकता है।

इसे निर्माण के लिए आवश्यक ग्राफ़ लेबलिंग की न्यूनतम संख्या के रूप में परिभाषित किया गया है G निम्नलिखित 4 ऑपरेशनों के माध्यम से:

1. नए शिखर का निर्माण v लेबल के साथ i (द्वारा चिह्नित i(v))
2. दो लेबल वाले ग्राफ़ के ग्राफ़ का असंयुक्त संघ G और H (द्वारा चिह्नित $G\oplus H$)
3. लेबल वाले प्रत्येक शीर्ष पर एक किनारे से जुड़ना i लेबल किए गए प्रत्येक शीर्ष पर j (द्वारा चिह्नित η(i,j)), कहाँ i ≠ j
4. लेबल का नाम बदलना i सूचक पत्र के लिए j (द्वारा चिह्नित ρ(i,j))

बंधे हुए क्लिक-चौड़ाई के ग्राफ़ में कॉग्रफ़ ़ और दूरी-वंशानुगत ग्राफ़ शामिल हैं। यद्यपि क्लिक-चौड़ाई की गणना करना एनपी-कठिन है जब यह असंबद्ध है, और यह अज्ञात है कि क्या इसे बहुपद समय में गणना की जा सकती है जब यह घिरा हुआ है, क्लिक-चौड़ाई के लिए कुशल सन्निकटन एल्गोरिदम ज्ञात हैं। इन एल्गोरिदम और कौरसेल के प्रमेय के आधार पर, कई ग्राफ़ अनुकूलन समस्याएं जो मनमाने ग्राफ़ के लिए एनपी कठिन हैं, उन्हें बाउंडेड क्लिक-चौड़ाई के ग्राफ़ पर जल्दी से हल या अनुमानित किया जा सकता है।

क्लिक-चौड़ाई की अवधारणा के अंतर्निहित निर्माण क्रम को 1990 में ब्रूनो कौरसेल, एंगेलफ्रिएट और रोज़ेनबर्ग द्वारा तैयार किया गया था। और तक Wanke (1994). क्लिक-विड्थ नाम का उपयोग एक अलग अवधारणा के लिए किया गया था Chlebíková (1992). 1993 तक, इस शब्द का वर्तमान अर्थ पहले से ही मौजूद था।

ग्राफ़ के विशेष वर्ग

कॉग्राफ वास्तव में अधिकतम 2 क्लिक-चौड़ाई वाले ग्राफ़ होते हैं। प्रत्येक दूरी-वंशानुगत ग्राफ़ में अधिकतम 3 क्लिक-चौड़ाई होती है। हालाँकि, इकाई अंतराल ग्राफ़ की क्लिक-चौड़ाई असीमित होती है (उनकी ग्रिड संरचना के आधार पर)। इसी प्रकार, द्विदलीय क्रमपरिवर्तन ग्राफ़ की क्लिक-चौड़ाई असीमित है (समान ग्रिड संरचना के आधार पर)। चार शीर्षों वाले पथ के लिए बिना किसी प्रेरित सबग्राफ आइसोमोर्फिक वाले ग्राफ़ के रूप में कोग्राफ के लक्षण वर्णन के आधार पर, निषिद्ध प्रेरित सबग्राफ द्वारा परिभाषित कई ग्राफ वर्गों की क्लिक-चौड़ाई को वर्गीकृत किया गया है। बंधे हुए क्लिक-चौड़ाई वाले अन्य ग्राफ़ में लीफ पावर शामिल है|k-परिबद्ध मूल्यों के लिए पत्ती शक्तियां k; ये एक पेड़ की पत्तियों के प्रेरित उपसमूह हैं T ग्राफ शक्ति में T^k. हालाँकि, असीमित घातांक वाली पत्ती शक्तियों में सीमित क्लिक-चौड़ाई नहीं होती है।

सीमा

Courcelle & Olariu (2000) और Corneil & Rotics (2005) कुछ ग्राफ़ की क्लिक-चौड़ाई पर निम्नलिखित सीमाएँ साबित हुईं:

• यदि किसी ग्राफ़ में अधिकतम क्लिक-चौड़ाई है k, तो ग्राफ़ का प्रत्येक प्रेरित सबग्राफ भी ऐसा ही करता है।
• क्लिक-चौड़ाई के ग्राफ का पूरक ग्राफ k में अधिकतम क्लिक-चौड़ाई है 2k.
• वृक्ष-चौड़ाई के रेखांकन w अधिकतम क्लिक-चौड़ाई है 3 · 2^{w − 1}. इस सीमा में घातीय निर्भरता आवश्यक है: ऐसे ग्राफ़ मौजूद हैं जिनकी क्लिक-चौड़ाई उनकी ट्रीविड्थ से तेजी से बड़ी है। दूसरी दिशा में, परिबद्ध क्लिक-चौड़ाई के ग्राफ़ में असीमित वृक्ष-चौड़ाई हो सकती है; उदाहरण के लिए, n-वर्टेक्स पूर्ण ग्राफ़ में क्लिक-चौड़ाई 2 लेकिन ट्रीविड्थ है n − 1. हालाँकि, क्लिक-चौड़ाई के ग्राफ़ k जिसका कोई पूर्ण द्विदलीय ग्राफ़ नहीं है K_t,t एक सबग्राफ के रूप में अधिकतम ट्रीविड्थ है 3k(t − 1) − 1. इसलिए, विरल ग्राफ़ के प्रत्येक परिवार के लिए, परिबद्ध वृक्ष-चौड़ाई परिबद्ध क्लिक-चौड़ाई के बराबर है।
• एक अन्य ग्राफ़ पैरामीटर, रैंक-चौड़ाई, क्लिक-चौड़ाई द्वारा दोनों दिशाओं में घिरा हुआ है: rank-width ≤ clique-width ≤ 2^{rank-width + 1}.

इसके अतिरिक्त, यदि कोई ग्राफ G में क्लिक-चौड़ाई है k, फिर ग्राफ पावर G^c में अधिकतम क्लिक-चौड़ाई है 2kc^k. हालाँकि ट्रीविड्थ से क्लिक-चौड़ाई की सीमा और ग्राफ़ शक्तियों की क्लिक-चौड़ाई की सीमा दोनों में एक घातीय अंतर है, ये सीमाएँ एक-दूसरे को संयोजित नहीं करती हैं: यदि एक ग्राफ G में ट्रीविड्थ है w, तब G^c में अधिकतम क्लिक-चौड़ाई है 2(c + 1)^{w + 1} − 2, वृक्ष चौड़ाई में केवल एकल घातीय।

कम्प्यूटेशनल जटिलता

Unsolved problem in mathematics:

Can graphs of bounded clique-width be recognized in polynomial time?

(more unsolved problems in mathematics)

कई अनुकूलन समस्याएं जो ग्राफ़ के अधिक सामान्य वर्गों के लिए एनपी-हार्ड हैं, उन्हें बंधे हुए क्लिक-चौड़ाई के ग्राफ़ पर गतिशील प्रोग्रामिंग द्वारा कुशलतापूर्वक हल किया जा सकता है, जब इन ग्राफ़ के लिए एक निर्माण अनुक्रम ज्ञात होता है। विशेष रूप से, प्रत्येक ग्राफ़ संपत्ति जिसे एमएसओ में व्यक्त किया जा सकता है₁ मोनैडिक द्वितीय-क्रम तर्क (तर्क का एक रूप जो शीर्षों के सेट पर परिमाणीकरण की अनुमति देता है) में कौरसेल के प्रमेय के एक रूप के अनुसार, बंधे हुए क्लिक-चौड़ाई के ग्राफ़ के लिए एक रैखिक-समय एल्गोरिदम है।

बहुपद समय में बंधे हुए क्लिक-चौड़ाई के ग्राफ़ के लिए इष्टतम ग्राफ़ रंग या हैमिल्टनियन चक्र ढूंढना भी संभव है, जब एक निर्माण अनुक्रम ज्ञात होता है, लेकिन बहुपद का घातांक क्लिक-चौड़ाई के साथ बढ़ता है, और कम्प्यूटेशनल जटिलता सिद्धांत से साक्ष्य से पता चलता है कि यह निर्भरता आवश्यक होने की संभावना है। परिबद्ध क्लिक-चौड़ाई के ग्राफ χ-परिबद्ध| हैंχ-बाउंडेड, जिसका अर्थ है कि उनकी रंगीन संख्या उनके सबसे बड़े समूह के आकार का एक कार्य है।

विभाजित अपघटन पर आधारित एल्गोरिदम का उपयोग करके बहुपद समय में क्लिक-चौड़ाई तीन के ग्राफ़ को पहचाना जा सकता है, और उनके लिए एक निर्माण अनुक्रम पाया जा सकता है। असंबद्ध क्लिक-चौड़ाई के ग्राफ़ के लिए, क्लिक-चौड़ाई की सटीक गणना करना एनपी-कठिन है, और सबलाइनर एडिटिव त्रुटि के साथ एक अनुमान प्राप्त करना भी एनपी-कठिन है। हालाँकि, जब क्लिक-चौड़ाई बंधी होती है, तो बहुपद समय में बंधी हुई चौड़ाई (वास्तविक क्लिक-चौड़ाई से तेजी से बड़ी) का निर्माण अनुक्रम प्राप्त करना संभव है, विशेष रूप से शीर्षों की संख्या में द्विघात समय में। यह खुला रहता है कि क्या सटीक क्लिक-चौड़ाई, या इसके लिए एक सख्त सन्निकटन, की गणना पैरामीटरयुक्त जटिलता में की जा सकती है।

संबंधित चौड़ाई पैरामीटर

बाउंडेड क्लिक-विड्थ के ग्राफ़ का सिद्धांत बाउंडेड ट्रीविड्थ के ग्राफ़ के समान है, लेकिन ट्रीविड्थ के विपरीत घने ग्राफ़ की अनुमति देता है। यदि ग्राफ़ के एक परिवार ने क्लिक-चौड़ाई को सीमित कर दिया है, तो या तो इसमें वृक्ष-चौड़ाई की सीमा है या प्रत्येक पूर्ण द्विदलीय ग्राफ परिवार में एक ग्राफ का एक उपग्राफ है। ट्रीविड्थ और क्लिक-विड्थ भी लाइन ग्राफ़ के सिद्धांत के माध्यम से जुड़े हुए हैं: ग्राफ़ के एक परिवार ने ट्रीविड्थ को सीमित कर दिया है यदि और केवल यदि उनके लाइन ग्राफ़ ने क्लिक-विड्थ को सीमित कर दिया है।

परिबद्ध क्लिक-चौड़ाई के ग्राफ़ में परिबद्ध जुड़वां-चौड़ाई भी होती है।

संदर्भ

• Bonnet, Édouard; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2022), "Twin-width I: Tractable FO model checking", Journal of the ACM, 69 (1): A3:1–A3:46, arXiv:2004.14789, doi:10.1145/3486655, MR 4402362
• Brandstädt, A.; Dragan, F.F.; Le, H.-O.; Mosca, R. (2005), "New graph classes of bounded clique-width", Theory of Computing Systems, 38 (5): 623–645, CiteSeerX 10.1.1.3.5994, doi:10.1007/s00224-004-1154-6, S2CID 2309695.
• Brandstädt, A.; Engelfriet, J.; Le, H.-O.; Lozin, V.V. (2006), "Clique-width for 4-vertex forbidden subgraphs", Theory of Computing Systems, 39 (4): 561–590, doi:10.1007/s00224-005-1199-1, S2CID 20050455.
• Brandstädt, Andreas; Hundt, Christian (2008), "Ptolemaic graphs and interval graphs are leaf powers", LATIN 2008: Theoretical informatics, Lecture Notes in Comput. Sci., vol. 4957, Springer, Berlin, pp. 479–491, doi:10.1007/978-3-540-78773-0_42, MR 2472761.
• Brandstädt, A.; Lozin, V.V. (2003), "On the linear structure and clique-width of bipartite permutation graphs", Ars Combinatoria, 67: 273–281, CiteSeerX 10.1.1.16.2000.
• Chlebíková, J. (1992), "On the tree-width of a graph", Acta Mathematica Universitatis Comenianae, New Series, 61 (2): 225–236, CiteSeerX 10.1.1.30.3900, MR 1205875.
• Cogis, O.; Thierry, E. (2005), "Computing maximum stable sets for distance-hereditary graphs", Discrete Optimization, 2 (2): 185–188, doi:10.1016/j.disopt.2005.03.004, MR 2155518.
• Corneil, Derek G.; Habib, Michel; Lanlignel, Jean-Marc; Reed, Bruce; Rotics, Udi (2012), "Polynomial-time recognition of clique-width ≤ 3 graphs", Discrete Applied Mathematics, 160 (6): 834–865, doi:10.1016/j.dam.2011.03.020, MR 2901093.
• Corneil, Derek G.; Rotics, Udi (2005), "On the relationship between clique-width and treewidth", SIAM Journal on Computing, 34 (4): 825–847, doi:10.1137/S0097539701385351, MR 2148860.
• Courcelle, Bruno; Engelfriet, Joost; Rozenberg, Grzegorz (1993), "Handle-rewriting hypergraph grammars", Journal of Computer and System Sciences, 46 (2): 218–270, doi:10.1016/0022-0000(93)90004-G, MR 1217156. Presented in preliminary form in Graph grammars and their application to computer science (Bremen, 1990), MR1431281.
• Courcelle, B. (1993), "Monadic second-order logic and hypergraph orientation", Proceedings of Eighth Annual IEEE Symposium on Logic in Computer Science (LICS '93), pp. 179–190, doi:10.1109/LICS.1993.287589, S2CID 39254668.
• Courcelle, B.; Makowsky, J. A.; Rotics, U. (2000), "Linear time solvable optimization problems on graphs on bounded clique width", Theory of Computing Systems, 33 (2): 125–150, CiteSeerX 10.1.1.414.1845, doi:10.1007/s002249910009, S2CID 15402031.
• Courcelle, B.; Olariu, S. (2000), "Upper bounds to the clique width of graphs", Discrete Applied Mathematics, 101 (1–3): 77–144, doi:10.1016/S0166-218X(99)00184-5.
• Dvořák, Zdeněk; Král', Daniel (2012), "Classes of graphs with small rank decompositions are χ-bounded", Electronic Journal of Combinatorics, 33 (4): 679–683, arXiv:1107.2161, doi:10.1016/j.ejc.2011.12.005, S2CID 5530520
• Fellows, Michael R.; Rosamond, Frances A.; Rotics, Udi; Szeider, Stefan (2009), "Clique-width is NP-complete", SIAM Journal on Discrete Mathematics, 23 (2): 909–939, doi:10.1137/070687256, MR 2519936.
• Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket (2010), "Intractability of clique-width parameterizations", SIAM Journal on Computing, 39 (5): 1941–1956, CiteSeerX 10.1.1.220.1712, doi:10.1137/080742270, MR 2592039.
• Fomin, Fedor V.; Korhonen, Tuukka (2022), "Fast FPT-approximation of branchwidth", Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, ACM, pp. 886–899, arXiv:2111.03492, doi:10.1145/3519935.3519996, S2CID 243832882.
• Golumbic, Martin Charles; Rotics, Udi (2000), "On the clique-width of some perfect graph classes", International Journal of Foundations of Computer Science, 11 (3): 423–443, doi:10.1142/S0129054100000260, MR 1792124.
• Gurski, Frank; Wanke, Egon (2000), "The tree-width of clique-width bounded graphs without K_n,n", in Brandes, Ulrik; Wagner, Dorothea (eds.), Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000, Konstanz, Germany, June 15–17, 2000, Proceedings, Lecture Notes in Computer Science, vol. 1928, Berlin: Springer, pp. 196–205, doi:10.1007/3-540-40064-8_19, MR 1850348.
• Gurski, Frank; Wanke, Egon (2007), "Line graphs of bounded clique-width", Discrete Mathematics, 307 (22): 2734–2754, doi:10.1016/j.disc.2007.01.020.
• Gurski, Frank; Wanke, Egon (2009), "The NLC-width and clique-width for powers of graphs of bounded tree-width", Discrete Applied Mathematics, 157 (4): 583–595, doi:10.1016/j.dam.2008.08.031, MR 2499471.
• Hliněný, Petr; Oum, Sang-il (2008), "Finding branch-decompositions and rank-decompositions", SIAM Journal on Computing, 38 (3): 1012–1032, CiteSeerX 10.1.1.94.2272, doi:10.1137/070685920, MR 2421076.
• Oum, Sang-il; Seymour, Paul (2006), "Approximating clique-width and branch-width", Journal of Combinatorial Theory, Series B, 96 (4): 514–528, doi:10.1016/j.jctb.2005.10.006, MR 2232389.
• Oum, Sang-il (2008), "Approximating rank-width and clique-width quickly", ACM Transactions on Algorithms, 5 (1): Art. 10, 20, CiteSeerX 10.1.1.574.8156, doi:10.1145/1435375.1435385, MR 2479181.
• Todinca, Ioan (2003), "Coloring powers of graphs of bounded clique-width", Graph-theoretic concepts in computer science, Lecture Notes in Comput. Sci., vol. 2880, Springer, Berlin, pp. 370–382, doi:10.1007/978-3-540-39890-5_32, MR 2080095.
• Wanke, Egon (1994), "k-NLC graphs and polynomial algorithms", Discrete Applied Mathematics, 54 (2–3): 251–266, doi:10.1016/0166-218X(94)90026-4, MR 1300250.