Computational complexity of graph orientation, bilevel and robust optimization problems

RWTH Publications (RWTH Aachen)

Abstract

The goal of this thesis is twofold. We study two types of computational problems: first, a decision problem, which is a graph orientation problem, and second, optimization problems in the realm of bilevel optimization and robust optimization. We derive a host of hardness and tractability results for a bunch of combinatorial problems within these two settings. Our completeness results span over the first and the second level of the polynomial hierarchy; we obtain $\mathsf{NP}$-complete and $\Sigma_2^\mathsf{p}$-complete results. For the graph orientation problem, we study SC-Orientation (SCO) wherein the task is to determine whether we can make an undirected graph 'singly connected' by means of edge orientations; a digraph $D$ is said to be singly connected if for each (ordered) pair of vertices $s, t \in V(D)$, there is at most one path from $s$ to $t$ in $D$. Our main result concerns graphs of a fixed girth $g$ and coloring number $c$. For every $g,c\geq 3$, the problem restricted to the graph class $\mathcal{G}_{g,c}$, which consists of instances of girth $g$ and coloring number $c$, is either $\mathsf{NP}$-complete or in $\mathsf{P}$. Not only that, but when SCO is in $\mathsf{P}$ on $\mathcal{G}_{g,c}$, we show that $\mathcal{G}_{g,c}$ contains only yes-instances of SCO. It is noteworthy that our hardness result relies on the existence of a solitary no-instance of SCO in $\mathcal{G}_{g,c}$. The results of this nature—either $\mathsf{NP}$-complete or all yes-instances—are rare in the field of computational complexity. Further, we consider bilevel optimization problems in which the ground set is partitioned between two decision makers whose objective functions are nested into each other. We study the bilevel versions of the assignment, interval scheduling, and independent set problems, and categorize them into their respective complexity classes. One result that stands out here is that Bilevel Interval Scheduling does not increase the complexity of the problem (both the underlying problem and its bilevel version are in $\mathsf{P}$), whereas Bilevel Independent Set goes from $\mathsf{NP}$-hard to $\Sigma_2^\mathsf{p}$-hard for the setting in which both decision makers have sum type objective functions. Lastly, within the setting of adversarial optimization under uncertainty, we introduce a model called recoverable robust optimization with commitment. Ours is a recoverable robust optimization model, in which the recovered solution must contain all surviving elements chosen in the initial solution. We study our model on different combinatorial optimization problems from the algorithmic and complexity perspective.

Authors 1

1. Komal Muluk corresponding Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen