ECCC-Report TR05-080https://eccc.weizmann.ac.il/report/2005/080Comments and Revisions published for TR05-080en-usWed, 24 Aug 2005 00:00:00 +0300
Revision 1
| Proving NP-hardness for clique-width I: non-approximability of sequential clique-width |
Michael R. Fellows,
Frances A. Rosamond,
Udi Rotics,
Stefan Szeider
https://eccc.weizmann.ac.il/report/2005/080#revision1Clique-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.
Wed, 24 Aug 2005 00:00:00 +0300https://eccc.weizmann.ac.il/report/2005/080#revision1
Paper TR05-080
| Proving NP-hardness for clique-width I: non-approximability of sequential clique-width |
Michael R. Fellows,
Frances A. Rosamond,
Udi Rotics,
Stefan Szeider
https://eccc.weizmann.ac.il/report/2005/080Clique-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.
Wed, 27 Jul 2005 16:27:14 +0300https://eccc.weizmann.ac.il/report/2005/080