On the Equivalence among Problems of Bounded Width

In this paper, we introduce a methodology, called decomposition-based reductions, for showing the equivalence among various problems of bounded-width.

First, we show that the following are equivalent for any

α

 > 0:

SAT

can be solved in

$O^*(2^{\alpha{\bf tw} })$

time,

3-SAT

can be solved in

$O^*(2^{\alpha{\bf tw} })$

time,

Max 2-SAT

can be solved in

$O^*(2^{\alpha{\bf tw} })$

time,

Independent Set

can be solved in

$O^*(2^{\alpha{\bf tw} })$

time, and

Independent Set

can be solved in

$O^*(2^{\alpha{\bf cw} })$

time,

where

${\bf tw} $

and

${\bf cw} $

are the tree-width and clique-width of the instance, respectively. Then, we introduce a new parameterized complexity class

${\mbox{\textup{EPNL}}} $

, which includes

Set Cover

and

TSP

, and show that

SAT

,

3-SAT

,

Max 2-SAT

, and

Independent Set

parameterized by path-width are

${\mbox{\textup{EPNL}}} $

-complete. This implies that if one of these

${\mbox{\textup{EPNL}}} $

-complete problems can be solved in

O

*

(

c

k

) time, then any problem in

${\mbox{\textup{EPNL}}} $

can be solved in

O

*

(

c

k

) time.