On Some Combinatorial Optimization Problems : Algorithms and Complexity
Hannes Uppman · Linköping University Electronic Press eBooks · 2015
This thesis is about the computational complexity of several classes of combinatorial optimization problems, all related to the constraint satisfaction problems.A constraint language consists of a domain and a set of relations on the domain.For each such language there is a constraint satisfaction problem (CSP).In this problem we are given a set of variables and a collection of constraints, each of which is constraining some variables with a relation in the language.The goal is to determine if domain values can be assigned to the variables in a way that satisfies all constraints.An important question is for which constraint languages the corresponding CSP can be solved in polynomial time.We study this kind of question for optimization problems related to the CSPs.The main focus is on extended minimum cost homomorphism problems.These are optimization versions of CSPs where instances come with an objective function given by a weighted sum of unary cost functions, and where the goal is not only to determine if a solution exists, but to find one of minimum cost.We prove a complete classification of the complexity for these problems on three-element domains.We also obtain a classification for the so-called conservative case.Another class of combinatorial optimization problems are the surjective maximum CSPs.These problems are variants of CSPs where a non-negative weight is attached to each constraint, and the objective is to find a surjective mapping of the variables to values that maximizes the weighted sum of satisfied constraints.The surjectivity requirement causes these problems to behave quite different from for example the minimum cost homomorphism problems, and many powerful techniques are not applicable.We prove a dichotomy for the complexity of the problems in this class on two-element domains.An essential ingredient in the proof is an algorithm that solves a generalized version of the minimum cut problem.This algorithm might be of independent interest.In a final part we study properties of NP-hard optimization problems.This is done with the aid of restricted forms of polynomial-time reductions that for example preserves solvability in sub-exponential time.Two classes of This work has been supported in part by the National Graduate School in Computer Science (CUGS), Sweden. Populärvetenskaplig sammanfattningOptimering går ut på att hitta värden för ett antal variabler så att resultatet blir så bra som möjligt (enligt en given kostnadsfunktion).Vi studerar kombinatoriska optimeringsproblem, problem där man för varje variabel enbart har ett ändligt antal möjliga val.Sådana problem är i någon mening lätta; för att hitta en så bra lösning som möjligt kan man helt enkelt prova alla sätt att välja värden för variablerna.Tyvärr är det här inte någon metod som fungerar i praktiken, redan vid ett fåtal variabler kan mängden alternativ bli så stor att den omöjligen kan gås igenom.Huvuddelen av avhandlingen handlar om för vilka optimeringsproblem det finns en effektiv algoritm, och för vilka det är mycket osannolikt att en sådan algoritm existerar.En mer exakt formulering av frågan vi ställer oss är: Vilka problem har en polynomisk algoritm och vilka problem är NP-svåra?Problem för vilka det finns en polynomisk algoritm kan i någon mening ses som effektivt lösbara.NP-svåra problem tros däremot inte kunna lösas effektivt.Att visa att inget NP-svårt problem har en polynomisk algoritm (eller att det mot förmodan faktiskt finns en sån algoritm) är ett välkänt öppet problem känt som P mot NP frågan, och tros vara mycket svårt.Till exempel har Clay Mathematics Institute utlyst en belöning på en miljon dollar för en lösning.Istället för att studera enskilda problem undersöker vi stora familjer, familjer som innehåller många viktiga problem med åtskilliga teoretiska och praktiska tillämpningar och som tidigare studerats enskilt.Syftet med det här angreppssättet är att avslöja fundamentala egenskaper som antingen möjliggör eller omöjliggör effektiva algoritmer.Fokus ligger alltså inte på att hitta den snabbaste algoritmen för ett enskilt problem, utan på att hitta enkla förklaringar till varför en stor klass av problem är NP-svåra, eller egenskaper som omvänt kan utnyttjas och därigenom möjliggöra en effektiv algoritm.Främst studerar vi så kallade "minimum cost homomorphism problems" och "minimum solution problems" som båda är klasser av kombinatoriska optimeringsproblem.Vi beskriver bland annat exakt vilka sådana problem som är NP-svåra och vilka som är polynomiska när man för varje variabel har tre vi värden att välja på.En annan familj av optimeringsproblem vi studerar är "surjective maximum constraint satisfaction problems".För den här klassen ger vi en fullständig klassificering då man har två värden (till exempel "sant" och "falskt").De effektivt lösbara problemen visar sig här komma i två sorter.Välkända metoder löser problemen av den ena sorten, och för att hantera problemen av den andra konstruerar vi en egen metod som löser en generalisering av minsta-snitt problemet.Den här algoritmen kan eventuellt vara användbar också i andra sammanhang.Slutligen studerar vi egenskaper hos NP-svåra optimeringsproblem och kan bland annat för två problemklasser hitta vad som kan kallas klassens lättaste NP-svåra problem.I have received support from many, for that I am very grateful.First of all I want to thank my supervisor Peter Jonsson for his encouragement, guidance and patience, and my secondary supervisors Christer Bäckström and Ulf Nilsson for all their help.