Abstrakt
Pro daný graf G=(V,E) se dvěma vybranými vrcholy s,t, a pro množinu dvojic vrcholů F (tzv. zakázané dvojice), problém cesty se zakázanými dvojicemi spočívá v hledání cesty mezi vrcholy s a t takové, že z každé zakázané dvojice používá nejvýšše jeden vrchol. V obecnosti jde o NP-těžký problém. Článek se studuje složitost problému vzhledem ke struktuře zakázaných dvojic.