Maximum independent sets near the upper bound

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: The size of a largest independent set of vertices in a given graph

G

is denoted by

a l p h a (G)

and is called its independence number (or stability number). Given a graph

G

and an integer

K,

it is NP-complete to decide whether

a l p h a (G) g e q K .

An upper bound for the independence number

a l p h a (G)

of a given graph

G

with

n

vertices and

m

edges is given by

a l p h a (G) l e q p := l f l o o r f r a c 12 + s q r t f r a c 14 + n^{2} - n - 2 m f l o o r .

In this paper we will consider maximum independent sets near this upper bound. Our main result is the following: There exists an algorithm with time complexity

O (n^{2})

that, given as an input a graph

G

with

n

vertices,

m

edges,

p := l f l o o r f r a c 12 + s q r t f r a c 14 + n^{2} - n - 2 m f l o o r,

and an integer

k g e q 0

with

p g e q 2 k + 1,

returns an induced subgraph

G_{p, k}

of

G

with

n_{0} l e q p + 2 k + 1

vertices such that

a l p h a (G) l e q p - k

if and only if

a l p h a (G_{p, k}) l e q p - k .

Furthermore, we will show that we can decide in time

O (1.273 8^{3 k} + k n)

whether

a l p h a (G_{p, k}) l e q p - k .

Review text

An independent set of a graph \(G\) is a set of vertices where no two vertices are adjacent. The independence number is the size of a maximum independent set in the graph and is denoted by \(\alpha(G)\). Let us recall the following upper bound for \(\alpha(G)\): Theorem. Let \(G\) be a graph of order \(n\) and size \(m\). Then \[\alpha(G)\leq p:=\lfloor \frac{1}{2}+\sqrt{\frac{1}{4}+n^2-n-2m}\rfloor.\] The author considers independent sets near the above upper bound and proved the following result: Theorem. There exists an algorithm with time complexity \(O(n^2)\) that, given as an input a graph \(G\) of order \(n\), size \(m\), \(p:=\lfloor \frac{1}{2}+\sqrt{\frac{1}{4}+n^2-n-2m}\rfloor\) and an integer \(k\geq 0\) with \(p\geq2k+1\), returns an induced subgraph \(G_{p,k}\) of \(G\) with \(n_0\leq p+2k+1\) vertices such that \(\alpha(G) \leq p-k\) if and only if \(\alpha(G_{p,k})\leq p-k.\) Furthermore, he shows that one can decide in \(O(1.2738^{3k}+n^2)\) time whether \(\alpha(G_{p,k})\leq p-k\).

Recommendations

Cites work

Cited in

(12)

This page was built for publication: Maximum independent sets near the upper bound

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2026337)