近日，实验室张鹏副教授作为第一作者和通讯作者在理论计算机科学领域顶级期刊IANDC（Information and Computation）上发表文章“Minimum label s-t cut has large integrality gaps”，揭示了标签割问题的计算困难性问题。山东大学为该论文的第一作者单位，中国科学院软件研究所为合作单位。

标签s-t割问题是一个来自于系统安全、计算机网络等领域典型的组合优化问题。在系统安全领域，入侵者对系统的攻击可用一个有向图来表示。入侵者一开始处于初始状态s，若其到达了成功状态t，就表明入侵者成功侵入了系统。从一个状态开始，入侵者施加一种攻击手段，就可以变换到另一个状态。系统防御者的任务在于，如何以最小的代价破坏入侵者的某些攻击手段，或者通过增加自身防御使入侵者的某些攻击手段无效，使入侵者不能到达成功状态。用顶点表示状态，用有向边表示状态的变迁，边上的标签表示攻击手段，就得到了一个带有标签的有向图。于是防御者的任务就可以描述为，找最小费用的一组标签，使得在图上去掉具有这些标签的边之后，顶点s和顶点t不连通。这恰好就是标签s-t割问题。可以看出，标签s-t割问题是经典的最小s-t割问题的推广。

已经证明标签s-t割问题是NP困难的。因此，近似算法就成为求解标签s-t割问题的一种常规途径。基于线性规划的技术是设计NP困难问题近似算法的一种强有力的技术，得到了广泛的应用。使用概率的方法，张鹏副教授及其合作者在论文中证明了，标签s-t割问题的一种自然的线性规划的整性间隙至少为Omega(m^1/3)，m为图上的边的数目。这一结果表明，如果使用纯粹的线性规划技术为标签s-t割问题设计近似算法，近似比不会好于Omega(m^1/3)。这从线性规划的角度揭示了标签s-t割问题具有很高的计算困难性。

IANDC是中国计算机学会认定的理论计算机科学领域的A类顶级期刊。理论计算机科学在传统上是数学的一个分支，该领域多是困难的理论研究问题，研究工作难度大，论文审稿周期长。IANDC平均每年发表论文不足一百篇，其中来自国内科研单位的论文仅为极少数。2018年和2019年国内科研单位在IANDC上发表的论文分别为3篇、4篇，论文作者来自于上海交通大学、南京大学、中科院软件所等国内著名高校和科研院所。本项研究是山东大学软件学院首次在理论计算机科学方向CCF-A类出版物（含期刊和会议）上发表论文，该工作得到了国家自然科学基金、山东省自然科学基金和山东大学基础科研业务费用的支持。

文章链接：https://www.sciencedirect.com/science/article/pii/S0890540120300316