Tree-partite graphs and the complexity of algorithms.

*(English)*Zbl 0574.68036
Fundamentals of computation theory, Proc. 5th Int. Conf., Cottbus/Ger. 1985, Lect. Notes Comput. Sci. 199, 412-421 (1985).

[For the entire collection see Zbl 0568.00020.]

A lot of algorithmic problems in graph theory are NP-hard and have (at least till now) no solutions in polynomial time. Many of them remain even NP-hard if they are restricted to smaller and simpler classes of graphs. But if the regarded class of graphs is very simple, as for instance the class of trees, or the class of series-parallel graphs, then some of the NP-hard problems have solutions in polynomial or even in linear time. This suggests the problem to find a structural reason for this behaviour of these algorithmic problems. The present paper tries to give a partial answer to this problem.

A lot of algorithmic problems in graph theory are NP-hard and have (at least till now) no solutions in polynomial time. Many of them remain even NP-hard if they are restricted to smaller and simpler classes of graphs. But if the regarded class of graphs is very simple, as for instance the class of trees, or the class of series-parallel graphs, then some of the NP-hard problems have solutions in polynomial or even in linear time. This suggests the problem to find a structural reason for this behaviour of these algorithmic problems. The present paper tries to give a partial answer to this problem.