Operations Research 2025
Abstract Submission

248. On the Complexity of Graph-Theoretic Versions of Partial Scenario Set Cover

Invited abstract in session TA-2: Combinatorial Optimization, stream Discrete and Combinatorial Optimization.

Thursday, 8:45-10:15
Room: H4

Authors (first author is the speaker)

1. Shai Dimant
Department Mathematics, AG OPT, RPTU Kaiserslautern
2. Sven Krumke
Mathematics, University of Kaiserslautern

Abstract

The Partial Scenario Set Cover problem (PSSC) is a known generalization of the (partial) set cover problem. We are given a finite ground set Q, a collection S of subsets of Q with associated nonnegative costs, and a second collection U of subsets of Q. The goal is to select a minimum-cost sub-collection of S that covers at least l sets from U.

The Smallest k-Edge Subgraph Problem (S-k-ES) is a special case of the PSSC in which the scenarios are given by single edges and the nodes play the role of the sets. The S-k-ES can be solved in polynomial time on graphs of bounded treewidth. This raises the question of whether graph-theoretic versions of PSSC can be solved in polynomial time on treewidth bounded graphs as well.

We first consider a generalization of the classical Steiner Tree problem, where given a graph G = (V,E), a non-negative cost function c on E and a subset R of vertices, the goal is to find a minimum cost subtree of G containing all terminal nodes, i.e. all nodes from R. In our problem, called Partial Scenario Steiner Tree (PSST), the terminal set R is uncertain: One is given a collection U of (terminal set) scenarios and the goal is to find a minimum cost subtree of G which completely contains at least a prespecified number l of the scenarios from U. The PSST is again a graph-theoretic special case of the PSSC.
We show that while PSST is trivial on path graphs and can be solved in polynomial time on trees when U is a subset of edges, it becomes NP-hard already on star graphs when this assumption is dropped, even when all scenarios are still of size 2. We identify a class of complicating scenarios whose number if constant, makes the problem polynomial time solvable. We then generalize our results to other graph-theoretic versions of PSSC.

Keywords

Status: accepted

Back to the list of papers