سوال ۳

اعداد \(1400\) و \(2021\) را ثابت در نظر بگیرید. هر عددی که فقط تابعی از این دو مقدار باشد، از نظر زمان اجرای چندجمله‌ای یک ثابت حساب می‌شود، حتی اگر بسیار بزرگ باشد.

شرط مهم مسئله این است که اگر \(uv \in E(G)\)، آنگاه طول مسیر بین \(u\) و \(v\) در درخت \(T\) حداکثر \(2021\) است: \[ \operatorname{dist}_T(u,v) \le 2021. \] پس یال‌های \(G\) نسبت به درخت \(T\) محلی هستند.

برای هر رأس \(x\) از درخت \(T\)، مجموعه‌ی زیر را تعریف کنید: \[ B_x =\{v\in V(G)\mid \operatorname{dist}_T(x,v)\le 2021\}. \] به این مجموعه یک bag می‌گوییم. فعلاً فقط آن را مثل یک پنجره‌ی شعاع \(2021\) دور \(x\) در درخت \(T\) ببینید.

اندازه‌ی هر bag مستقل از \(n\) است. چون درجه‌ی هر رأس در \(T\) حداکثر \(1400\) است، داریم: $$ \vert B_x\vert \le 1+1400+1400 \cdot 1399+ \cdots +1400 \cdot 1399^{2020}. $$ این عدد را \(K\) بنامید. مهم فقط این است که \(K\) ثابت است.

اکنون «درخت bagها» را تعریف می‌کنیم. ساختار درختی همان \(T\) است، اما روی هر رأس \(x\) از \(T\)، مجموعه‌ی \(B_x\) را می‌نویسیم. اگر \(xy\in E(T)\)، آنگاه bagهای \(B_x\) و \(B_y\) نیز در این درخت مجاورند.

نشان دهید هر یال \(uv\in E(G)\) داخل حداقل یکی از bagها کامل دیده می‌شود.

برای یک رأس ثابت \(v\)، به همه‌ی bagهایی نگاه کنید که \(v\) را دارند. این‌ها دقیقاً رأس‌های \(x\)ای هستند که \[ \operatorname{dist}_T(x,v)\le 2021. \] این مجموعه در درخت \(T\) متصل است. این یعنی حضور هر رأس در bagها به صورت یک بازه‌ی متصل روی درخت است.

سعی کنید بر درخت تازه تعریف شده DP بزنید

یک رأس دلخواه \(r\) انتخاب کنید و آن را به همه‌ی bagها اضافه کنید: \[ C_x=B_x\cup\{r\}. \] اندازه‌ی bagها هنوز ثابت است. این کار در انتهای DP کمک می‌کند که همه‌ی رأس‌ها را نسبت به یک رأس ثابت \(r\) کنترل کنیم.

درخت bagها را ریشه‌دار کنید و از پایین به بالا روی آن DP بزنید. می‌توان فرض کرد بین دو bag مجاور، چند راس میانی اضافه شده‌اند تا در هر مرحله فقط یک رأس به bag اضافه شود یا فقط یک رأس از bag حذف شود.

اگر دو bag مجاور \(A\) و \(B\) باشند، بین آن‌ها زنجیری بگذارید که ابتدا رأس‌های \(B\setminus A\) را یکی‌یکی اضافه کند و سپس رأس‌های \(A\setminus B\) را یکی‌یکی حذف کند. اندازه‌ی bagها شاید تا چند برابر \(K\) بزرگ شود، ولی همچنان ثابت می‌ماند.

هر یال \(uv\in E(G)\) را دقیقاً به یکی از bagهایی نسبت دهید که هر دو سر یال را دارند. مثلاً می‌توانید طبق یک قرارداد ثابت، یال \(uv\) را به bag مربوط به یکی از دو سرش نسبت دهید. مهم این است که هر یال دقیقاً یک بار پردازش شود.

شرط «همبند و فاقد یال برشی» را به یک شرط جهت‌دار تبدیل کنید. از گزاره‌ی زیر استفاده کنید:

یک گراف بدون‌جهت همبند و بدون برشی است اگر و فقط اگر بتوان یال‌هایش را طوری جهت‌دار کرد که گراف جهت‌دار حاصل قویا همبند شود.

یک طرف گزاره‌ی قبل ساده است. اگر جهت‌دهی قویا همبند داشته باشیم، هیچ یالی نمی‌تواند برشی باشد؛ چون اگر یک یال برشی دو طرف گراف را جدا کند، جهت آن یال هرچه باشد، در جهت مخالف دیگر راهی بین دو طرف وجود ندارد.

برای طرف دیگر، روی گراف بدون یال برشی یک DFS بزنید. یال‌های درخت DFS را از پدر به فرزند جهت بدهید و یال‌های غیردرختی را از نواده به جد. حالا بررسی کنید چرا ریشه به همه می‌رسد و چرا همه می‌توانند به ریشه برگردند.

