Upper Domination: Towards a Dichotomy Through Boundary Properties
| Autor: | Victor Zamaraev, Jérôme Monnot, Shahid Hussain, Bernard Ries, Vadim V. Lozin, Hassan AbouEisha |
|---|---|
| Přispěvatelé: | Center for Numerical Porous Media (NumPor) - King Abdullah University of Science and Technology, King Abdullah University of Science and Technology (KAUST), autre, AUTRES, Warwick Mathematics Institute (WMI), University of Warwick [Coventry], Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), University of Fribourg, Albert-Ludwigs-Universität Freiburg |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) General Computer Science Boundary (topology) 0102 computer and information sciences NP-hard 01 natural sciences Combinatorics Cardinality Dominating set Upper dominating set TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Boundary class [INFO]Computer Science [cs] 0101 mathematics QA Mathematics Conjecture Applied Mathematics 010102 general mathematics Graph Computer Science Applications 010201 computation theory & mathematics Theory of computation Complexity dichotomy MathematicsofComputing_DISCRETEMATHEMATICS Computer Science - Discrete Mathematics |
| Zdroj: | ALGORITHMICA Algorithmica Algorithmica, 2018, 80 (10), ⟨10.1007/s00453-017-0346-9⟩ |
| ISSN: | 0178-4617 |
| Popis: | The results of this paper previously appeared as extended abstracts in proceedings of the 8th International Conference on Combinatorial Optimization and Applications, COCOA 2014, and the 27th International Workshop on Combinatorial Algorithms, IWOCA 2016.; An upper dominating set in a graph is a minimal dominating set of maximum cardinality. The problem of finding an upper dominating set is generally NP-hard. We study the complexity of this problem in finitely defined classes of graphs and conjecture that the problem admits a complexity dichotomy in this family. A helpful tool to study the complexity of an algorithmic problem is the notion of boundary classes. However, none of such classes has been identified so far for the upper dominating set problem. We discover the first boundary class for this problem and prove the dichotomy for monogenic classes. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink