Deconstructing parameterized hardness of fair vertex deletion problems. (English) Zbl 1534.68175
Du, Ding-Zhu (ed.) et al., Computing and combinatorics. 25th international conference, COCOON 2019, Xi’an, China, July 29–31, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11653, 325-337 (2019).
Summary: For a graph \(G\) and a positive integer \(d\), a set \(S\subseteq V(G)\) is a fair set with the fairness factor \(d\) if for every vertex in \(G\), at most \(d\) of its neighbors are in the \(S\). In the \({\varPi}\)-Vertex Deletion problem, the aim is to find in a given graph a set \(S\) of minimum size such that \(G\setminus S\) satisfies the property \({\varPi}\). We look at \({\varPi}\)-Fair Vertex Deletion problem where we also want \(S\) to be a fair set.
It is known that the general \({\varPi}\)-Fair Vertex Deletion problem where \({\varPi}\) is expressible by a first order formula and is also given as input is W[1]-hard when parameterized by treewidth. Our first observation is that if we also parameterize by the fairness constant \(d\), then \({\varPi}\)-Fair Vertex Deletion is FPT (fixed-parameter tractable) even if \({\varPi}\)-Vertex Deletion can be expressed by a Monadic Second Order (MSO) formula. As a corollary we get an FPT algorithm for Fair Feedback Vertex Set (FFVS) and Fair Vertex Cover (FVC) parameterized by solution size.
We then do a deep dive on FVC and more generally \({\varPi}\)-Fair Vertex Deletion problems parameterized by solution size \(k\) when \({\varPi}\) is characterized by a finite set of forbidden graphs. We show that these problems are FPT and develop a polynomial kernel when \(d\) is a constant. While the FPT algorithms use the standard branching technique, the fairness constraint introduces challenges to design a polynomial kernel. En route, we give a polynomial kernel for a special instance of Min-Ones-SAT and Fair \(q\)-Hitting Set, a generalization of \(q\)-hitting set, with a fairness constraint on an underlying graph structure on the universe. These could be of independent interest.
To complement our FPT results, we show that Fair Set and Fair Independent Set problems are W[1]-hard even in 3-degenerate graphs when the fairness factor is 1. We also show that FVC is polynomial-time solvable when \(d=1\) or 2, and NP-hard for \(d\ge 3\), and that FFVS is NP-hard for all \(d\ge 1\).
For the entire collection see [Zbl 1416.68009].
It is known that the general \({\varPi}\)-Fair Vertex Deletion problem where \({\varPi}\) is expressible by a first order formula and is also given as input is W[1]-hard when parameterized by treewidth. Our first observation is that if we also parameterize by the fairness constant \(d\), then \({\varPi}\)-Fair Vertex Deletion is FPT (fixed-parameter tractable) even if \({\varPi}\)-Vertex Deletion can be expressed by a Monadic Second Order (MSO) formula. As a corollary we get an FPT algorithm for Fair Feedback Vertex Set (FFVS) and Fair Vertex Cover (FVC) parameterized by solution size.
We then do a deep dive on FVC and more generally \({\varPi}\)-Fair Vertex Deletion problems parameterized by solution size \(k\) when \({\varPi}\) is characterized by a finite set of forbidden graphs. We show that these problems are FPT and develop a polynomial kernel when \(d\) is a constant. While the FPT algorithms use the standard branching technique, the fairness constraint introduces challenges to design a polynomial kernel. En route, we give a polynomial kernel for a special instance of Min-Ones-SAT and Fair \(q\)-Hitting Set, a generalization of \(q\)-hitting set, with a fairness constraint on an underlying graph structure on the universe. These could be of independent interest.
To complement our FPT results, we show that Fair Set and Fair Independent Set problems are W[1]-hard even in 3-degenerate graphs when the fairness factor is 1. We also show that FVC is polynomial-time solvable when \(d=1\) or 2, and NP-hard for \(d\ge 3\), and that FFVS is NP-hard for all \(d\ge 1\).
For the entire collection see [Zbl 1416.68009].
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 03B70 | Logic in computer science |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q27 | Parameterized complexity, tractability and kernelization |
References:
| [1] | Alambardar Meybodi, M., Fomin, F., Mouawad, A.E., Panolan, F.: On the parameterized complexity of [1, j]-domination problems. In: FSTTCS 2018 (2018) |
| [2] | Buss, JF; Goldsmith, J.; Choffrut, C.; Jantzen, M., Nondeterminism within P, STACS 91, 348-359, 1991, Heidelberg: Springer, Heidelberg · Zbl 0773.68030 · doi:10.1007/BFb0020811 |
| [3] | Courcelle, B., The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Inf. Comput., 85, 1, 12-75, 1990 · Zbl 0722.03008 · doi:10.1016/0890-5401(90)90043-H |
| [4] | Cygan, M., Parameterized Algorithms, 2015, Cham: Springer, Cham · Zbl 1334.90001 · doi:10.1007/978-3-319-21275-3 |
| [5] | Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: FOCS, pp. 150-159. IEEE (2011) · Zbl 1292.68122 |
| [6] | Diestel, R., Graph Theory, 2005, Heidelberg: Springer, Heidelberg · Zbl 1074.05001 |
| [7] | Fellows, MR; Jansen, BM; Rosamond, F., Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity, Eur. J. Comb., 34, 3, 541-566, 2013 · Zbl 1448.68465 · doi:10.1016/j.ejc.2012.04.008 |
| [8] | Garey, MR; Johnson, DS; Stockmeyer, L., Some simplified NP-complete graph problems, TCS, 1, 3, 237-267, 1976 · Zbl 0338.05120 · doi:10.1016/0304-3975(76)90059-1 |
| [9] | Knop, D.; Koutecký, M.; Masařík, T.; Toufar, T.; Bodlaender, HL; Woeginger, GJ, Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity, Graph-Theoretic Concepts in Computer Science, 344-357, 2017, Cham: Springer, Cham · Zbl 1484.68072 · doi:10.1007/978-3-319-68705-6_26 |
| [10] | Knop, D., Masarík, T., Toufar, T.: Parameterized complexity of fair deletion problems II. CoRR abs/1803.06878 (2018) |
| [11] | Kolman, P., Lidickỳ, B., Sereni, J.S.: On fair edge deletion problems. Manuscript (2009). http://kam.mff.cuni.cz/kolman/papers/kls09.pdf |
| [12] | Kratsch, S.; Wahlström, M., Two edge modification problems without polynomial kernels, Discrete Optim., 10, 3, 193-199, 2013 · Zbl 1506.68040 · doi:10.1016/j.disopt.2013.02.001 |
| [13] | Lewis, JM; Yannakakis, M., The node-deletion problem for hereditary properties is NP-complete, JCSS, 20, 2, 219-230, 1980 · Zbl 0436.68029 |
| [14] | Lin, L.; Sahni, S., Fair edge deletion problems, IEEE Trans. Comput., 38, 5, 756-761, 1989 · Zbl 1395.68213 · doi:10.1109/12.24280 |
| [15] | Masařík, T.; Toufar, T.; Gopal, TV; Jäger, G.; Steila, S., Parameterized complexity of fair deletion problems, Theory and Applications of Models of Computation, 628-642, 2017, Cham: Springer, Cham · Zbl 1485.68192 · doi:10.1007/978-3-319-55911-7_45 |
| [16] | Rizzi, R., Minimum weakly fundamental cycle bases are hard to find, Algorithmica, 53, 3, 402-424, 2009 · Zbl 1172.68026 · doi:10.1007/s00453-007-9112-8 |
| [17] | Telle, JA, Complexity of domination-type problems in graphs, Nord. J. Comput., 1, 1, 157-171, 1994 |
| [18] | van Rooij, JMM; Bodlaender, HL; Rossmanith, P.; Fiat, A.; Sanders, P., Dynamic programming on tree decompositions using generalised fast subset convolution, Algorithms - ESA 2009, 566-577, 2009, Heidelberg: Springer, Heidelberg · Zbl 1256.68157 · doi:10.1007/978-3-642-04128-0_51 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
