Clique-width is a graph parameter, defined by a composition mechanism
for vertex-labeled graphs, which measures in a certain sense the
complexity of a graph. Hard graph problems (e.g., problems
expressible in Monadic Second Order Logic, that includes NP-hard
problems) can be solved efficiently for graphs of certified small
clique-width. It is widely believed that determining the clique-width
of a graph is NP-hard; in spite of considerable efforts, no
NP-hardness proof has been found so far.

In this paper we show a non-approximability result for restricted form
of clique-width, termed r-sequential clique-width, considering only
such clique-width constructions where one of any two graphs put
together by disjoint union must have r or fewer vertices. In
particular, we show that for every positive integer r, the
r-sequential clique-width cannot be absolutely approximated in
polynomial time unless P=NP, and that given G and k the question of
whether the r-sequential clique-width of G is at most k is
NP-complete.

We show further that this non-approximability result holds even for
graphs of a very particular structure: for graphs obtained from
cobipartite graphs by replacing edges with induced paths. In part II
of this series of papers we use this strengthened result to show that,
unless P=NP, there is no polynomial-time absolute approximation
algorithm for (unrestricted) clique-width, and that, given a graph G
and an integer k, deciding whether the the clique-width G is at most k
is NP-complete. This solves a problem that has been open since the
introduction of clique-width in the early 1990s.

Clique-width is a graph parameter, defined by a composition mechanism
for vertex-labeled graphs, which measures in a certain sense the
complexity of a graph. Hard graph problems (e.g., problems
expressible in Monadic Second Order Logic, that includes NP-hard
problems) can be solved efficiently for graphs of certified small
clique-width. It is widely believed that determining the clique-width
of a graph is NP-hard; in spite of considerable efforts, no
NP-hardness proof has been found so far.

In this paper we show a non-approximability result for restricted form
of clique-width, termed r-sequential clique-width, considering only
such clique-width constructions where one of any two graphs put
together by disjoint union must have r or fewer vertices. In
particular, we show that for every positive integer r, the
r-sequential clique-width cannot be absolutely approximated in
polynomial time unless P=NP.

We show further that this non-approximability result holds even for
graphs of a very particular structure: for graphs obtained from
cobipartite graphs by replacing edges with induced paths. In part II
of this series of papers we use this strengthened result to show that,
unless P=NP, there is no polynomial-time absolute approximation
algorithm for (unrestricted) clique-width; this solves a problem that
has been open since the introduction of clique-width in the early
1990s.