Tìm hạt nhân để xóa mức độ d-Bound
Trong $d$ Vấn đề xóa mức độ có giới hạn, chúng tôi được cung cấp một biểu đồ vô hướng $G$ và một số nguyên dương $k$và nhiệm vụ là phải tìm ra nhiều nhất $k$ các đỉnh như vậy mà việc loại bỏ làm giảm mức đỉnh lớn nhất của đồ thị xuống nhiều nhất là $d$.
Câu hỏi đặt ra là làm thế nào để tìm một nhân đa thức (trong$k$ và $d$) cho vấn đề này.
Tôi dường như có thể nhận được quy tắc rút gọn duy nhất mà nếu bất kỳ đỉnh nào có mức độ $ > k+d$, nó phải ở đó trong tập hợp xóa (nếu câu trả lời cho ví dụ là có). Bởi vì nếu không, thì ít nhất$k+1$trong số các nước láng giềng của nó phải ở trong tập hợp xóa. Tôi dường như không thể vượt quá điểm này.
Bài tập lấy từ cuốn sách này (bài tập$2.9$).
Tôi cũng biết rằng chúng ta có thể loại bỏ các cạnh giữa các đỉnh với mức độ $< d$và tìm giải pháp trong biểu đồ đã sửa đổi (gợi ý từ cuốn sách). Nhưng tôi không chắc nó sẽ hữu ích như thế nào, trong việc nhận được giới hạn về số lượng đỉnh / cạnh trong$k$ và $d$.
Tôi sẽ chỉ đánh giá cao những gợi ý nếu có thể (một cái gì đó có thể nằm ngoài gợi ý của cuốn sách).
PS: cho $d=0$ điều này làm giảm vấn đề che đỉnh.
Trả lời
Quy tắc rút gọn 1. Hãy$V$là tập hợp các đỉnh bị cô lập. Chuyển đổi phiên bản từ$I = (G,k,d)$ đến $I^{'} = (G -V, k,d)$. Nếu$I^{'}$ là một ví dụ có, sau đó cũng vậy $I$, bởi vì việc thêm lại các đỉnh biệt lập không làm tăng thêm mức độ của các đỉnh khác. Và các đỉnh biệt lập đã có bậc 0 ($\le d$ như $d \ge 0$). Và nếu$I$ là một ví dụ có, vì vậy là $I^{'}$, như $G-V$ là một biểu đồ con của $G$, và $k$ và $d$ vẫn giữ nguyên trong hai trường hợp.
Quy tắc rút gọn 2. Nếu một đỉnh$v$ có bằng cấp $\ge k+d+1$thì nó phải được giữ trong tập hợp xóa. Nếu không thì$k+1$của hàng xóm của nó phải được giữ trong tập hợp xóa. Điều này không thể được thực hiện, vì kích thước tối đa của bộ xóa là$k$. Vì vậy, sau khi giảm này tất cả các đỉnh sẽ có độ$\le k+d$.
Quy tắc rút gọn 3 Nếu có hai đỉnh$v$ và $w$, mức độ đó của cả hai là $\le d$. Sau đó, cạnh$vw$ có thể được loại bỏ khi chuyển đổi phiên bản từ $I = (G, k,d)$ đến $I^{'} = (G-\{vw\}, k,d)$. Nếu$I$ là một ví dụ có, vì vậy là $I^{'}$ như $G-\{vw\}$ là một biểu đồ con của $G$, với $k$ và $d$vẫn giữ nguyên trên các phiên bản. Và nếu$I^{'}$ là một ví dụ có, vì vậy là $I$, như thêm lại $vw$ có thể làm cho mức độ của $v$ và $w$ nhất $d$ (như ban đầu họ có bằng cấp $\le d$).
Qui định $1$ có thể được áp dụng sau khi áp dụng Quy tắc $3$ cũng.
Bây giờ xem xét một đồ thị trong đó các đỉnh có độ $\le d$ không chia sẻ một cạnh, không có đỉnh nào bị cô lập và và tất cả các đỉnh đều có mức độ $\le k+d$(tức là không có quy tắc nào ở trên được áp dụng). Để cho$A$ là tập hợp các đỉnh có độ $\le d$ và để $B$ là tập hợp các đỉnh có độ $> d$. Chúng ta có thể tranh luận rằng$|B| \le k(k+d) +k$, nếu không thì đầu ra là không. Bởi vì nếu$|B| > k(k+d) +k$, sau đó như hầu hết $k$ các yếu tố sẽ được chọn từ $B$ cho tập hợp xóa và $ > k(k+d)$ các phần tử sẽ được để lại (trong $B$). Và vì mỗi người trong số họ có mức độ$> d$, chúng đều có ít nhất một cạnh đi vào tập hợp xóa. Nhưng tập hợp xóa chỉ có thể chứa$k(k+d)$các cạnh. Cũng như mỗi đỉnh trong$A$ có ít nhất một người hàng xóm (và tất cả họ đều ở $B$), số đỉnh tối đa trong $A$, sẽ bị ràng buộc là $|A| \le |B|(k+d) \le (k(k+d)+k)(k+d) = k(k+d)(k+d+1)$. Vì thế$|A| + |B| \le k(k+d) + k(k+d)(k+d+1) = k(k+d)(k+d+2)$.