ในวิทยาการคอมพิวเตอร์และทฤษฎีกราฟคำว่าการเข้ารหัสสี (color-coding)หมายถึงเทคนิคเชิงอัลกอริทึมที่มีประโยชน์ในการค้นหารูปแบบเครือข่ายตัวอย่างเช่น สามารถใช้เพื่อตรวจจับเส้นทางง่ายๆที่มีความยาวk ใน กราฟที่กำหนดอัลกอริทึมการเข้ารหัสสีแบบดั้งเดิมเป็นแบบความน่าจะเป็นแต่สามารถ ลดความสุ่ม ลงได้โดยไม่ทำให้เวลาในการทำงานเพิ่มขึ้นมากนัก

การใช้รหัสสีสามารถนำไปใช้กับการตรวจจับวงจรที่มีความยาวที่กำหนด และโดยทั่วไปแล้วจะนำไปใช้กับปัญหาความเหมือนกันของกราฟย่อย ( ปัญหา NP-complete ) ซึ่งจะให้ผลลัพธ์เป็นอัลกอริทึมที่มีเวลาการทำงานเป็นพหุนามเมื่อรูปแบบกราฟย่อยที่พยายามตรวจจับนั้นมี treewidth ที่ จำกัด

วิธีการกำหนดรหัสสีได้รับการเสนอและวิเคราะห์ในปี 1994 โดยNoga Alon , Raphael YusterและUri Zwick ^{[ 1 ] [ 2 ]}

วิธีการกำหนดรหัสสีสามารถให้ผลลัพธ์ดังต่อไปนี้:

• สำหรับค่าคงที่k ทุกค่า หากกราฟG = ( V , E )ประกอบด้วยวัฏจักรแบบง่ายที่มีขนาดkแล้ว วัฏจักรดังกล่าวสามารถพบได้ใน:
  • ${\displaystyle O(|V|^{\โอเมก้า })}$เวลาที่คาดไว้ หรือ
  • ${\displaystyle O(|V|^{\omega }\log |V|)}$เวลากรณีเลวร้ายที่สุด โดยที่ωคือเลขชี้กำลังของการคูณเมทริกซ์^{[ 3 ]}
• สำหรับค่าคงที่k ทุกค่า และสำหรับกราฟG = ( V , E ) ทุกกราฟ ที่อยู่ในตระกูลกราฟปิดไมเนอร์ที่ ไม่ใช่กราฟว่าง (เช่นกราฟระนาบ ) ถ้าGมีวัฏจักรแบบง่ายขนาดkวัฏจักรดังกล่าวสามารถพบได้ใน:
  • O ( V )เวลาที่คาดไว้ หรือ
  • เวลาที่เลวร้ายที่สุด O ( V log V )
• ถ้ากราฟG = ( V , E )มีกราฟย่อยที่สมมาตรกับ กราฟ treewidth ที่มีขอบเขต ซึ่งมี จุดยอด O (log V )จุด กราฟย่อยดังกล่าวสามารถค้นหาได้ในเวลาพหุนาม

เพื่อแก้ปัญหาการค้นหาซับกราฟในกราฟG = ( V , E ) ที่กำหนดให้ โดยที่Hอาจเป็นเส้นทาง วงจร หรือกราฟtreewidth ที่มีขอบเขตใดๆ วิธีการระบายสีเริ่มต้นด้วยการระบายสีจุดยอดแต่ละจุดของG แบบสุ่ม ด้วยสีต่างๆ จากนั้นพยายามค้นหาสำเนาที่มีสีสันของHในG ที่ระบายสีแล้ว ในที่นี้ กราฟที่มีสีสันคือกราฟที่จุดยอดทุกจุดในกราฟนั้นถูกระบายสีด้วยสีที่แตกต่างกัน วิธีนี้ทำงานโดยการทำซ้ำ (1) การระบายสีกราฟแบบสุ่ม และ (2) การค้นหาสำเนาที่มีสีสันของซับกราฟเป้าหมาย และในที่สุดก็จะสามารถพบซับกราฟเป้าหมายได้หากทำซ้ำกระบวนการนี้เป็นจำนวนครั้งที่เพียงพอ ${\displaystyle H=(V_{H},E_{H})}$${\displaystyle |V_{H}|=O(\log |V|)}$${\displaystyle k=|V_{H}|}$

