2025-11-11T21:37:18.898302

Graph modification of bounded size to minor-closed classes as fast as vertex deletion

Morelle, Sau, Thilikos

A replacement action is a function $\mathcal{L}$ that maps each graph $H$ to a collection of graphs of size at most $|V(H)|$. Given a graph class $\mathcal{H}$, we consider a general family of graph modification problems, called $\mathcal{L}$-Replacement to $\mathcal{H}$, where the input is a graph $G$ and the question is whether it is possible to replace some induced subgraph $H_1$ of $G$ on at most $k$ vertices by a graph $H_2$ in $\mathcal{L}(H_1)$ so that the resulting graph belongs to $\mathcal{H}$. $\mathcal{L}$-Replacement to $\mathcal{H}$ can simulate many graph modification problems including vertex deletion, edge deletion/addition/edition/contraction, vertex identification, subgraph complementation, independent set deletion, (induced) matching deletion/contraction, etc. We present two algorithms. The first one solves $\mathcal{L}$-Replacement to $\mathcal{H}$ in time $2^{{\rm poly}(k)}\cdot |V(G)|^2$ for every minor-closed graph class $\mathcal{H}$, where {\rm poly} is a polynomial whose degree depends on $\mathcal{H}$, under a mild technical condition on $\mathcal{L}$. This generalizes the results of Morelle, Sau, Stamoulis, and Thilikos [ICALP 2020, ICALP 2023] for the particular case of Vertex Deletion to $\mathcal{H}$ within the same running time. Our second algorithm is an improvement of the first one when $\mathcal{H}$ is the class of graphs embeddable in a surface of Euler genus at most $g$ and runs in time $2^{\mathcal{O}(k^{9})}\cdot |V(G)|^2$, where the $\mathcal{O}(\cdot)$ notation depends on $g$. To the best of our knowledge, these are the first parameterized algorithms with a reasonable parametric dependence for such a general family of graph modification problems to minor-closed classes.

academic

সীমাবদ্ধ আকারের গ্রাফ সংশোধন থেকে মাইনর-বদ্ধ শ্রেণী পর্যন্ত শীর্ষবিন্দু মুছে ফেলার মতো দ্রুত

মৌলিক তথ্য

পেপার আইডি: 2504.16803
শিরোনাম: Graph modification of bounded size to minor-closed classes as fast as vertex deletion
লেখক: Laure Morelle, Ignasi Sau, Dimitrios M. Thilikos
শ্রেণীবিভাগ: cs.DS (ডেটা স্ট্রাকচার এবং অ্যালগরিদম)
প্রকাশনার সময়/সম্মেলন: ২০২৫ ইউরোপীয় অ্যালগরিদম বার্ষিক সম্মেলন (ESA 2025)
পেপার লিঙ্ক: https://arxiv.org/abs/2504.16803

সারসংক্ষেপ

এই পেপারটি সাধারণীকৃত গ্রাফ সংশোধন সমস্যা অধ্যয়ন করে, যাকে $\mathcal{L}$ -প্রতিস্থাপন থেকে $\mathcal{H}$ সমস্যা বলা হয়। একটি প্রতিস্থাপন ক্রিয়া ফাংশন $\mathcal{L}$ এবং লক্ষ্য গ্রাফ শ্রেণী $\mathcal{H}$ দেওয়া হলে, সমস্যাটি হল নির্ধারণ করা যে ইনপুট গ্রাফ $G$ এর একটি প্রেরিত উপগ্রাফ $H_1$ (যাতে সর্বাধিক $k$ টি শীর্ষবিন্দু রয়েছে) কে $\mathcal{L}(H_1)$ থেকে একটি গ্রাফ $H_2$ দিয়ে প্রতিস্থাপন করা যায় কিনা যাতে ফলাফল গ্রাফটি $\mathcal{H}$ এ থাকে। এই কাঠামোটি বিভিন্ন গ্রাফ সংশোধন সমস্যা অনুকরণ করতে পারে, যার মধ্যে রয়েছে শীর্ষবিন্দু মুছে ফেলা, প্রান্ত মুছে ফেলা/যোগ করা/সম্পাদনা করা/সংকুচিত করা, শীর্ষবিন্দু একীভূত করা, উপগ্রাফ পরিপূরক ইত্যাদি। পেপারটি দুটি অ্যালগরিদম উপস্থাপন করে: প্রথম অ্যালগরিদম $2^{\text{poly}(k)} \cdot |V(G)|^2$ সময়ে যেকোনো মাইনর-বদ্ধ গ্রাফ শ্রেণী $\mathcal{H}$ এর জন্য সমস্যাটি সমাধান করে; দ্বিতীয় অ্যালগরিদম অয়লার অপচয় সর্বাধিক $g$ এর সারফেসে এম্বেড করা যায় এমন গ্রাফ শ্রেণীর জন্য, চলমান সময় $2^{\mathcal{O}(k^9)} \cdot |V(G)|^2$ এ উন্নত হয়।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যার গুরুত্ব