پس مسئله معادل این می‌شود: کمترین تعداد یال را انتخاب کنیم و به هر یال انتخاب‌شده یکی از دو جهت را بدهیم، به طوری که گراف جهت‌دار حاصل قویا همبند شود. در پایان جهت‌ها را فراموش می‌کنیم.

در یک راس DP، فرض کنید bag فعلی \(X\) باشد. چون \(|X|\) ثابت است، می‌توانیم رابطه‌ی دسترسی جهت‌دار بین رأس‌های داخل \(X\) را به عنوان حالت نگه داریم.

یک حالت DP یک رابطه‌ی دودویی است: \[ R\subseteq X\times X. \] معنای \((a,b)\in R\) این است که در بخش پردازش‌شده، از \(a\) به \(b\) یک مسیر جهت‌دار وجود دارد.

رابطه‌ی \(R\) را همیشه از لحاظ ترایایی بسته نگه دارید. یعنی اگر \[ (a,b)\in R \qquad\text{و}\qquad (b,c)\in R, \] آنگاه باید \[ (a,c)\in R \] هم برقرار باشد.

مقدار DP را این‌طور تعریف کنید: \[ dp[t,R]= \] کمترین تعداد یال انتخاب‌شده در بخش زیرین راس\(t\)، به طوری که رابطه‌ی دسترسی روی bag فعلی دقیقاً \(R\) باشد.

هنگام اضافه شدن یک رأس \(v\) به bag، فقط رابطه‌ی \[ (v,v) \] را اضافه کنید. صرف ورود یک رأس به bag، مسیر جدیدی به رأس‌های دیگر ایجاد نمی‌کند.

هنگام پردازش یک یال \(uv\)، سه انتخاب دارید: \[ \times, \qquad u\to v, \qquad v\to u. \] اگر یال را انتخاب کنیم، هزینه \(1\) زیاد می‌شود. اگر مثلاً \(u\to v\) را انتخاب کنیم، رابطه‌ی جدید برابر است با \[ R'=\operatorname{TC}(R\cup\{(u,v)\}), \] که \(\operatorname{TC}\) یعنی بستار ترایایی.

هنگام حذف یک رأس \(v\) از bag، بعداً دیگر نمی‌توانیم اطلاعات تازه‌ای درباره‌ی \(v\) بسازیم. پس باید همین حالا مطمئن شویم که \(v\) به مرز باقی‌مانده وصل است. اگر bag فعلی \(X\) باشد، باید دو رأس، شاید متفاوت، وجود داشته باشند: \[ a,b\in X\setminus\{v\} \] به طوری که \[ (v,a)\in R \qquad\text{و}\qquad (b,v)\in R. \] اگر چنین \(a,b\)ای وجود نداشت، این حالت مردود است.

اگر دو زیرمسئله با bag یکسان \(X\) ترکیب شوند و رابطه‌های آن‌ها \(R_1\) و \(R_2\) باشد، رابطه‌ی پدر برابر است با \[ R=\operatorname{TC}(R_1\cup R_2). \] هزینه‌ها نیز جمع می‌شوند: \[ dp[t,R]=dp[t_1,R_1]+dp[t_2,R_2]. \] به دلیل مالکیت یکتای یال‌ها، هیچ یالی دوبار شمرده یا با دو جهت ناسازگار انتخاب نمی‌شود.

در انتهای DP کاری کنید که bag ریشه فقط شامل \(r\) باشد. جواب مقدار \[ dp[\text{root},\{(r,r)\}] \] است. با نگه داشتن اشاره‌گرهای بازسازی، خود یال‌های انتخاب‌شده نیز به دست می‌آیند.

درستی DP از دو جهت بررسی می‌شود. از یک طرف، هر انتقال واقعاً متناظر با انتخاب تعدادی یال جهت‌دار است، و در پایان هر رأس \(v\) هم از \(r\) قابل دسترسی است و هم به \(r\) می‌رسد؛ پس گراف قویا همبند است.

از طرف دیگر، یک جواب بهینه را بردارید و آن را جهت‌دهی قویا همبند کنید. اگر DP دقیقاً همان انتخاب‌های یال‌ها را دنبال کند، هنگام حذف هر رأس \(v\) گیر نمی‌کند؛ چون مسیرهای \(v\leadsto r\) و \(r\leadsto v\) باید از مرز باقی‌مانده عبور کنند. این همان شرط وجود \(a,b\) در مرحله‌ی حذف است.

تعداد حالت‌ها برای یک bag حداکثر \[ 2^{K^2} \] است، چون حالت یک رابطه روی حداکثر \(K\) رأس است. این عدد ثابت است. تعداد گره‌های DP و یال‌های پردازش‌شده چندجمله‌ای است، پس زمان کل از شکل \[ f(K)\cdot (n+m)^{O(1)} \] است. چون \(K\) ثابت است، الگوریتم چندجمله‌ای است.