zbMATH — the first resource for mathematics

Domination problems with no conflicts. (English) Zbl 1387.05181
Summary: Domination problems have been studied in graph theory for decades. In most of them, it is NP-complete to find an optimal solution, while it is easy (and even trivial in some cases) to find a solution in polynomial time, regardless of its size.
In recent works, authors added conflicts to classical discrete optimization problems. In this paper, a conflict is a pair of vertices that cannot be both in a solution. Set of conflicts can be viewed as edges of a so called conflict graph. An instance is then a support graph and a conflict graph. With these new constraints, the existence of a solution (dominating set or independent dominating set) with no conflicts is no more guaranteed. We explore this subject and we prove that it is NP-complete to decide the existence of a solution even in very restricted classes of graphs and conflicts (sparse or dense). We also propose polynomial algorithms for some sub-cases, using deterministic finite automata.
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Full Text: DOI
[1] Ausiello, G.; Crescenzi, P.; Gambosi, G.; Kann, V.; Marchetti-Spaccamela, A.; Protasi, M., Complexity and approximation: combinatorial optimization problems and their approximability properties, (2012), Springer Science & Business Media · Zbl 0937.68002
[2] Cornet, A.; Laforest, C., Total domination, connected vertex cover and Steiner tree with conflicts, Discrete Math. Theor. Comput. Sci., 19, 3, (2017) · Zbl 1401.05214
[3] F. Delbot, C. Laforest, R. Phan, Hardness Results and Approximation Algorithms for Discrete Optimization Problems with Conditional and Unconditional Forbidden Vertices, Research Report (Jan. 2016) 2016. URL https://hal.archives-ouvertes.fr/hal-01257820.
[4] Gabow, H. N.; Maheshwari, S. N.; Osterweil, L. J., On two problems in the generation of program test paths, IEEE Trans. Softw. Eng., 3, 227-231, (1976)
[5] Haynes, T. W.; Hedetniemi, S.; Slater, P., Fundamentals of domination in graphs, (1998), CRC Press · Zbl 0890.05002
[6] M.M. Kanté, C. Laforest, B. Momège, An exact algorithm to check the existence of (elementary) paths and a generalisation of the cut problem in graphs with forbidden transitions, in: SOFSEM 2013, 2013, pp. 257-267. · Zbl 1303.05194
[7] M.M. Kanté, C. Laforest, B. Momège, Trees in graphs with conflict edges or forbidden transitions, in: TAMC 2013, Hong Kong, 2013, pp. 343-354.
[8] M.M. Kanté, F.Z. Moataz, B. Momège, N. Nisse, Finding paths in grids with forbidden transitions, in: WG 2015, 2015, pp. 154-168.
[9] Kolman, P.; Pangrác, O., On the complexity of paths avoiding forbidden pairs, Discrete Appl. Math., 157, 13, 2871-2876, (2009) · Zbl 1209.05245
[10] Kováč, J., Complexity of the path avoiding forbidden pairs problem revisited, Discrete Appl. Math., 161, 10, 1506-1512, (2013) · Zbl 1287.05071
[11] C. Laforest, B. Momège, Some hamiltonian properties of one-conflict graphs, in: IWOCA 2014, 2014, pp. 262-273. · Zbl 1401.05174
[12] C. Laforest, B. Momège, Nash-Williams-type and Chvátal-type conditions in one-conflict graphs, in: SOFSEM 2015, 2015, pp. 327-338. · Zbl 1435.05124
[13] Linz, P., An introduction to formal languages and automata, (2011), Jones & Bartlett Publishers
[14] Tovey, C. A., A simplified NP-complete satisfiability problem, Discrete Appl. Math., 8, 1, 85-89, (1984) · Zbl 0534.68028
[15] Yinnone, H., On paths avoiding forbidden pairs of vertices in a graph, Discrete Appl. Math., 74, 1, 85-92, (1997) · Zbl 0878.68091
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.