สมมติว่าสำเนาของHในG กลายเป็นภาพที่มีสีสันด้วยความน่าจะเป็น pที่ไม่เป็นศูนย์ดังนั้นจึงสรุปได้ทันทีว่า ถ้าการระบายสีแบบสุ่มนั้นถูกทำซ้ำ⁠1/พีครั้งจากนั้นคาดว่าสำเนานี้จะกลายเป็นสีหนึ่งครั้ง โปรดทราบว่าถึงแม้ p จะมีขนาดเล็ก แต่ก็แสดงให้เห็นว่าถ้าpมีขนาดเล็กในระดับพหุนามเท่านั้น สมมติอีกครั้งว่ามีอัลกอริทึมอยู่ ซึ่งเมื่อกำหนดกราฟ Gและการระบายสีที่แมปแต่ละจุดยอดของ Gไปยังหนึ่งใน kสี อัลกอริทึมจะค้นหาสำเนาของ H ที่มีสีสัน หากมีอยู่ ภายในเวลาการทำงาน O ( r ) บางอย่าง จากนั้นเวลาที่คาดหวังในการค้นหาสำเนาของ Hใน Gหากมีอยู่คือ ${\displaystyle |V_{H}|=O(\log |V|)}$${\displaystyle O({\tfrac {r}{p}})}$

บางครั้ง การใช้รูปแบบการกำหนดสีที่จำกัดกว่าก็เป็นสิ่งที่พึงปรารถนาเช่นกัน ตัวอย่างเช่น ในบริบทของการค้นหาวัฏจักรในกราฟระนาบเป็นไปได้ที่จะพัฒนาอัลกอริทึมที่ค้นหาวัฏจักรที่มีสีที่ดี โดยที่วัฏจักรจะมีสีที่ดีก็ต่อเมื่อจุดยอดของวัฏจักรนั้นถูกระบายสีด้วยสีที่ต่อเนื่องกัน

ตัวอย่างเช่น การค้นหาวัฏจักรอย่างง่ายที่มีความยาวk ในกราฟG = ( V , E )

โดยการใช้วิธีการระบายสีแบบสุ่ม วงจรแบบง่ายแต่ละวงจะมีโอกาส ที่จะกลายเป็นวงจรที่มีสีสัน เนื่องจากมีวิธีระบายสี จุดยอด kจุดบนวงจร ซึ่งในจำนวนนั้นมีเหตุการณ์ที่มีสีสันเกิดขึ้น จากนั้นสามารถใช้อัลกอริธึม (ที่อธิบายต่อไป) เพื่อค้นหาวงจรที่มีสีสันในกราฟG ที่ระบายสีแบบสุ่มได้ ในเวลาโดยที่คือค่าคงที่ของการคูณเมทริกซ์ ดังนั้นโดยรวมแล้วจะใช้ เวลา ในการ ค้นหา วงจรแบบง่ายที่มีความยาวkในG${\displaystyle k!/k^{k}>e^{-k}}$${\displaystyle k^{k}}$${\displaystyle k!}$${\displaystyle O(V^{\โอเมก้า })}$${\displaystyle \omega }$${\displaystyle e^{k}\cdot O(V^{\omega })}$

