← 研踪 PaperTrailarXiv:1803.06878 · v5
Parameterized Complexity of Fair Vertex Evaluation Problems
首次提交 2018-03-19 19:49
版本更新 2026-11-05 20:53
雷达观测 2026-11-06 12:09
摘要
Graph modification problems form a unifying framework for many classical graph problems, where the goal is to remove a minimum number of vertices so that the resulting graph satisfies a desired property $π$. In this work, we replace the classical objective of minimizing the solution size with the fair objective [Lin&Sahni: Fair edge deletion problems. IEEE Trans. Comput. 89], which minimizes the maximum number of deleted neighbors incident to any vertex. This fairness criterion aims to distribute deletions evenly across the graph and leads to new algorithmic and complexity challenges. We study fair deletion and evaluation problems in the logical setting, where the target property~$π$ is defined by a formula in a logic $\mathsf{L}$. In particular, we consider the Fair $\mathsf{L}$ Vertex Evaluation problem, which asks whether there exists a vertex set $W$ of bounded fair cost such that a given formula $\varphi(X)$ holds in the input graph $G$. Our main result is an FPT algorithm for the Fair MSO$_1$ Vertex Evaluation problem with one free variable, parameterized by the twin cover number of the input graph and the quantifier length of the formula. We further show that extending this result to formulas with $\ell$ free variables is unlikely: the $\ell$-Fair FO Vertex Evaluation problem is W[1]-hard for parameter $\ell$ even on graphs of twin cover one. As a concrete case study, we investigate the Fair Vertex Cover}\ problem, one of the simplest fairness-aware graph problems. We prove that it is W[1]-hard when parameterized by the combined treedepth and feedback vertex set, but admits an FPT algorithm for the parameter modular width.
作者备注：25 pages, 5 figures, presented at MFCS 2019
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v5 · 2026-11-05 20:53 · 最新观测版本
Parameterized Complexity of Fair Vertex Evaluation Problems
Graph modification problems form a unifying framework for many classical graph problems, where the goal is to remove a minimum number of vertices so that the resulting graph satisfies a desired property $π$. In this work, we replace the classical objective of minimizing the solution size with the fair objective [Lin&Sahni: Fair edge deletion problems. IEEE Trans. Comput. 89], which minimizes the maximum number of deleted neighbors incident to any vertex. This fairness criterion aims to distribute deletions evenly across the graph and leads to new algorithmic and complexity challenges. We study fair deletion and evaluation problems in the logical setting, where the target property~$π$ is defined by a formula in a logic $\mathsf{L}$. In particular, we consider the Fair $\mathsf{L}$ Vertex Evaluation problem, which asks whether there exists a vertex set $W$ of bounded fair cost such that a given formula $\varphi(X)$ holds in the input graph $G$. Our main result is an FPT algorithm for the Fair MSO$_1$ Vertex Evaluation problem with one free variable, parameterized by the twin cover number of the input graph and the quantifier length of the formula. We further show that extending this result to formulas with $\ell$ free variables is unlikely: the $\ell$-Fair FO Vertex Evaluation problem is W[1]-hard for parameter $\ell$ even on graphs of twin cover one. As a concrete case study, we investigate the Fair Vertex Cover}\ problem, one of the simplest fairness-aware graph problems. We prove that it is W[1]-hard when parameterized by the combined treedepth and feedback vertex set, but admits an FPT algorithm for the parameter modular width.
查看此版本解读 →查看此版本原文 ↗