Fixed-Parameter Complexity of Minimum Profile Problems

Abstract: Let

G = (V, E)

be a graph. An ordering of

G

is a bijection

a l p h a : V d o m 1, 2, ..., | V | .

For a vertex

v

in

G

, its closed neighborhood is

N [v] = u i n V : u v i n E c u p v .

The profile of an ordering

a l p h a

of

G

is

p r f_{a l p h a} (G) = s u m_{v i n V} (a l p h a (v) - m i n a l p h a (u) : u i n N [v]) .

The profile

p r f (G)

of

G

is the minimum of

p r f_{a l p h a} (G)

over all orderings

a l p h a

of

G

. It is well-known that

p r f (G)

is the minimum number of edges in an interval graph

H

that contains

G

is a subgraph. Since

| V | - 1

is a tight lower bound for the profile of connected graphs

G = (V, E)

, the parametrization above the guaranteed value

| V | - 1

is of particular interest. We show that deciding whether the profile of a connected graph

G = (V, E)

is at most

| V | - 1 + k

is fixed-parameter tractable with respect to the parameter

k

. We achieve this result by reduction to a problem kernel of linear size.

Recommendations

Cited in

(7)

This page was built for publication: Fixed-Parameter Complexity of Minimum Profile Problems