อัลกอริทึมการค้นหาวงจรที่มีสีสันทำงานโดยการค้นหาคู่ของจุดยอดทั้งหมดในVที่เชื่อมต่อกันด้วยเส้นทางแบบง่ายที่มีความยาวk − 1ก่อน จากนั้นจึงตรวจสอบว่าจุดยอดสองจุดในแต่ละคู่เชื่อมต่อกันหรือไม่ กำหนดฟังก์ชันการระบายสีc  : V → {1, ..., k }เพื่อระบายสีกราฟG ให้แจงนับ _การแบ่งส่วนของเซตสี{1, ..., k }ออกเป็นสองเซตย่อย_C1 และ C2 ที่มีขนาดเท่ากัน โปรดทราบว่าVสามารถแบ่งออกเป็นV1และ_V2 ได้ตามลำดับ และให้G1และG2แทนกราฟย่อยที่เกิดจากV1 _และ V2 _{ตาม ลำดับ จาก นั้น}ค้นหาเส้นทางที่มีสีสันที่มี_ความยาวในแต่ละG1และG2 _{แบบเรียกซ้ำ}สมมติว่าเมทริกซ์บูลีนA ₁และA ₂แทนการเชื่อมต่อของจุดยอดแต่ละคู่ในG ₁และG ₂ด้วยเส้นทางที่มีสีสันตามลำดับ และให้Bเป็นเมทริกซ์ที่อธิบายความสัมพันธ์ประชิดระหว่างจุดยอดของV ₁และจุดยอดของV ₂ผลคูณบูลีนจะให้จุดยอดทุกคู่ในVที่เชื่อมต่อกันด้วยเส้นทางที่มีสีสันที่มีความยาวk − 1ดังนั้น ความสัมพันธ์แบบเวียนเกิดของการคูณเมทริกซ์คือซึ่งให้เวลาทำงานเท่ากับแม้ว่าอัลกอริทึมนี้จะพบเฉพาะจุดปลายของเส้นทางที่มีสีสันเท่านั้น แต่อัลกอริทึมอื่นโดย Alon และ Naor ^{[ 4 ]}ที่ค้นหาเส้นทางที่มีสีสันเองก็สามารถรวมเข้าด้วยกันได้ ${\displaystyle k/2}$${\displaystyle k/2-1}$${\displaystyle A_{1}BA_{2}}$${\displaystyle t(k)\leq 2^{k}\cdot t(k/2)}$${\displaystyle 2^{O(k)}\cdot V^{\โอเมก้า }}$

การลดความสุ่มของการกำหนดรหัสสีเกี่ยวข้องกับการแจงนับการระบายสีที่เป็นไปได้ของกราฟGเพื่อให้ไม่จำเป็นต้องใช้ความสุ่มในการระบายสีG อีกต่อไป สำหรับการค้นพบกราฟย่อยเป้าหมาย HในGนั้น การแจงนับจะต้องรวมอย่างน้อยหนึ่งกรณีที่Hมีสีสัน เพื่อให้บรรลุเป้าหมายนี้ การแจงนับตระกูลฟังก์ชันแฮชk -perfect F จาก {1, ..., | V |}ไปยัง{1, ..., k }ก็เพียงพอแล้ว ตามคำนิยามFเป็นk -perfect ถ้าสำหรับทุกเซตย่อยSของ{1, ..., | V |}โดยที่มีฟังก์ชันแฮชhในF อยู่ ซึ่งh  : S → {1, ..., k }เป็นperfectกล่าวอีกนัยหนึ่ง ต้องมีฟังก์ชันแฮชในFที่ระบายสี จุดยอด k จุดใดๆ ด้วย สีที่แตกต่างกัน kสี ${\displaystyle |S|=k}$

มีแนวทางหลายประการในการสร้าง ตระกูลแฮชที่สมบูรณ์แบบ k ดังกล่าว :

1. การสร้างที่ชัดเจนที่ดีที่สุดคือโดยMoni Naor , Leonard J. SchulmanและAravind Srinivasan [ ^{5 ] ซึ่ง} สามารถสร้าง ตระกูลที่มีขนาดได้ การสร้างนี้ไม่จำเป็นต้องมีซับกราฟเป้าหมายอยู่ในปัญหาการค้นหาซับกราฟดั้งเดิม${\displaystyle e^{k}k^{O(\log k)}\log |V|}$
2. โครงสร้างที่ชัดเจนอีกแบบหนึ่งโดยJeanette P. Schmidtและ Alan Siegel ^{[ 6 ]}ทำให้เกิดตระกูลที่มีขนาด${\displaystyle 2^{O(k)}\log ^{2}|V|}$
3. โครงสร้างอีกแบบหนึ่งที่ปรากฏในเอกสารต้นฉบับของNoga Alon et al. ^{[ 2 ]}สามารถได้มาโดยการสร้าง ตระกูล k -perfect ก่อน ซึ่งแมป{1, ..., | V |}ไปยัง{1, ..., k ² }ตามด้วยการสร้าง ตระกูล k -perfect อีกตระกูลหนึ่ง ซึ่งแมป{1, ..., k ² }ไปยัง{1, ..., k }ในขั้นตอนแรก เป็นไปได้ที่จะสร้างตระกูลดังกล่าวด้วย บิตสุ่ม 2 n log kซึ่งเกือบจะเป็นอิสระแบบ2log k ^{[ 7 ] [ 8 ]}และปริภูมิของตัวอย่างที่จำเป็นสำหรับการสร้างบิตสุ่มเหล่านั้นสามารถมีขนาดเล็กได้ ในขั้นตอนที่สอง Jeanette P. Schmidt และ Alan Siegel ^{[ 6 ]}ได้แสดงให้เห็นว่าขนาดของ ตระกูล k -perfect ดังกล่าวสามารถเป็นดังนั้น โดยการประกอบ ตระกูล k -perfect จากทั้งสองขั้นตอนจะได้ ตระกูล k -perfect ขนาดที่แมปจาก{1, ..., | V |}ไปยัง{1, ..., k }${\displaystyle k^{O(1)}\log |V|}$${\displaystyle 2^{O(k)}}$${\displaystyle 2^{O(k)}\log |V|}$

