A graph \(G = (V,E)\) is monopolar if its vertex set admits a partition \(V = (C \uplus I)\) where \(G[C]\) is a cluster graph and \(I\) is an independent set in \(G\) ; this is a monopolar partition of \(G\) . The Monopolar Recognition problem—deciding whether an input graph is monopolar—is known to be NP-hard even in very restricted graph classes. We develop fast exact exponential-time and parameterized algorithms for Monopolar Recognition. Our exact algorithm solves Monopolar Recognition in \(\mathcal {O}^{\star }(1.3734^{n})\) time on input graphs with \(n\) vertices, where the \(\mathcal {O}^{\star }()\) notation hides polynomial factors. In fact, we develop algorithms that solve the more general problems Monopolar Extension and List Monopolar Partition in the same running time. These are the first improvements over the trivial \(\mathcal {O}^{\star }(2^{n})\) -time algorithms for all these problems. These problems cannot be solved in \(\mathcal {O}^{\star }(2^{o(n)})\) time, under ETH. Our FPT algorithms solve Monopolar Recognition in \(\mathcal {O}^{\star }(3.076^{k_{v}})\)  and \(\mathcal {O}^{\star }(2.253^{k_{e}})\) time where \(k_{v}\) and \(k_{e}\) are, respectively, the sizes of the smallest vertex and edge modulators of the input graph to claw-free graphs. These results are a significant addition to the small number of FPT algorithms currently known for Monopolar Recognition.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Faster Algorithms for Graph Monopolarity

  • Geevarghese Philip,
  • Shrinidhi Teganahally Sridhara

摘要

A graph \(G = (V,E)\) is monopolar if its vertex set admits a partition \(V = (C \uplus I)\) where \(G[C]\) is a cluster graph and \(I\) is an independent set in \(G\) ; this is a monopolar partition of \(G\) . The Monopolar Recognition problem—deciding whether an input graph is monopolar—is known to be NP-hard even in very restricted graph classes. We develop fast exact exponential-time and parameterized algorithms for Monopolar Recognition. Our exact algorithm solves Monopolar Recognition in \(\mathcal {O}^{\star }(1.3734^{n})\) time on input graphs with \(n\) vertices, where the \(\mathcal {O}^{\star }()\) notation hides polynomial factors. In fact, we develop algorithms that solve the more general problems Monopolar Extension and List Monopolar Partition in the same running time. These are the first improvements over the trivial \(\mathcal {O}^{\star }(2^{n})\) -time algorithms for all these problems. These problems cannot be solved in \(\mathcal {O}^{\star }(2^{o(n)})\) time, under ETH. Our FPT algorithms solve Monopolar Recognition in \(\mathcal {O}^{\star }(3.076^{k_{v}})\)  and \(\mathcal {O}^{\star }(2.253^{k_{e}})\) time where \(k_{v}\) and \(k_{e}\) are, respectively, the sizes of the smallest vertex and edge modulators of the input graph to claw-free graphs. These results are a significant addition to the small number of FPT algorithms currently known for Monopolar Recognition.