Minimaximal and maximinimal optimisation problems: a partial order-based approach

David F. Manlove¹

Department of Computing Science, University of Glasgow, Glasgow G12 8QQ, Scotland.
Email: davidm@dcs.gla.ac.uk.

Abstract

We study a class of optimisation problems called minimaximal and maximinimal optimisation problems. Such a problem $\Pi'$ may be obtained from an optimisation problem $\Pi$, called the source optimisation problem, by defining a partial order $\prec^{x}$ on the set of feasible solutions ${\cal F}(x)$ for a given instance x of $\Pi$. If the objective of $\Pi$ is to maximise (respectively minimise) the measure over ${\cal F}(x)$, then the objective of $\Pi'$is to minimise (maximise) the measure over all elements of ${\cal F}(x)$ that are maximal (minimal) with respect to $\prec^{x}$. Many optimisation problems occurring in the literature are minimaximal or maximinimal optimisation problems.

In this thesis, we present the first unifying framework for formulating minimaximal and maximinimal optimisation problems, based on this partial order concept. To accompany this framework, we define a variety of partial orders, an important example being the partial order of set inclusion. By considering various source optimisation problems from the literature, and partial orders from our collection, we use our framework to obtain a range of minimaximal and maximinimal optimisation problems. We study these individual examples mainly from the point of view of algorithmic complexity.

The series of examples begins with the source optimisation problem CHROMATIC NUMBER, whose objective is to minimise the number of colours over all proper colourings of a given graph. A related problem is ACHROMATIC NUMBER, in which we seek to maximise the number of colours over all proper colourings of a given graph G such that each pair of distinct colours occurs at the endpoints of some edge of G. We show that ACHROMATIC NUMBER is a maximinimal counterpart of CHROMATIC NUMBER, by defining a partition-related partial order on the set of all proper colourings of G. A natural refinement of this partial order gives rise to an additional maximinimal optimisation problem concerned with graph colouring, which we call B-CHROMATIC NUMBER. The objective of this problem is to maximise the number of colours over all proper colourings of G such that for each colour i, there is a distinguished vertex of colour i that is adjacent to a vertex of every colour $j\neq i$. Whilst the ACHROMATIC NUMBER problem has been studied for over thirty years, the B-CHROMATIC NUMBER problem is new. We show that the decision version of B-CHROMATIC NUMBER is NP-complete in arbitrary graphs, and also bipartite graphs. However, we prove that B-CHROMATIC NUMBER is solvable in polynomial time for trees, in contrast with ACHROMATIC NUMBER.

Many other examples of minimaximal and maximinimal optimisation problems relating to graph parameters have already been studied in the literature. We focus on graph-theoretic minimaximal and maximinimal optimisation problems that may be obtained from source optimisation problems using the partial order of set inclusion. In particular, we investigate source optimisation problems and their minimaximal or maximinimal counterparts relating to vertex, edge and total covers, and independent sets, matchings and total matchings in a graph. Each of the twelve optimisation problems implied by the previous sentence has been studied in some form in the literature. We review existing complexity results and obtain a number of new results, namely NP-completeness proofs for the decision versions of MAXIMUM MINIMAL TOTAL COVER in planar graphs, MINIMUM MAXIMAL TOTAL MATCHING in bipartite and chordal graphs, and MINIMUM INDEPENDENT DOMINATING SET (or MINIMUM MAXIMAL INDEPENDENT SET) in planar cubic graphs.

We also study source optimisation problems and their minimaximal or maximinimal counterparts relating to strong stable sets, cliques, dominating sets, total dominating sets, edge dominating sets and irredundant sets in a graph. Again, we survey existing algorithmic results, if any, for the twelve implicit optimisation problems, and obtain several new results, namely NP-completeness proofs for the decision versions of MINIMUM MAXIMAL STRONG STABLE SET in planar graphs of maximum degree 3, MINIMUM MAXIMAL CLIQUE in general graphs, and MINIMUM TOTAL DOMINATING SET in planar cubic graphs.

For a graph G=(V,E), a refinement of the notion of an independent set that is maximal with respect to the partial order of set inclusion has been considered in the literature. An independent set $S\subseteq V$ is k-maximal ($k\geq 1$) if the removal of any r-1 vertices from S, together with the addition of any r vertices from $V\backslash S$(for any $r\leq k$), results in a non-independent set. We consider minimaximal optimisation problems related to finding minimum cardinality k-maximal independent sets in a graph. We focus mainly on the case k=2, and prove that the decision version of the problem of determining the minimum size of a 2-maximal independent set is NP-complete, even for planar graphs of maximum degree 3. However, for trees, we give a linear-time algorithm.