ในกรณีของการลดความสุ่มของการระบายสีบ่อน้ำ ซึ่งแต่ละจุดยอดบนกราฟย่อยจะถูกระบายสีตามลำดับจำเป็นต้องมี ตระกูลฟังก์ชันแฮชที่สมบูรณ์แบบ kตัวจาก{1, ..., | V |}ไปยัง{1, ..., k !} ตระกูลที่สมบูรณ์แบบ k ตัวที่เพียงพอ ซึ่งแมปจาก{1, ..., | V |}ไปยัง{1, ..., k ^k }สามารถสร้างได้ในลักษณะที่คล้ายกับแนวทางที่ 3 ข้างต้น (ขั้นตอนแรก) โดยเฉพาะอย่างยิ่ง จะทำโดยใช้ บิตสุ่ม nk log kที่เกือบจะเป็น อิสระ k log kและขนาดของ ตระกูลที่สมบูรณ์แบบ k ที่ได้ จะเป็น ${\displaystyle k^{O(k)}\log |V|}$

การลดความสุ่มของวิธีการกำหนดรหัสสีสามารถประมวลผลแบบขนานได้อย่างง่ายดาย ทำให้ได้อัลกอริธึม NC ที่มีประสิทธิภาพ

ในปัจจุบัน การใช้รหัสสีได้รับความสนใจอย่างมากในสาขาชีวสารสนเทศตัวอย่างหนึ่งคือการตรวจจับเส้นทางการส่งสัญญาณใน เครือข่าย ปฏิสัมพันธ์ระหว่างโปรตีน (PPI) อีกตัวอย่างหนึ่งคือการค้นหาและนับจำนวนโมทีฟในเครือข่าย PPI การศึกษาทั้งเส้นทางการส่งสัญญาณและโมทีฟช่วยให้เข้าใจความเหมือนและความแตกต่างของหน้าที่ กระบวนการ และโครงสร้างทางชีวภาพต่างๆ ในสิ่งมีชีวิตได้ลึกซึ้งยิ่งขึ้น

เนื่องจากปริมาณข้อมูลยีนที่สามารถรวบรวมได้มีจำนวนมหาศาล การค้นหาเส้นทางหรือรูปแบบต่างๆ จึงอาจใช้เวลานานมาก อย่างไรก็ตาม การใช้เทคนิคการระบายสีช่วยให้สามารถค้นหารูปแบบหรือเส้นทางการส่งสัญญาณที่มีจุดยอดในเครือข่ายGที่มี จุดยอด nจุดได้อย่างมีประสิทธิภาพมากในเวลาที่เป็นพหุนาม ดังนั้นจึงช่วยให้เราสามารถสำรวจโครงสร้างที่ซับซ้อนหรือใหญ่ขึ้นในเครือข่ายปฏิสัมพันธ์โปรตีนได้ ${\displaystyle k=O(\log n)}$

• Alon, N.; Dao, P.; Hajirasouliha, I.; Hormozdiari, F.; Sahinalp, SC (2008). "การนับและการค้นพบรูปแบบเครือข่ายชีวโมเลกุลโดยการเข้ารหัสสี" . Bioinformatics . 24 (13): i241– i249. doi : 10.1093/bioinformatics/btn163 . PMC  2718641 . PMID  18586721 .
• Hüffner, F.; Wernicke, S.; Zichner, T. (2008). "วิศวกรรมอัลกอริทึมสำหรับการเข้ารหัสสีพร้อมการประยุกต์ใช้ในการตรวจจับเส้นทางการส่งสัญญาณ" Algorithmica . 52 (2): 114– 132. CiteSeerX  10.1.1.68.9469 . doi : 10.1007/s00453-007-9008-7 . S2CID  81069 .