图的非循环和全循环方向：日本东京大学计算机科学系的研究

可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）655-666www.elsevier.com/locate/entcs非循环和全循环方向法利·苏亚雷斯·奥利维拉1Hiraishi Hidefumi2 Hiroshi Imai3东京大学计算机科学系日本东京摘要本文研究了两类图的定向：无圈定向和全圈定向的计数和枚举问题。计数对他们两人来说都是#P-hard。 为了避免这个问题，我们提出了固定参数可处理（FPT）算法。对于枚举任务，我们构造一个二元决策图（BDD）来表示这两种类型的所有方向，而不是显式地2 2我在数他们。 我们证明了这种构造的运行时间由O∞（2pw/4+o（pw））关于路径宽度pw限定. 然后，我们开发了更快的FPT算法来计算非循环和完全2 2无圈定向，运行时间为O×（2bw/2+o（bw）），其中bw表示给定图的branch-宽度. 这些计数算法是通过将我们的计数算法中的观测值应用于分支分解而得到的关键词：非循环方向，全循环方向，参数化算法，FPT算法，路径宽度，分支宽度，二叉决策图1引言无向图G=（V，E）的图定向是通过定向G的所有边而获得的有向图。在本文中，我们设计了枚举和计数算法的路径宽度和分支宽度参数的无循环和全循环方向。如果一个定向是有向无环图，则称它是无环的;如果它的每个连通分支都是强连通的，则称它是全环的众所周知，对于平面图，这两个方向是对偶的，即平面图的无圈方向与其对偶图的全圈方向1电子邮件：diveira@is.s.u-tokyo.ac.jp2电子邮件：hiraishi1729@is.s.u-tokyo.ac.jp3电子邮件：imai@is.s.u-tokyo.ac.jphttps://doi.org/10.1016/j.entcs.2019.08.0571571-0661/© 2019作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。656F.S. Oliveira等人/理论计算机科学电子笔记346（2019）655无圈定向和全圈定向与组合几何学和几何学中的各种对象有关。最著名的关系是图着色和无圈定向之间的关系G的非循环定向数等于（−1）n×G（−1），其中×G表示其色多项式[26]。由于着色和非零流之间的对偶性，全循环定向的数目可以通过计算χ <$G（−1）[17]的非零多项式来获得。这种色多项式和多项式之间的对偶（或者说，非循环方向和全循环方向之间的对偶）被合成为Tutte多项式[7]的概念，并自然地扩展到几何对象，如超平面排列，点配置，多面体等，在定向拟阵的透镜中[16]。Tutte多项式是从色多项式推广而来的拟阵不变二元多项式T（x，y），它包含了除图以外的关于拟阵的广泛信息。特别地，图的无圈定向和全圈定向的数目分别通过评估T（2，0）[26]和T（0，2）[17]来获得证明了图的生成森林与这两类定向密切相关。也就是说，Merino-Welsh猜想指出，对于任何给定的无向图，没有环和桥，生成森林的数量至多是无圈方向和全圈方向的数量中的最大值;等价地，T（1， 1）≤max{T（2， 0），T（0， 2）}。证明了该不等式对拟阵的Tutte多项式也成立。图和拟阵的几个子类有部分结果[27，18，20，8]。非循环和全循环取向也与超平面排列有着有趣的联系，超平面排列是组合学和几何学领域中研究得很好的对象。 给定一个图G=（V，E），每个图的超平面集xi=xj{i，j}∈E称为图排列，它的对偶实体由拟阵对偶给出，共图排列在由任何给定的图形排列划分的空间区域与相应图形的非循环方向之间存在双射[13]。虽然人们可以在线性时间内找到给定无向图的这两个方向，但即使对于二分图[28]，计数和枚举它们也是P-困难的。设计固定参数易处理算法（FPT）是解决复杂问题的一种有前途的方法。如果一个算法在O（f（k）poly（N））时间内运行，则该算法是关于结构参数k的FPT，其中f是可计算函数，N是输入大小。对于非循环和全循环方向的计数问题，所有已知的FPT算法都可以通过计算Tutte多项式得到。在图论和几何学中，显式枚举对象的规范方法是反向搜索.在[1]中，反向搜索技术被开发用于各种各样的对象，包括超平面排列的细胞，因此它们可以被扩展用于枚举图的无圈和全圈定向。也有专门用于非循环方向的枚举算法[25，3，9]。本文利用二叉决策图（Binary Decision Diagrams，简称BDDiagrams）设计了隐式枚举图的无圈和全圈方向的参数化算法。BDD）。BDD最初是由Bryant[6]设计的，F.S. Oliveira等人/理论计算机科学电子笔记346（2019）655657[|≤≤布尔函数他们允许一个执行布尔运算的压缩数据，而不解压。BDD的这一突出优点产生了一系列基于BDD的组合优化和枚举问题的方法例如，通过以自上而下的方式构造与生成森林相关的BDD，来描述计算Tutte多项式的算法[23]。基于BDD的算法也被开发来解决图优化和枚举问题，例如最大团，图着色，图覆盖[11]和路径枚举[15]。我们提出了关于路径宽度pw的FPT算法，用于构造所有非循环和全循环方向的BDD，导致运行时间为O<$（2pw2/4+o（pw2）），其中符号O<$忽略了多项式因子的数量，边缘.据我们所知，目前最快的FPT算法用于计数非循环方向，相对于图[19]的树宽tw在O/（2tw2+o（tw2））时间内运行，并且相对于图[23]的路径宽度pw在O/（2pwlog（pw））时间内运行。注意，不等式tw≤ pw始终成立，因此这些算法的时间复杂度低于这里提供的算法然而，我们的算法构造的BDD有几个用途以外的计数。它可以用来，除其他事项外，枚举的非循环和全循环的方向图，并抽样这些方向均匀随机。它也可以与在同一域上定义的其他布尔函数的BDD结合，在布尔运算方面。一旦构建了BDD，所有的非循环（分别为在O（mN）时间内可以枚举所有的非循环（分别是）方向，其中N表示非循环（分别是）方向的总数。 全循环）取向。 非循环方向的枚举已被应用于分布式调度机制中的资源管理[2，3]。另一方面，全循环方向的枚举已被应用于为道路网络中的单行道问题寻找可行方向[10]。对于计数任务，我们提供了FPT算法，利用分支分解和分支宽度对非循环和全循环定向进行了研究。这些概念最初是在[22]中引入的，其中图的分支宽度bw被证明与其树宽度tw线性相关，树宽度tw是图问题的参数化算法设计中更标准的图宽度，如下所示：2 tw/ 3 + 1 bw tw +1。 我们的非循环和全循环方向的计数算法运行在O<$（2bw2/2+o（bw2））时间内，比O<$（2tw2+o（tw2））的速度快， 在[19]中的上述算法，其评估Tutte多项式。最后，我们提到分支分解可以用来设计其他类型的图方向的参数化计数算法。[24]中关于雕刻分解的FPT算法可以自然地转换为关于分支分解的XP算法，其中如果对于某个可计算函数f和输入大小N，算法在O（Nf（k））时间内运行，则称该算法为XP。658F.S. Oliveira等人/理论计算机科学电子笔记346（2019）6552枚举非循环和全循环定向除非另有说明，本节中的所有图表都是有限和简单的。 为对于图G，我们用V（G）表示它的点集，用E（G）表示它的边集.此外，我们定义n（G）：= card（V（G））和m（G）：= card（E（G））。 如果图G从上下文中是清楚的，我们简单地写V，E，n和m。图的部分定向是通过定向它的一些边而获得的部分有向图。更正式地说，G的部分定向P是子图G=（V，E）和有向图D=（V，A）的边不交并，其中EE，其中A是通过将E\E的每条边{u，v}替换为有向边（u，v）或（v，u）而获得的有向边集合。对于G的任意部分定向P，我们记E（P）：=E和A（P）：=A。注意，图和有向图特别是部分定向。对于S<$E（P）<$A（P），我们用G[S]表示由S诱导的部分定向，并且我们说v∈V与S相邻，如果它相邻S的至少一个元素。在本节中，我们提出了算法来构造BDD，这些BDD可以用于枚举给定图G的所有非循环和全循环方向。 二叉决策图（Binary Decision Diagram，BDD）是一种非循环图，布尔函数，最初在[6]中提出。Sekine，Imai，Tani[23]建议以自顶向下的方式进行BDD构建（与[6]中的自底向上方式相反），我们在这里也遵循这种方法在这种方法中，人们连续地向布尔变量赋值。在di-gram中，通过将值分配给单个变量，从其父节点获得子节点（节点）然后考虑与布尔函数相关的子结构（在我们的情况下，部分方向）的等价性。两个子结构被称为等价的，如果对于剩余变量的所有可能的赋值（假设剩余变量对于两个子结构是相同的），第一个的输出等于第二个关于布尔函数的输出。当两个子结构等价时，计算它们是冗余的，因此它们可以在完全构建数据结构之前合并，从而减少内存使用。这个过程的一个例子如图所示1 .一、在这里，我们考虑一个准约简有序二元决策图（QOBDD），如[23]所示，只应用我们将在本节后面指定的合并规则。预先确定变量的排序，QOBDD被构造为分层图，使得第i层中的所有节点对应于顺序中的第i个变量。设G是一个图。固定顶点集V的任何顺序，取一个特征向量v ∈ {0，1}E来表示如果v（{u，v}）= 0，则用（u，v）代替{ u，v }，否则用（v，u）代替{u，v}得到的有向图，其中uuv和<$a是G [A（P）]中从u到v的有向路）.由图G和它的边的序e1，e2，···，em检查两个局部方向是否相等的测试如步骤b和c所示。(i) 将节点G添加到第0层。(ii) 对于每个k∈{1，2，···，m}，(a) 将与通过对第（k-1）层的每个节点P0的边ek进行定向而获得的所有部分定向P相对应的对（P，pp（P））以及指向P0（它们在BDD中的父节点）的指针添加到临时集合Tk。(b) 对于Tk中的每一对（P，pp（P）），如果不存在P的不与E（P）相邻的顶点（其是源或汇），则将P添加到第k层，将P的父映射到P，将P映射到0，并且设置Tk：=Tk\ {（P，pp（P））}。(c) 将剩余集Tk划分为由P诱导的等价类，相同的可达性关系，从每个等价类中选择一个元素，将其P添加到BDD的第k层，并将P的父类映射到P。(iii) 在第m层中，将剩余的节点映射到0或1。我们可以使用类似的算法来为所有非循环方向构建BDD，而不是上面步骤b中所做的，当它们包含至少一个有向循环时，将部分方向直接映射到0在这种情况下，一个结点P的降维是否包含有向圈完全由消去阵面α（P）、可达关系RP和剩余无向边E（P）的方向来刻画，而不依赖于A（P）（直到RP）.因此，在非循环方向的情况下，不必存储关于有向边的信息，而仅存储关于可达性关系的信息。相反，在枚举全循环方向的算法中，包含在连接消除前沿顶点的有向路径中的A（P）中的有向边可能在P的某个后代中失去该性质，因此我们必须保留关于每个部分方向的信息。我们在图1中展示了这些结构的例子。我们的方法的正确性是基于下面的两个结果。命题2.3在BDD的任意给定水平上，对于全循环取向，如果RPi=RPj，则允许合并部分取向P i和P j，并且对于两者，660F.S. Oliveira等人/理论计算机科学电子笔记346（2019）65521221 2联系我们110011 2 123 4 341 1水平1 23 40113 4 343 4 343 4 3 41 2121 2 121 21212 11223 4 343 4 343 4 343 43 4343412121212 1212121212 12 121212 123343434 3434 3434 34 3434 343434 341212 1212 12 1212 12 12 12 12 1212 1212 1212121212434 34 34 34 34 34 34 34 34 34 34 34 34 34 3 4 3434343434Fig. 1.（左）由四个顶点的循环图生成的二叉决策树C4.边的顺序如下：1， 2 1， 3 2， 4 3， 4。<<<实线和虚线分别表示边从最小顶点到最大顶点和从最大顶点到最小顶点的方向。（中）简化的二元决策图用于枚举使用我们的算法构造的非循环方向。红色部分方向表示已经发现了一个直接循环，没有必要继续发展从它们发出的分支。（右）简化的二元决策图，用于枚举从我们的算法构建的全循环方向。红色部分方向表示不与E（P）相邻的汇或源已被因此，没有必要继续开发从它们发出的分支其中，不存在不与任何无向边相邻的顶点，所述无向边是源或汇。证据设P表示BDD中的一个部分定向，其中P的顶点不与E（P）相邻，E（P）是源或汇，设D（P）表示由E（P）的一个固定的任意定向所产生的有向图。为了证明这个定理，证明一个映射s是足够的，它把每个P带到一个简化的版本s（P），使得（i）D（s（P））是全循环的，如果D（P）是全循环的，并且（ii）D（s（P））完全由RP刻画。我们构造映射如下：我们首先对G[A（P）]的每个强连通分量进行顶点识别，得到s1（P）。由于强连通分支的任意一对顶点的元素都是相互可达的，所以我们得到D（P）是全循环的，如果D（ s1（P））是全循环的.然后我们通过设置A（s（P））：={（u，v）∈α（ s1（P））2：uRs （P ）v}并删除α（s1（P））中不包含的（新的）孤立点，从s1（P）定义s（P从定义可以得出D（s（P））完全由RP刻画。设α：=α（s1（P））=α（s（P））.证明了D（s1（P））的一个必要条件全循环的条件是D（s（P））全循环（充分性是直接的），我们用矛盾的方法来处理。设D（s（P））是全循环的，但存在v0，vl∈α（v0/=vl）使得v0Rs（P）vl，且在D（s（P））上不存在从vl到v0的注意，v0Rs（P）vl意味着v0Rs1（P）vl，因此存在有向游动（v0，v1），（v1，v2），.，（vl−1，vl）包含在A（s1（P））中。因为所有的有向边A（s1（P））包含在定向后的某个圈中，则必有包含在E（s1（P））中的任意长的路径bi，pi，ai，其中ai，bi是顶点，pi是任意长的路径，且在定向后取每个vi到vi−1（i=1，2，···，l因此，walk（vl ，bl），pl ，（al ，vl−1），（vl−1，bl−1）， . ，（a2，v1），（v1，b1），p1，（a1，v0）in212212F.S. Oliveira等人/理论计算机科学电子笔记346（2019）655661∗D（s（P））（直到圈的顶点标识）将vl连接到v0，这是一个矛盾，完成了证明。 Q命题2.4在BDD的任意给定水平上，对于无圈定向，如果RPi= RPj且两者都不包含有向圈，则允许合并部分定向P i和P j。证据设α：=α（Pi）=α（Pj）.对于剩余无向边的任意方向，设Di和Dj分别是由Pi和Pj得到的有向图.利用对称性，证明了如果Di是循环的，则Dj也是循环的.假设Di包含有向圈C。这个循环必须经过α，否则就可以得出Dj是非循环的。我们可以用圈C中的有向路C A（P j）代替有向路CA（P i），得到D j的新圈C。Q由上述算法构造的BDD中的节点数量取决于边的排序，并且寻找最佳排序通常是一个co-NP-complete问题[6]。特别是，重要的是要考虑BDD的宽度，定义为一个级别中所有级别的最大节点数我们描述了一个排序的边缘，表示路径宽度排序，基于路径分解的一个图，它允许我们绑定的宽度的BDD，最初介绍 在[21]中。关于图的路分解和相应的路宽的详细说明，我们请读者参考[4]。在这里，我们注意到路径宽度可以计算，并且可以在时间2O（pw2）n中找到相应的路径分解对于路宽为pw的图[12]，并回忆基于区间图的路宽的一个刻画。给定直线上的n个区间，区间图是它们的交图，即在这些区间上的两个区间相邻且它们的交不为零的图。此外，一个（不一定是区间）图G的区间厚度比G的区间超图中的最大团大小小1。已知图的路宽至多为k−1 i表示其间隔厚度至多为k[4]。给定一个路宽为pw的图G，我们由此得出结论：在n个区间上存在一个区间图，它也是G的一个超图，其最大团大小至多为pw +1。不失一般性，我们可以假设区间的端点在{1，2，.，2n}。如果我们将区间按其右端点的递增顺序排序，我们可以将边的路径宽度排序定义为基于此的字典序。间隔的排序引理2.5 [21]对于任何图G，其边的路宽排序的消除前沿的大小以pw +1为界，其中pw表示G的路宽。一个二元关系被称为严格偏序，如果它是不相关的，传递的和不对称的。 这是一个众所周知的和容易验证的事实，对于任何有限集， S的所有偏序的集合与S的所有严格偏序的集合是双射的。662F.S. Oliveira等人/理论计算机科学电子笔记346（2019）65524+24= 244= 24定理2.6本节中描述的BDD的宽度由下式限定：pw2+o（pw2）24对于边的路径宽度排序，其中pw表示图的路径宽度。证据让我们首先考虑非循环定向的BDD。对于给定的部分定向P，其中A（P）是非循环的，检验可达关系RP是消去阵面α（P）上的严格偏序是很简单的.如上所述，在α（P）上的严格偏序集和α（P）上的偏序集之间存在一一对应。[14]中给出了n个元素的有限集合的偏序个数Pn的以下界限：log2Pn =n23n时间复杂度O（logn）4 2由此得到所需的结果。在全循环定向的情况下，可能存在顶点子集其元素是相互可达的。如果我们对这些子集执行顶点识别，我们可以通过考虑基数为1，2，.的集合上的可达性关系来使用[ 14 ]中的结果，，分别。可能的可达性关系的总数由12+o（pw2）22+o（pw2）pw2+o（pw2）+ ···+24pw2+o（pw2）+（pw−1）2（pw−1）2+o（pw2）pw2+o（pw2）2 pw−1（pw−1）2+o（pw2）= 24+ 24 24pw2+o（pw2）Q3基于分支分解我们回顾分支分解和分支宽度。设G=（V，E）是一个无向图，其中V和E分别是它的顶点集和边集.图G的一个分支分解D是一个对（T，φ），其中T是一个有根二叉树，|E|叶，φ是从E到T的叶集合的双射。为了避免混淆，我们称T的顶点为节点，T的边为链路。 给定一个分支分解D=（T，φ）和它的连接e，值w（D）和we按以下方式赋值。在T中删除e，我们得到两个子树T1（包含根）和T2（不包含根）。设L i（i =1，2）是T i中的叶的集合. 然后我们可以得到E的划分（E1，E2），其中Ei= φ−1（L i）（i = 1，2），其中φ−1（L i）={φ−1（l）：l∈L i}。设mid（e）为G[E1]和G[E2]的公共顶点集，其中G[Ei]（i=1，2）分别是G值we.F.S. Oliveira等人/理论计算机科学电子笔记346（2019）655663被定义为|中（e）|，即G [E1]和G [E2]之间共有的顶点数。值w（D）是D的所有链路e中的最大值we。分支宽度bw（G）（或缩写为BW（G））bw）是G的所有可能分支分解D中的最小值w（D）。对于任何固定的k，存在一个线性时间算法，该算法检查图是否具有由k限定的分支宽度，如果是，则输出最小分支宽度的分支分解[5]。图二.分支分解：（a）一个给定的图G，（b）G的一棵分解树T，（c）由T的一个链环e导出的两个边子图给定G的最优分支分解D=（T，φ），构造FPT算法来计算非循环定向和全循环定向的个数我们首先引入一些符号来构造我们的算法。为了方便起见，我们预先在顶点之间固定一个线性顺序。<对于一个给定的节点u，我们用u0表示它的父节点，用u1和u2表示它的两个子节点，如果有的话。 注意，非叶节点u有两个子节点u1和u2，非根节点u有其父节点u0。对于非根节点u，设e0为{u，u0}。通过删除T中的e0，我们得到两个子树。用T0表示不包含根的，用L0表示不包含T0的叶的集合，用E0表示不包含φ−1（L0）的。对于根节点u，我们设置E0：=E。我们的算法计算非循环和全循环方向的数量，通过执行动态规划的分支分解在自底向上的方式从叶子到根。在开始动态规划之前，我们为每个节点u准备一个数组DPu。如果节点u不是根，则数组DPu由集合{0，1，2，3}Wu索引，其中Wu={（a，b）∈mid（e0）2：

下载后可阅读完整内容，剩余1页未读，立即下载