论文标题
图形分配到连接的簇中的参数化复杂性
Parameterized Complexity of Graph Partitioning into Connected Clusters
论文作者
论文摘要
Given an undirected graph $G$ and $q$ integers $n_1,n_2,n_3, \cdots, n_q$, balanced connected $q$-partition problem ($BCP_q$) asks whether there exists a partition of the vertex set $V$ of $G$ into $q$ parts $V_1,V_2,V_3,\cdots, V_q$ such that for all $ i \ in [1，q] $，$ | v_i | = n_i $，并且在$ v_i $上诱导的图已连接。相关的问题表示为平衡的连接$ q $ - 边缘分区问题（$ bcep_q $）的定义如下。给定无向图$ g $和$ q $ integers $ n_1，n_2，n_3，\ cdots，n_q $，$ bcep_q $询问是否存在$ g $ g $ g $ q $ q $ q $ parts $ e_1，e_2，e_2，e_3，e_3，e_3，e_q $的$ g $ parts $ e_2，e_q $的$ i__ $ i y y y y |在边缘集合$ e_i $上诱导的图是连接的。在这里，我们研究了$ q = 2 $的问题，并证明$ bcp_q $ for $ q \ geq 2 $ is $ w [1] $ - 硬。我们还表明，$ bcp_2 $不太可能在平面图上具有多项式内核。取得积极的结果，我们表明$ bcp_2 $是固定参数可通过图形的参数（fpt），该参数通过图的widterth进行了参数，该参数概括为平面图的fpt算法。我们设计了另一种FPT算法和一个由$ \ min（N_1，N_2）$参数化的单元磁盘图的类别内核。最后，我们证明，与$ bcp_2 $不同，$ bcep_2 $是由$ \ min（n_1，n_2）$进行参数化的。
Given an undirected graph $G$ and $q$ integers $n_1,n_2,n_3, \cdots, n_q$, balanced connected $q$-partition problem ($BCP_q$) asks whether there exists a partition of the vertex set $V$ of $G$ into $q$ parts $V_1,V_2,V_3,\cdots, V_q$ such that for all $i\in[1,q]$, $|V_i|=n_i$ and the graph induced on $V_i$ is connected. A related problem denoted as the balanced connected $q$-edge partition problem ($BCEP_q$) is defined as follows. Given an undirected graph $G$ and $q$ integers $n_1,n_2,n_3, \cdots, n_q$, $BCEP_q$ asks whether there exists a partition of the edge set of $G$ into $q$ parts $E_1,E_2,E_3,\cdots, E_q$ such that for all $i\in[1,q]$, $|E_i|=n_i$ and the graph induced on the edge set $E_i$ is connected. Here we study both the problems for $q=2$ and prove that $BCP_q$ for $q\geq 2$ is $W[1]$-hard. We also show that $BCP_2$ is unlikely to have a polynomial kernel on the class of planar graphs. Coming to the positive results, we show that $BCP_2$ is fixed parameter tractable (FPT) parameterized by treewidth of the graph, which generalizes to FPT algorithm for planar graphs. We design another FPT algorithm and a polynomial kernel on the class of unit disk graphs parameterized by $\min(n_1,n_2)$. Finally, we prove that unlike $BCP_2$, $BCEP_2$ is FPT parameterized by $\min(n_1,n_2)$.