গ্রাফ সংশোধন সমস্যাগুলি অ্যালগরিদমিক গ্রাফ তত্ত্বে মৌলিক অবস্থান রাখে এবং গণনামূলক জীববিজ্ঞান, কম্পিউটার দৃষ্টিভঙ্গি, মেশিন লার্নিং, নেটওয়ার্ক বিশ্লেষণ, সমাজবিজ্ঞান এবং অন্যান্য অনেক ক্ষেত্রে ব্যাপক প্রয়োগ রয়েছে। এই ধরনের সমস্যাগুলি সাধারণত জিজ্ঞাসা করে যে ইনপুট গ্রাফকে লক্ষ্য গ্রাফ শ্রেণীতে একটি গ্রাফে রূপান্তরিত করা যায় কিনা সীমিত সংশোধন ক্রিয়াকলাপের মাধ্যমে।

বিদ্যমান পদ্ধতির সীমাবদ্ধতা

সর্বজনীনতার অভাব: বিদ্যমান গবেষণা প্রধানত নির্দিষ্ট সংশোধন ক্রিয়াকলাপের উপর দৃষ্টি নিবদ্ধ করে (যেমন শীর্ষবিন্দু মুছে ফেলা), একটি একীভূত তাত্ত্বিক কাঠামোর অভাব রয়েছে
প্যারামিটার নির্ভরতা বিশাল: যদিও কিছু অ্যালগরিদম মেটাথিওরেম বিদ্যমান রয়েছে (যেমন কোরসেলের উপপাদ্যের সম্প্রসারণ), প্যারামিটার নির্ভরতা অত্যন্ত বিশাল, এমনকি একটি মোটামুটি উপরের সীমাও দেওয়া যায় না
প্রযোজ্য পরিসীমা সীমিত: মাইনর-বদ্ধ লক্ষ্য গ্রাফ শ্রেণীর জন্য, শুধুমাত্র শীর্ষবিন্দু মুছে ফেলার সমস্যা ভালভাবে অধ্যয়ন করা হয়েছে, অন্যান্য সংশোধন ক্রিয়াকলাপের গবেষণা অত্যন্ত সীমিত

গবেষণা প্রেরণা

এই পেপারের মূল প্রেরণা হল যুক্তিসঙ্গত প্যারামিটার নির্ভরতা বজায় রেখে যতটা সম্ভব বিস্তৃত গ্রাফ সংশোধন সমস্যার জন্য একটি একীভূত অ্যালগরিদমিক কাঠামো প্রদান করা। লেখকরা দুটি গবেষণা দিকের মধ্যে ব্যবধান পূরণ করতে চান: একটি হল বিশাল প্যারামিটার নির্ভরতা সহ সাধারণ মেটাথিওরেম, দ্বিতীয়টি নির্দিষ্ট সমস্যার জন্য দক্ষ অ্যালগরিদম।

মূল অবদান

