Kernelization and approximation of distance-r independent sets on nowhere dense graphs
作者： Michał Pilipczuk , Sebastian Siebertz
DOI: 10.1016/J.EJC.2021.103309
关键词: Mathematics 、 Combinatorics 、 Kernel (set theory) 、 Nowhere dense set 、 Independent set 、 Vertex (geometry) 、 Duality (order theory) 、 Dominating set 、 Integer 、 Kernelization
摘要: Abstract For a positive integer r , distance- independent set in an undirected graph G is I ⊆ V ( ) of vertices pairwise at distance greater than while dominating D such that every vertex the graph within most from . We study duality between maximum size 2 and minimum nowhere dense classes, as well kernelization complexity problem on these classes. Specifically, we prove admits almost linear kernel graph class.
sci-hub.st 参考文章(35)
Nicolas Bousquet, Stéphan Thomassé, VC-dimension and Erdős-Pósa property Discrete Mathematics. ,vol. 338, pp. 2302- 2317 ,(2015) , 10.1016/J.DISC.2015.05.026
Nicholas Wormald, Noga Alon, High Degree Graphs Contain Large-Star Factors Fete of Combinatorics and Computer Science. pp. 9- 21 ,(2010) , 10.1007/978-3-642-13580-4_1
Patrice Ossona de Mendez, Jaroslav Neetil, Sparsity: Graphs, Structures, and Algorithms ,(2012)
Nicholas C. Wormald, Some problems in the enumeration of labelled graphs Bulletin of The Australian Mathematical Society. ,vol. 21, pp. 159- 160 ,(1980) , 10.1017/S0004972700011436
Jaroslav Nešetřil, Patrice Ossona de Mendez, Grad and classes with bounded expansion I. Decompositions The Journal of Combinatorics. ,vol. 29, pp. 760- 776 ,(2008) , 10.1016/J.EJC.2006.07.013
Jaroslav Nešetřil, Patrice Ossona de Mendez, On nowhere dense graphs The Journal of Combinatorics. ,vol. 32, pp. 600- 617 ,(2011) , 10.1016/J.EJC.2011.01.006
Victor Chepoi, Bertrand Estellon, Yann Vaxes, Covering Planar Graphs with a Fixed Number of Balls Discrete and Computational Geometry. ,vol. 37, pp. 237- 244 ,(2007) , 10.1007/S00454-006-1260-0
Ran Raz, Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP symposium on the theory of computing. pp. 475- 484 ,(1997) , 10.1145/258533.258641
H. Brönnimann, M. T. Goodrich, Almost optimal set covers in finite VC-dimension Discrete and Computational Geometry. ,vol. 14, pp. 463- 479 ,(1995) , 10.1007/BF02570718
M.R. Garey, D.S. Johnson, L. Stockmeyer, Some simplified NP-complete graph problems Theoretical Computer Science. ,vol. 1, pp. 237- 267 ,(1976) , 10.1016/0304-3975(76)90059-1