Vi studerar den minsta spännvidd träd problem, den maximala matchning problem och den kortaste vägen problemet med binära diskonterande begränsningar: En negativ disjunktiv begränsning anger att ett visst par kanter inte kan inneslutas samtidigt i en genomförbar lösning. Det är praktiskt att representera dessa negativa disjunktiva begränsningar i termer av en så kallad konfliktgraf vars hörn motsvarar kanterna på den underliggande grafen, och vars kanter kodar begränsningarna. Vi bevisar att minsta spännvidd träd problemet är starkt N Phard, även om varje ansluten komponent i konfliktgrafen är en väg av längd två. På den positiva sidan är detta problem polynomiskt lösbar om varje ansluten komponent är en enda kant (det vill säga en väg av längd ett). Det maximala matchningsproblemet är N P-hard för konfliktgrafer där varje ansluten komponent är en enda kant. Dessutom kommer vi att undersöka dessa grafproblem under positiva disjunktiva begränsningar: I denna inställning för vissa par av kanter, en genomförbar lösning måste innehålla minst en kant från varje par. Vi etablerar ett antal komplexa resultat för dessa varianter inklusive APX-hårdhet för den kortaste vägen problem.
Darmann m.fl. REF studerar hårdheten av det maximala matchningsproblemet med den ytterligare strukturen av konflikt (respektive, tvingar) diagram.
Paths, trees and matchings under disjunctive constraints
{'venue': 'Discret. Appl. Math.', 'journal': 'Discret. Appl. Math.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}