Recognizing k-equistable graphs in FPT time

Abstract: A graph

G = (V, E)

is called equistable if there exist a positive integer

t

and a weight function

w : V o m a t h b b N

such that

S s u b s e t e q V

is a maximal stable set of

G

if and only if

w (S) = t

. Such a function

w

is called an equistable function of

G

. For a positive integer

k

, a graph

G = (V, E)

is said to be

k

-equistable if it admits an equistable function which is bounded by

k

. We prove that the problem of recognizing

k

-equistable graphs is fixed parameter tractable when parameterized by

k

, affirmatively answering a question of Levit et al. In fact, the problem admits an

O (k^{5})

-vertex kernel that can be computed in linear time.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Recognizing \(k\)-equistable graphs in FPT time