Approximating Upper Degree-Constrained Partial Orientations

Abstract

In the Upper Degree-Constrained Partial Orientation (UDPO) problem we are given an undirected graph G=(V,E), together with two degree constraint functions d^-,d^+:V -> N. The goal is to orient as many edges as possible, in such a way that for each vertex v in V the number of arcs entering v is at most d^-(v), whereas the number of arcs leaving v is at most d^+(v). This problem was introduced by Gabow [SODA'06], who proved it to be MAXSNP-hard (and thus APX-hard). In the same paper Gabow presented an LP-based iterative rounding 4/3-approximation algorithm.

As already observed by Gabow, the problem in question is a special case of the classic 3-Dimensional Matching, which in turn is a special case of the k-Set Packing problem. Back in 2006 the best known polynomial time approximation algorithm for 3-Dimensional Matching was a simple local search by Hurkens and Schrijver [SIDMA'89], the approximation ratio of which is (3+epsilon)/2; hence the algorithm of Gabow was an improvement over the approach brought from the more general problems.

In this paper we show that the UDPO problem when cast as 3-Dimensional Matching admits a special structure, which is obliviously exploited by the known approximation algorithms for k-Set Packing. In fact, we show that already the local-search routine of Hurkens and Schrijver gives (4+epsilon)/3-approximation when used for the instances coming from UDPO. Moreover, the recent approximation algorithm for 3-Set Packing [Cygan, FOCS'13] turns out to be a (5+epsilon)/4-approximation for UDPO. This improves over 4/3 as the best ratio known up to date for UDPO.