Result: Parity Games of Bounded Tree-Depth
Further Information
La complexité exacte de la résolution des jeux de parité est un problème ouvert majeur. Plusieurs auteurs ont recherché des algorithmes efficaces sur des classes spécifiques de graphiques. En particulier, Obdr\v{z}\'{a}lek a montré que pour les graphiques de largeur d'arbre bornée ou de largeur de clique, le problème se trouve dans $ \mathrm{P}$ , qui a ensuite été amélioré par Ganardi, qui a montré que c'est même dans $ \mathrm{LOGCFL}$ ( avec une hypothèse supplémentaire pour le cas de la largeur de clique). Ici, nous étendons cette ligne de recherche en montrant que pour les graphiques de profondeur d'arbre bornée, le problème de la résolution des jeux de parité est dans l'uniforme de l'espace logique $ \text{AC}^0 $ . Nous y parvenons en considérant d'abord un paramètre que nous obtenons à partir d'une modification de la largeur de clique, que nous appelons la largeur de clique peu profonde. Nous fournissons par la suite une réduction appropriée.
La complejidad exacta de resolver juegos de paridad es un gran problema abierto. Varios autores han buscado algoritmos eficientes sobre clases específicas de gráficos. En particular, Obdr\v{z}\'{a}lek demostró que para los gráficos de ancho de árbol acotado o ancho de clique, el problema está en $\mathrm{P}$, que luego fue mejorado por Ganardi, quien demostró que está incluso en $\mathrm{LOGCFL}$ (con una suposición adicional para el caso de ancho de clique). Aquí ampliamos esta línea de investigación al mostrar que para los gráficos de profundidad de árbol acotado, el problema de resolver juegos de paridad está en el espacio de registro uniforme $\text{AC}^0 $. Logramos esto considerando primero un parámetro que obtenemos de una modificación del ancho de clique, que llamamos ancho de clique superficial. Posteriormente proporcionamos una reducción adecuada.
The exact complexity of solving parity games is a major open problem. Several authors have searched for efficient algorithms over specific classes of graphs. In particular, Obdr\v{z}\'{a}lek showed that for graphs of bounded tree-width or clique-width, the problem is in $\mathrm{P}$, which was later improved by Ganardi, who showed that it is even in $\mathrm{LOGCFL}$ (with an additional assumption for clique-width case). Here we extend this line of research by showing that for graphs of bounded tree-depth the problem of solving parity games is in logspace uniform $\text{AC}^0$. We achieve this by first considering a parameter that we obtain from a modification of clique-width, which we call shallow clique-width. We subsequently provide a suitable reduction.
يعد التعقيد الدقيق لحل ألعاب التكافؤ مشكلة كبيرة مفتوحة. بحث العديد من المؤلفين عن خوارزميات فعالة عبر فئات محددة من الرسوم البيانية. على وجه الخصوص، أظهر Obdr\v{z }\'{ a}lek أنه بالنسبة للرسوم البيانية لعرض الشجرة المحدود أو عرض الزمرة، تكون المشكلة في $\mathrm{P }$، والتي تم تحسينها لاحقًا بواسطة Ganardi، الذي أظهر أنه حتى في $\mathrm{LOGCFL }$ (مع افتراض إضافي لحالة عرض الزمرة). هنا نوسع هذا الخط من البحث من خلال إظهار أنه بالنسبة للرسوم البيانية لعمق الأشجار المحدود، فإن مشكلة حل ألعاب التكافؤ موجودة في logspace uniform $\text{AC }^0 $. نحقق ذلك من خلال النظر أولاً في المعلمة التي نحصل عليها من تعديل عرض الزمرة، والتي نسميها عرض الزمرة الضحل. نحن نقدم بعد ذلك تخفيضًا مناسبًا.