একীভূত কাঠামো: $\mathcal{L}$ -প্রতিস্থাপন থেকে $\mathcal{H}$ এর একটি একীভূত কাঠামো প্রস্তাব করে, যা বিভিন্ন গুরুত্বপূর্ণ গ্রাফ সংশোধন সমস্যা অনুকরণ করতে পারে
সাধারণ অ্যালগরিদম: যেকোনো মাইনর-বদ্ধ গ্রাফ শ্রেণী $\mathcal{H}$ এর জন্য, $2^{\text{poly}(k)} \cdot n^2$ চলমান সময় সহ একটি অ্যালগরিদম প্রদান করে, যা বর্তমান সেরা শীর্ষবিন্দু মুছে ফেলার অ্যালগরিদমের সাথে একই সময় জটিলতা রয়েছে
সীমাবদ্ধ অপচয় অপ্টিমাইজেশন: বদ্ধ অয়লার অপচয় সারফেসে এম্বেড করা যায় এমন গ্রাফ শ্রেণীর জন্য, চলমান সময় $2^{\mathcal{O}(k^9)} \cdot n^2$ এ উন্নত করে
প্রযুক্তিগত উদ্ভাবন: অপ্রাসঙ্গিক শীর্ষবিন্দু প্রযুক্তি প্রসারিত করে, নতুন সমজাতীয়তার সংজ্ঞা প্রস্তাব করে এবং বিশেষায়িত গতিশীল প্রোগ্রামিং অ্যালগরিদম ডিজাইন করে

পদ্ধতি বিস্তারিত

কাজের সংজ্ঞা

প্রতিস্থাপন ক্রিয়া (Replacement Action): ফাংশন $\mathcal{L}$ প্রতিটি অর্ডারকৃত গ্রাফ $H_1$ কে একটি সেটে ম্যাপ করে $\mathcal{L}(H_1)$ , যাতে বেশ কয়েকটি জোড়া $(H_2, \phi)$ রয়েছে, $H_2$ হল একটি গ্রাফ যার শীর্ষবিন্দু সংখ্যা $|V(H_1)|$ অতিক্রম করে না, $\phi: V(H_1) \to V(H_2) \cup \{\emptyset\}$ হল একটি ম্যাপিং ফাংশন।

$\mathcal{L}$ -প্রতিস্থাপন থেকে $\mathcal{H}$ সমস্যা:

ইনপুট: গ্রাফ $G$ এবং পূর্ণসংখ্যা $k$
সমস্যা: $G$ এর একটি শীর্ষবিন্দু সেট $S$ (সর্বাধিক $k$ টি শীর্ষবিন্দু সহ) বিদ্যমান রয়েছে কিনা যাতে $\mathcal{L}^S(G) \cap \mathcal{H} \neq \emptyset$

উত্তরাধিকার শর্ত: প্রতিস্থাপন ক্রিয়া $\mathcal{L}$ উত্তরাধিকারী হওয়ার প্রয়োজন, অর্থাৎ যদি $(H_2, \phi) \in \mathcal{L}(H_1)$ , তাহলে $H_1$ এর যেকোনো প্রেরিত উপগ্রাফ $H_1'$ এর জন্য, সংশ্লিষ্ট সীমাবদ্ধতাও $\mathcal{L}(H_1')$ এ রয়েছে।

অ্যালগরিদম আর্কিটেকচার

তিনটি মূল উপাদান

1. সীমাবদ্ধ ট্রি-প্রস্থের গতিশীল প্রোগ্রামিং অ্যালগরিদম

Nice ট্রি বিয়োজন ব্যবহার করে, প্রতিটি নোডে আংশিক সমাধান অনুমান করে
প্রতিনিধিত্ব-ভিত্তিক প্রযুক্তি ব্যবহার করে অবস্থা স্থান আকার নিয়ন্ত্রণ করে
চলমান সময়: $2^{\mathcal{O}(k^2+(k+tw)\log(k+tw))} \cdot n$

2. অপ্রাসঙ্গিক শীর্ষবিন্দু প্রযুক্তি

