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

असंयुक्त संघों, रीलेबलिंग और लेबल-जॉइन्स द्वारा क्लिक-विड्थ 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, ट्रीविड्थ में केवल एकल घातीय।

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

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

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

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

संबंधित विड्थ पैरामीटर

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

परिबद्ध क्लिक-विड्थ के ग्राफ़ में परिबद्ध ट्विन-विड्थ भी होती है।

संदर्भ

• 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.