Partial Degree Bounded Edge Packing Problem

In [1], whether a target binary string

s

can be represented from a boolean formula with operands chosen from a set of binary strings

W

was studied. In this paper, we first examine selecting a maximum subset

X

from

W

, so that for any string

t

in

X

,

t

is not representable by

X

 ∖ {

t

}. We rephrase this problem as graph, and surprisingly find it give rise to a broad model of edge packing problem, which itself falls into the model of forbidden subgraph problem. Specifically, given a graph

G

(

V

,

E

) and a constant

c

, the problem asks to choose as many as edges to form a subgraph

G

′. So that in

G

′, for each edge, at least one of its endpoints has degree no more than

c

. We call such

G

′ partial

c

degree bounded. This edge packing problem model also has a direct interpretation in resource allocation. There are

n

types of resources and

m

jobs. Each job needs two types of resources. A job can be accomplished if either one of its necessary resources is shared by no more than

c

other jobs. The problem then asks to finish as many jobs as possible. For edge packing problem, when

c

 = 1, it turns out to be the complement of dominating set and able to be 2-approximated. When

c

 = 2, it can be 32/11-approximated. We also prove it is

NP

-complete for any constant

c

on graphs and is

O

(|

V

|

2

) solvable on trees. We believe this partial bounded graph problem is intrinsic and merits more attention.