বড় সমজাতীয় সমতল দেয়ালে অপ্রাসঙ্গিক শীর্ষবিন্দু খুঁজে পায়
সাধারণ সংশোধন ক্রিয়াকলাপ পরিচালনা করার জন্য বিদ্যমান সমজাতীয়তার সংজ্ঞা প্রসারিত করে
মূল ফাংশন: $f_6(k,a) = \mathcal{O}_{a,\ell_F}(k^c)$ , যেখানে $c$ $a$ এবং বাধা গ্রাফের আকারের উপর নির্ভর করে

3. শাখা কৌশল

যখন গ্রাফে বড় দেয়াল এবং পর্যাপ্ত অনেক পথ সহ শীর্ষবিন্দু সেট থাকে, তখন "বাধ্যতামূলক" শীর্ষবিন্দু খুঁজে পায়
প্রমাণ করে যে যেকোনো সমাধান অবশ্যই সেই সেটে কোনো শীর্ষবিন্দু অন্তর্ভুক্ত করে
Lemma 4.1 ব্যবহার করে শাখার কার্যকারিতা নিশ্চিত করে

অ্যালগরিদম প্রবাহ

Algorithm Main(G, S', H'_2, φ', k):
1. মৌলিক পরীক্ষা: যদি |S'| > k, no-instance ফেরত দিন
2. দেয়াল খুঁজুন: Find-Wall অ্যালগরিদম ব্যবহার করুন
   - যদি ট্রি-প্রস্থ ছোট হয়, গতিশীল প্রোগ্রামিং ব্যবহার করুন
   - অন্যথায় r_1-দেয়াল W_1 খুঁজে পান
3. সমতল দেয়াল খুঁজুন:
   - প্রতিটি r_2-উপদেয়ালের জন্য, Grasped-or-Flat প্রয়োগ করুন
   - যদি flatness জোড়া পাওয়া যায়, ধাপ 4 এ যান
   - অন্যথায় ধাপ 5 এ যান
4. অপ্রাসঙ্গিক শীর্ষবিন্দু ক্ষেত্রে:
   - Irrelevant-Vertex অ্যালগরিদম প্রয়োগ করুন
   - পুনরাবৃত্তিমূলকভাবে G-v প্রক্রিয়া করুন
5. শাখা ক্ষেত্রে:
   - বাধ্যতামূলক শীর্ষবিন্দু সেট খুঁজে পান
   - সংশোধন পদ্ধতি অনুমান করুন এবং পুনরাবৃত্তিমূলকভাবে প্রক্রিয়া করুন

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

1. প্রসারিত সমজাতীয়তার সংজ্ঞা

ঐতিহ্যবাহী সংজ্ঞা শুধুমাত্র শীর্ষবিন্দু মুছে ফেলা বিবেচনা করে, নতুন সংজ্ঞা যেকোনো $\mathcal{L}$ -সংশোধন পরিচালনা করতে হবে:

A-বর্ধিত ফ্ল্যাপ: flatness জোড়া $(W,R)$ এবং শীর্ষবিন্দু সেট $A$ এর জন্য, বর্ধিত ফ্ল্যাপ $F^A$ সংজ্ঞায়িত করুন
প্যালেট: $(\mathcal{A}, \ell)$ -palette $(C) = \{\ell\text{-folio}(F^A) | F \in \text{influence}_R(C)\}$
সমজাতীয়তা: সমস্ত অভ্যন্তরীণ ইট একই প্যালেট থাকার প্রয়োজন

2. সীমাবদ্ধ অপচয়ের বিশেষ চিকিত্সা

সমতল এম্বেডিংয়ের বিশেষ বৈশিষ্ট্য ব্যবহার করে:

বাধ্যতামূলক সেট আকার 1: সীমাবদ্ধ অপচয় ক্ষেত্রে, $a_F = 1$
ছোট সমজাতীয় সমতল দেয়াল: Lemma 5.1 প্রমাণ করে যে নির্দিষ্ট শর্তে সরাসরি সমজাতীয়তা পাওয়া যায়
উন্নত চলমান সময়: সাধারণ ক্ষেত্রে বিশাল দেয়াল আকারের প্রয়োজনীয়তা এড়ায়

পরীক্ষামূলক সেটআপ

এই পেপারটি একটি বিশুদ্ধ তাত্ত্বিক কাজ, এতে পরীক্ষামূলক মূল্যায়ন অন্তর্ভুক্ত নেই। সমস্ত ফলাফল তাত্ত্বিক অ্যালগরিদম জটিলতা বিশ্লেষণ।

উপসংহার এবং আলোচনা

প্রধান উপসংহার

তাত্ত্বিক অগ্রগতি: প্রথমবারের মতো $2^{\text{poly}(k)} \cdot n^2$ সময়ে অসংখ্য গ্রাফ সংশোধন সমস্যা মাইনর-বদ্ধ শ্রেণীতে সমাধান করে
প্রযুক্তিগত অবদান: অপ্রাসঙ্গিক শীর্ষবিন্দু প্রযুক্তি সাধারণ সংশোধন ক্রিয়াকলাপে সফলভাবে প্রসারিত করে
ব্যবহারিক উন্নতি: সীমাবদ্ধ অপচয় ক্ষেত্রে উল্লেখযোগ্য উন্নত $2^{\mathcal{O}(k^9)} \cdot n^2$ অ্যালগরিদম প্রদান করে

সীমাবদ্ধতা

প্যারামিটার নির্ভরতা বিশাল: যদিও এটি একক-সূচক, poly $(k)$ এর ডিগ্রি এখনও খুব বড় (কমপক্ষে $2^{2^{s_F^{24}}}$ )
উত্তরাধিকার সীমাবদ্ধতা: প্রতিস্থাপন ক্রিয়া অবশ্যই উত্তরাধিকারী হতে হবে, কিছু প্রাকৃতিক সমস্যা বাদ দেয়
তাত্ত্বিক প্রকৃতি: অ্যালগরিদম প্রধানত তাত্ত্বিক তাৎপর্য রাখে, ব্যবহারিক বাস্তবায়ন চ্যালেঞ্জের সম্মুখীন হতে পারে

ভবিষ্যত দিকনির্দেশনা

প্যারামিটার নির্ভরতা উন্নতি: poly $(k)$ এর ডিগ্রি হ্রাস করার জন্য নতুন কৌশল খুঁজে পান
অ-উত্তরাধিকার ক্ষেত্রে: অ-উত্তরাধিকার প্রতিস্থাপন ক্রিয়াকলাপ কীভাবে পরিচালনা করতে হয় তা অধ্যয়ন করুন
ব্যবহারিক অ্যালগরিদম: ব্যবহারিক মূল্য সহ অ্যালগরিদম ভেরিয়েন্ট বিকাশ করুন
প্রসারিত প্রয়োগ: অসীম আকারের সংশোধন জড়িত সমস্যা বিবেচনা করুন

গভীর মূল্যায়ন

সুবিধা

তাত্ত্বিক গভীরতা: একাধিক গুরুত্বপূর্ণ গ্রাফ সংশোধন সমস্যা সফলভাবে একীভূত করে, গভীর তাত্ত্বিক অন্তর্দৃষ্টি প্রদান করে
প্রযুক্তিগত উদ্ভাবন: অপ্রাসঙ্গিক শীর্ষবিন্দু প্রযুক্তির সম্প্রসারণ অত্যন্ত উচ্চ প্রযুক্তিগত কঠিনতা এবং উদ্ভাবনী
ফলাফল তাৎপর্য: প্রথমবারের মতো অসংখ্য গ্রাফ সংশোধন সমস্যার জন্য যুক্তিসঙ্গত প্যারামিটারকৃত অ্যালগরিদম প্রদান করে
লেখার গুণমান: পেপারটি স্পষ্ট কাঠামো, পর্যাপ্ত প্রযুক্তিগত বিবরণ এবং নির্ভুল গাণিতিক অভিব্যক্তি রয়েছে

অপূর্ণতা

জটিলতা ধ্রুবক: যদিও এটি FPT অ্যালগরিদম, লুকানো ধ্রুবক অত্যন্ত বিশাল, ব্যবহারিকতা সীমিত করে
প্রযুক্তিগত জটিলতা: অ্যালগরিদম অসংখ্য জটিল গ্রাফ তাত্ত্বিক ধারণা জড়িত, বোঝা এবং বাস্তবায়নের প্রবেশদ্বার উচ্চ
প্রযোজ্য সীমাবদ্ধতা: উত্তরাধিকার শর্ত যদিও প্রযুক্তিগতভাবে প্রয়োজনীয়, তবে সমস্যার কভারেজ পরিসীমা সীমিত করে

প্রভাব

তাত্ত্বিক অবদান: প্যারামিটারকৃত অ্যালগরিদম তত্ত্বে গুরুত্বপূর্ণ অবদান করে, বিশেষত গ্রাফ সংশোধন সমস্যা ক্ষেত্রে
পদ্ধতি মূল্য: প্রসারিত অপ্রাসঙ্গিক শীর্ষবিন্দু প্রযুক্তি অন্যান্য সমস্যার জন্য অনুপ্রেরণা হতে পারে
গবেষণা দিকনির্দেশনা: প্যারামিটার নির্ভরতা উন্নত করা এবং আরও সাধারণ সমস্যা পরিচালনার জন্য পরবর্তী উন্নতির ভিত্তি স্থাপন করে

প্রযোজ্য পরিস্থিতি

এই অ্যালগরিদম প্রধানত প্রযোজ্য:

তাত্ত্বিক গবেষণা: নির্দিষ্ট সমস্যা শ্রেণীর সমাধানযোগ্যতা প্রমাণ করতে
ছোট প্যারামিটার ক্ষেত্রে: যখন $k$ ছোট হয় তখন ব্যবহারিক মূল্য থাকতে পারে
অ্যালগরিদম ডিজাইন: আরও ব্যবহারিক হিউরিস্টিক অ্যালগরিদম ডিজাইনের জন্য তাত্ত্বিক নির্দেশনা প্রদান করতে

প্রযুক্তিগত বিবরণ সম্পূরক

সমতল দেয়াল প্রযুক্তি

দেয়াল কাঠামো: $r$ -দেয়াল প্রাথমিক দেয়ালের প্রান্ত বিভাজন করে প্রাপ্ত সমতল গ্রাফ
Flatness জোড়া: $(W,R)$ যেখানে $R$ বিভাজন $(X,Y)$ এবং rendition $(Γ,σ,π)$ অন্তর্ভুক্ত করে
সমজাতীয়তা: সমস্ত অভ্যন্তরীণ ইটের বর্ধিত ফ্ল্যাপ একই টপোলজিক্যাল মাইনর বৈশিষ্ট্য থাকার প্রয়োজন

গতিশীল প্রোগ্রামিং অ্যালগরিদম

Nice ট্রি বিয়োজন: মান introduce, forget, join নোড ব্যবহার করে
প্রতিনিধিত্ব প্রযুক্তি: সীমাবদ্ধ আকারের প্রতিনিধি গ্রাফ ব্যবহার করে অবস্থা স্থান নিয়ন্ত্রণ করে
সীমানা প্রক্রিয়াকরণ: সংশোধন শীর্ষবিন্দু সীমানায় থাকার ক্ষেত্রে সাবধানে প্রক্রিয়া করে

এই পেপারটি গ্রাফ সংশোধন সমস্যায় প্যারামিটারকৃত অ্যালগরিদম তত্ত্বের গুরুত্বপূর্ণ অগ্রগতি প্রতিনিধিত্ব করে। যদিও ব্যবহারিক প্রয়োগ সীমিত, তবে এই ক্ষেত্রের তাত্ত্বিক উন্নয়নে গুরুত্বপূর্ণ অবদান রাখে।