Abstract

Many classic graph problems – such as Isomorphism, Max Cut, Chromatic Number, Edge Dominating Set and Hamiltonian Cycle – are known to be polynomial-time solvable on cographs, fixed-parameter tractable (FPT) when parameterized by treewidth, yet W[1]-hard when parameterized by clique-width. This reveals a sharp tractability gap between treewidth and clique-width. In this work, we propose a new structural graph parameter, $\mathcal{C}$-modular-treewidth, which lies between treewidth and clique-width. The parameter leverages modular decomposition and restricts modules to induce graphs from a fixed class $\mathcal{C}$ (e.g., cographs or edgeless graphs). By exploiting true and false twins – a hallmark of cograph-like structure – our parameter allows the design of efficient algorithms for several hard problems beyond the reach of treewidth-based methods. In this work, we show that $\mathcal{C}$-modular-treewidth enables efficient solutions under suitable choices of $\mathcal{C}$, opening a new pathway in the parameterized complexity landscape between treewidth and clique-width. In particular we show that

  • When parameterized by cograph-modular-treewidth, Isomorphism admits an FPT algorithm, whereas Chromatic Number remains W[1]-hard.
  • When parameterized by independent-modular-treewidth, Max Cut and Chromatic Number admit FPT algorithms, whereas Hamiltonian Cycle and Edge Dominating Set remain W[1]-hard.