Many integer-valued graph parameters have fractional counterparts in the literature. We define the concept of fractional graph optimisation problems, relating to fractional graph parameters, and show how minimaximal and maximinimal versions may be defined, using a partial order on functions. We formulate several examples of such problems using the framework, and by considering appropriate linear programming constructions, we show that the optimal measure (the solution to the evaluation version of the minimaximal or maximinimal fractional graph optimisation problem concerned) is computable, has rational values, and is attained by some function of compact representation which satisfies the feasibility constraint for the minimaximal or maximinimal fractional graph optimisation problem concerned. These three issues have implications for the algorithmic behaviour of a minimaximal or maximinimal fractional graph optimisation problem. We also survey complexity results relating to the source fractional graph optimisation problems and their minimaximal or maximinimal counterparts that we define.

Minimaximal and maximinimal optimisation problems that relate to areas other than the domain of graph theory are also studied in this thesis. By considering source optimisation problems belonging to the Garey and Johnson [Computers and Intractability, Freeman, 1979] problem categories of Network Design, Sets and Partitions, Data Storage, Compression and Representation, Mathematical Programming, and Logic, and by imposing various partial orders, we formulate a range of natural minimaximal and maximinimal optimisation problems. These interesting individual examples, most of which are new, are minimaximal or maximinimal versions of the following problems (Garey and Johnson problem numbers in brackets): LONGEST PATH (ND29), 3 D-MATCHING (SP1), MINIMUM TEST SET (SP6), BIN PACKING (SR1), KNAPSACK (MP9), MAXIMUM 2 -SAT (LO5), ONE-IN-THREE 3 SAT (LO4), LONGEST COMMON SUBSEQUENCE (SR10), SHORTEST COMMON SUPERSEQUENCE (SR8), LONGEST COMMON SUBSTRING (SR10) and SHORTEST COMMON SUPERSTRING (SR9). We survey complexity results for the source optimisation problem $\Pi$ in each case, and also those, if any, for the minimaximal or maximinimal counterpart(s) of $\Pi$. We obtain new NP-completeness results for minimaximal or maximinimal versions of the first seven problems in the above list, and construct a polynomial-time algorithm for a minimaximal counterpart of LONGEST COMMON SUBSTRING.

We also consider the computational complexity of minimaximal and maximinimal optimisation problems from a more general viewpoint. We present conditions under which a Turing reduction from an optimisation problem, $\Pi_{1}$, to another, $\Pi_{2}$, is also a Turing reduction from $\Pi_{1}'$ to $\Pi_{2}'$, where $\Pi_{i}'$ is a minimaximal or maximinimal version of $\Pi_{i}$ (i=1,2). We call Turing reductions satisfying these additional constraints MM-reductions. Some examples of MM-reductions are given, involving several partial orders, and involving source optimisation problems from a variety of domains.

Additionally, we discuss the question of how, in general, we may test a feasible solution of an optimisation problem $\Pi$ for maximality or minimality, and how we may find feasible solutions that are maximal or minimal, with respect to a partial order defined on the feasible solutions of $\Pi$for a given instance. In particular, we examine this question when $\Pi$ is BIN PACKING and when $\Pi$ is CHROMATIC NUMBER.

We show that, for a natural partition-related partial order $\prec^{x}$ defined on the feasible solutions for a given instance x of BIN PACKING, the problem of testing a feasible solution for $\prec^{x}$-minimality is NP-hard, but perhaps surprisingly, the problem of finding a feasible solution that is $\prec^{x}$-minimal is polynomial time solvable.

In the case of CHROMATIC NUMBER, we consider two families of partition-related partial orders defined on the set of all proper colourings of a given graph G. We investigate the problems of testing a proper colouring for minimality, and finding proper graph colourings that are minimal, with respect to these partial orders. We also consider the complexity of the associated maximinimal optimisation problems in each case. Our algorithmic results for testing and finding show where the thresholds between polynomial-time solvability and NP-hardness lie, within the hierarchy of problems corresponding to the two partial order families. These developments imply possible local search strategies for approximating the chromatic number in certain graph classes.

Finally, we revisit the general framework for minimaximal and maximinimal optimisation problems, considering an alternative definition in which the partial order is defined on the set of all possible (not necessarily feasible) solutions. We show that in some, but not all, cases, the revised definition gives rise to the same maximal and minimal solutions as would be obtained by defining the partial order concerned on the feasible solutions. These observations yield a greater insight into the structure of minimaximal and maximinimal optimisation problems.


Thesis supervisor: Dr. Rob Irving, Senior Lecturer in Computing Science.