On the (Parameterized) Complexity of Recognizing Well-Covered $$(r,\ell )$$ -graphs

DOI10.1007/978-3-319-48749-6_31zbMath1483.68247arXiv1705.09177OpenAlexW2540507702MaRDI QIDQ2958335

Sancrey Rodrigues Alves, Uéverton dos Santos Souza, Sulamita Klein, Ignasi Sau, Konrad K. Dabrowski, Luérbio Faria

Publication date: 1 February 2017

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1705.09177

zbMATH Keywords

coNP-completenessparameterized complexitypolynomial kernelwell-covered graphFPT-algorithm\((r,\ell)\)-graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (3)

Integer programming in parameterized complexity: five miniatures ⋮ Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity ⋮ On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph

Cites Work

• A generalization of Villarreal's result for unmixed tripartite graphs
• AND-compression of NP-complete problems: streamlined proof and minor observations
• Fundamentals of parameterized complexity
• List matrix partitions of chordal graphs
• On problems without polynomial kernels
• Algorithmic meta-theorems for restrictions of treewidth
• Very well covered graphs
• Partitions of graphs into one or two independent sets and cliques
• Well-covered claw-free graphs
• New Limits to Classical and Quantum Instance Compression
• Complexity results for well‐covered graphs
• List Partitions
• Parameterized Algorithms on Perfect Graphs for Deletion to (r,l)-Graphs
• Paths, Trees, and Flowers
• Parameterized Algorithms
• Some covering concepts in graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the (Parameterized) Complexity of Recognizing Well-Covered $$(r,\ell )$$ -graphs