On the Approximability of Digraph Ordering

Given an

n

-vertex digraph

D

 = (

V

,

A

) the

Max-

k

-Ordering

problem is to compute a labeling ℓ:

V

 → [

k

] maximizing the number of forward edges, i.e. edges (

u

,

v

) such that ℓ(

u

) < ℓ(

v

). For different values of

k

, this reduces to

Maximum Acyclic Subgraph

(

k

 = 

n

), and

Max-DiCut

(

k

 = 2). This work studies the approximability of

Max-

k

-Ordering

and its generalizations, motivated by their applications to job scheduling with

soft

precedence constraints. We give an LP rounding based 2-approximation algorithm for

Max-

k

-Ordering

for any

k

 = {2,…,

n

}, improving on the known

$\left.2k\middle/(k-1)\right.$

-approximation obtained via random assignment. The tightness of this rounding is shown by proving that for any

k

 = {2,…,

n

} and constant

ε

 > 0,

Max-

k

-Ordering

has an LP integrality gap of 2 − 

ε

for

$n^{\Omega\left(\left.1\middle/\log\log k\right.\right)}$

rounds of the Sherali-Adams hierarchy.

A further generalization of

Max-

k

-Ordering

is the

restricted maximum acyclic subgraph

problem or

RMAS

, where each vertex

v

has a finite set of allowable labels

S

v

 ⊆ ℤ

 + 

. We prove an LP rounding based

$\left.4\sqrt{2}\middle/\left(\sqrt{2}+1\right)\right. \approx 2.344$

approximation for it, improving on the

$2\sqrt{2} \approx 2.828$

approximation recently given by Grandoni et al. [5]. In fact, our approximation algorithm also works for a general version where the objective counts the edges which go forward by at least a positive

offset

specific to each edge.

The minimization formulation of digraph ordering is

DAG edge deletion

or

DED

(

k

), which requires deleting the minimum number of edges from an

n

-vertex directed acyclic graph (DAG) to remove all paths of length

k

. We show that both, the LP relaxation and a local ratio approach for

DED

(

k

) yield

k

-approximation for any

k

 ∈ [

n

]. A vertex deletion version was studied earlier by Paik et al. [16], and Svensson [17].