2025-11-21T08:22:15.372442

An efficient algorithm for \textsc{$\mathcal{F}$-subgraph-free Edge Deletion} on graphs having a product structure

An, Im, Kim et al.
Given a family $\mathcal{F}$ of graphs, a graph is \emph{$\mathcal{F}$-subgraph-free} if it has no subgraph isomorphic to a member of $\mathcal{F}$. We present a fixed-parameter linear-time algorithm that decides whether a planar graph can be made $\mathcal{F}$-subgraph-free by deleting at most $k$ vertices or $k$ edges, where the parameters are $k$, $\lvert \mathcal{F} \rvert$, and the maximum number of vertices in a member of $\mathcal{F}$. The running time of our algorithm is double-exponential in the parameters, which is faster than the algorithm obtained by applying the first-order model checking result for graphs of bounded twin-width. To obtain this result, we develop a unified framework for designing algorithms for this problem on graphs with a ``product structure.'' Using this framework, we also design algorithms for other graph classes that generalize planar graphs. Specifically, the problem admits a fixed-parameter linear time algorithm on disk graphs of bounded local radius, and a fixed-parameter almost-linear time algorithm on graphs of bounded genus. Finally, we show that our result gives a tight fixed-parameter algorithm in the following sense: Even when $\mathcal{F}$ consists of a single graph $F$ and the input is restricted to planar graphs, it is unlikely to drop any parameters $k$ and $\lvert V(F) \rvert$ while preserving fixed-parameter tractability, unless the Exponential-Time Hypothesis fails.
academic

পণ্য কাঠামো সহ গ্রাফে F-সাবগ্রাফ-মুক্ত প্রান্ত মুছে ফেলার জন্য একটি দক্ষ অ্যালগরিদম

মৌলিক তথ্য

  • পত্র ID: 2510.14674
  • শিরোনাম: পণ্য কাঠামো সহ গ্রাফে F-সাবগ্রাফ-মুক্ত প্রান্ত মুছে ফেলার জন্য একটি দক্ষ অ্যালগরিদম
  • লেখক: শিনউ আন (বার-ইলান বিশ্ববিদ্যালয়), সিওংহিউক ইম (KAIST এবং IBS), সিওকবিওম কিম (KAIST এবং IBS), ময়ূর্ঘওয়ান লি (হানইয়াং বিশ্ববিদ্যালয়)
  • শ্রেণীবিভাগ: cs.DM (বিচ্ছিন্ন গণিত), cs.DS (ডেটা কাঠামো এবং অ্যালগরিদম), math.CO (সমন্বয়মূলক গণিত)
  • প্রকাশনার সময়: ২০২৫ সালের অক্টোবর ১৭ (arXiv প্রিপ্রিন্ট)
  • পত্র লিঙ্ক: https://arxiv.org/abs/2510.14674

সারসংক্ষেপ

গ্রাফ পরিবার F\mathcal{F} দেওয়া হলে, যদি একটি গ্রাফে F\mathcal{F} এর কোনো সদস্যের সাথে সমরূপী কোনো সাবগ্রাফ না থাকে, তাহলে সেই গ্রাফকে F\mathcal{F}-সাবগ্রাফ-মুক্ত বলা হয়। এই পত্রটি একটি নির্ধারিত পরামিতি রৈখিক সময়ের অ্যালগরিদম উপস্থাপন করে যা নির্ধারণ করে যে একটি সমতল গ্রাফ সর্বাধিক kk টি প্রান্ত মুছে ফেলার মাধ্যমে F\mathcal{F}-সাবগ্রাফ-মুক্ত করা যায় কিনা, যেখানে পরামিতি হল kk, ∣F∣|\mathcal{F}| এবং F\mathcal{F} এর গ্রাফগুলির সর্বাধিক শীর্ষবিন্দু সংখ্যা। অ্যালগরিদমের চলার সময় পরামিতির সাপেক্ষে দ্বিগুণ সূচকীয়, যা সীমাবদ্ধ twin-width গ্রাফে প্রথম-ক্রম মডেল পরীক্ষার ফলাফল প্রয়োগ করে প্রাপ্ত অ্যালগরিদমের চেয়ে দ্রুত।

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

সমস্যার সংজ্ঞা

F-সাবগ্রাফ-মুক্ত প্রান্ত মুছে ফেলা সমস্যা নিম্নরূপ সংজ্ঞায়িত:

  • ইনপুট: গ্রাফ GG এবং অ-নেতিবাচক পূর্ণসংখ্যা kk
  • কাজ: নির্ধারণ করুন যে আকার সর্বাধিক kk এর একটি প্রান্ত সেট S⊆E(G)S \subseteq E(G) বিদ্যমান কিনা যাতে G−SG - S F\mathcal{F} এর কোনো গ্রাফ সাবগ্রাফ হিসাবে অন্তর্ভুক্ত না করে

গবেষণার তাৎপর্য

  1. ব্যবহারিক প্রয়োগ মূল্য: এই সমস্যা বাস্তব-বিশ্বের বিভিন্ন পরিস্থিতি মডেল করতে পারে, যেমন:
    • প্রাণী রোগ ছড়িয়ে পড়া নিয়ন্ত্রণ: গ্রাফ খামারের মধ্যে সংক্রমণ নেটওয়ার্ক প্রতিনিধিত্ব করে, লক্ষ্য হল কয়েকটি সংযোগ নিষিদ্ধ করে মহামারী নিয়ন্ত্রণ করা
    • নেটওয়ার্ক নিরাপত্তা: কয়েকটি প্রান্ত মুছে ফেলার মাধ্যমে দূষিত নেটওয়ার্ক কাঠামো ভাঙা
  2. তাত্ত্বিক গুরুত্ব:
    • প্রান্ত দ্বিপক্ষীকরণ (Edge Bipartization) এবং প্রতিক্রিয়া চাপ সেট (Feedback Arc Set) এর মতো অনেক ক্লাসিক সমস্যা অন্তর্ভুক্ত করে
    • গ্রাফ সংশোধন সমস্যার একটি গুরুত্বপূর্ণ বিশেষ ক্ষেত্র

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

  1. জটিলতা বাধা: এমনকি যদি F\mathcal{F} শুধুমাত্র একটি একক গ্রাফ FF অন্তর্ভুক্ত করে, এই সমস্যা অনেক গ্রাফ FF এর জন্য NP-সম্পূর্ণ
  2. পরামিতিযুক্ত জটিলতা:
    • শুধুমাত্র সমাধানের আকার kk কে পরামিতি হিসাবে ব্যবহার করলে, সমস্যা W1-সম্পূর্ণ সমস্যা অন্তর্ভুক্ত করে (যেমন ক্লিক এবং স্বাধীন সেট)
    • শুধুমাত্র গাছের প্রস্থকে পরামিতি হিসাবে ব্যবহার করলে, সমস্যা W2-কঠিন
  3. চলার সময়: বিদ্যমান twin-width পদ্ধতি টাওয়ার-নির্ভর চলার সময় উৎপন্ন করে

মূল অবদান

  1. একীভূত অ্যালগরিদম কাঠামো: গ্রাফ পণ্য কাঠামোর উপর ভিত্তি করে একটি একীভূত কাঠামো বিকশিত করেছে, যা পণ্য কাঠামো সহ গ্রাফ শ্রেণীর জন্য প্রযোজ্য
  2. দক্ষ অ্যালগরিদম:
    • সমতল গ্রাফে নির্ধারিত পরামিতি রৈখিক সময়ের অ্যালগরিদম (সময় জটিলতা 2O(∣F∣2kr3)⋅n2^{O(|\mathcal{F}|^2kr^3)} \cdot n)
    • সীমাবদ্ধ স্থানীয় ব্যাসার্ধ ডিস্ক গ্রাফে নির্ধারিত পরামিতি রৈখিক সময়ের অ্যালগরিদম
    • সীমাবদ্ধ গণ গ্রাফে নির্ধারিত পরামিতি প্রায়-রৈখিক সময়ের অ্যালগরিদম
  3. পণ্য কাঠামো তত্ত্ব সম্প্রসারণ: প্রমাণ করেছে যে সীমাবদ্ধ স্থানীয় ব্যাসার্ধের ডিস্ক গ্রাফ পণ্য কাঠামো রাখে
  4. কঠোরতা ফলাফল: প্রমাণ করেছে যে অ্যালগরিদম পরামিতি নির্ভরতার ক্ষেত্রে সর্বোত্তম, যদি না সূচকীয় সময় অনুমান ব্যর্থ হয়

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

মূল প্রযুক্তিগত কাঠামো

গ্রাফ পণ্য কাঠামো

দুটি গ্রাফ GG এবং HH এর জন্য, শক্তিশালী পণ্য G⊠HG \boxtimes H নিম্নরূপ সংজ্ঞায়িত:

  • শীর্ষবিন্দু সেট: V(G)×V(H)V(G) \times V(H)
  • প্রান্ত সেট: দুটি শীর্ষবিন্দু (u,v)(u,v) এবং (u′,v′)(u',v') সংলগ্ন যখন এবং শুধুমাত্র যখন নিম্নলিখিত শর্তগুলির মধ্যে একটি সন্তুষ্ট হয়:
    • u=u′u = u' এবং vv′∈E(H)vv' \in E(H)
    • v=v′v = v' এবং uu′∈E(G)uu' \in E(G)
    • uu′∈E(G)uu' \in E(G) এবং vv′∈E(H)vv' \in E(H)

যদি গ্রাফ শ্রেণী C\mathcal{C} এর প্রতিটি গ্রাফ কোনো গাছের প্রস্থ সর্বাধিক ww এর গ্রাফ HH এবং পথ PP এর শক্তিশালী পণ্যের একটি সাবগ্রাফ হয়, তাহলে C\mathcal{C} পণ্য কাঠামো রাখে বলা হয়।

প্রধান অ্যালগরিদম কাঠামো (উপপাদ্য 1.5)

ইনপুট:

  • গ্রাফ GG (nn শীর্ষবিন্দু সহ)
  • গ্রাফ HH (গাছের প্রস্থ ≤w\leq w) এবং পথ PP
  • GG থেকে H⊠PH \boxtimes P এর এম্বেডিং

আউটপুট: GG এ F\mathcal{F}-সাবগ্রাফ-মুক্ত প্রান্ত মুছে ফেলা সমস্যার সমাধান

সময় জটিলতা: 2O(∣F∣2kr3w)⋅n2^{O(|\mathcal{F}|^2kr^3w)} \cdot n

অ্যালগরিদম ডিজাইন

স্তরযুক্ত কৌশল

  1. স্তরের সংজ্ঞা: পথ PP এর শীর্ষবিন্দুগুলিকে [ℓ][ℓ] হিসাবে চিহ্নিত করুন, ii-তম স্তরকে Vi=(V(H)×{i})∩V(G)V_i = (V(H) \times \{i\}) \cap V(G) হিসাবে সংজ্ঞায়িত করুন
  2. ব্যবধান বিভাজন: প্রতিটি পূর্ণসংখ্যা jj এর জন্য, Ij=[3(j−1)r+1,3jr]I_j = [3(j-1)r+1, 3jr] এবং VIj=⋃i∈IjViV_{I_j} = \bigcup_{i \in I_j} V_i সংজ্ঞায়িত করুন

বিচ্ছিন্ন সংযুক্ত উপাদান পরিচালনার মূল অন্তর্দৃষ্টি (উপপাদ্য 3.2)

ধরুন CC হল F∈FF \in \mathcal{F} এর একটি সংযুক্ত উপাদান, F′=F∖V(C)F' = F \setminus V(C)। যদি কমপক্ষে k+rk+r টি ভিন্ন বিজোড় সূচক jj বিদ্যমান থাকে যাতে G[VIj]G[V_{I_j}] CC এর একটি অনুলিপি অন্তর্ভুক্ত করে, তাহলে:

  • যেকোনো সমাধান অবশ্যই F′F' এর সমস্ত অনুলিপি মুছে ফেলবে
  • সমস্যা (F∖{F})∪{F′}(\mathcal{F} \setminus \{F\}) \cup \{F'\}-সাবগ্রাফ-মুক্ত প্রান্ত মুছে ফেলার সমতুল্য

অ্যালগরিদম পদক্ষেপ

  1. প্রথম পর্যায়: পুনরাবৃত্তিমূলকভাবে পরীক্ষা করুন যে সংযুক্ত উপাদান অনুলিপির অত্যধিক সংখ্যা বিদ্যমান কিনা, যদি থাকে তাহলে সেই অনুযায়ী F\mathcal{F} সংশোধন করুন
  2. দ্বিতীয় পর্যায়: সংযুক্ত উপাদান অনুলিপি সহ স্তরগুলির "মধ্য" অংশ মুছে ফেলুন, গাছের প্রস্থ সীমাবদ্ধ গ্রাফ পান
  3. চূড়ান্ত সমাধান: গাছের প্রস্থ সীমাবদ্ধ গ্রাফে বিদ্যমান অ্যালগরিদম প্রয়োগ করুন

পণ্য কাঠামো সম্প্রসারণ

ডিস্ক গ্রাফের পণ্য কাঠামো (উপপাদ্য 1.7)

প্রধান ফলাফল: প্রতিটি স্থানীয় ব্যাসার্ধ সর্বাধিক ρ\rho এর ডিস্ক গ্রাফ H⊠PH \boxtimes P এর একটি সাবগ্রাফ, যেখানে HH এর গাছের প্রস্থ O(ρ9)O(\rho^9), PP একটি পথ।

মূল প্রযুক্তি:

  1. বিন্যাস গ্রাফ: ডিস্ক পরিবার D\mathcal{D} এর বিন্যাস গ্রাফ ADA_{\mathcal{D}} ব্যবহার করুন
  2. গভীরতা-dd নাবালক মডেল: ব্যাসার্ধ সীমাবদ্ধ নাবালক মডেল ধারণা প্রবর্তন করুন
  3. স্ফীতকরণ অপারেশন: স্ফীতকরণ অপারেশনের মাধ্যমে ডিস্ক গ্রাফ এবং বিন্যাস গ্রাফ সংযুক্ত করুন

রৈখিক সময় গণনা

অ্যালগরিদম জটিলতা: 2O(ρ)⋅n2^{O(\rho)} \cdot n

প্রধান পদক্ষেপ:

  1. বিন্যাস গ্রাফ ADA_{\mathcal{D}} গণনা করুন (সময় O(ρn)O(\rho n))
  2. স্ফীত গ্রাফ AD′A'_{\mathcal{D}} গণনা করুন (সময় O(ρ3n)O(\rho^3 n))
  3. গভীরতা-ρ\rho নাবালক মডেল নির্মাণ করুন (সময় 2O(ρ)⋅n2^{O(\rho)} \cdot n)

পরীক্ষামূলক ফলাফল

তাত্ত্বিক ফলাফল

পত্রটি প্রধানত তাত্ত্বিক ফলাফল প্রদান করে, যার মধ্যে রয়েছে:

  1. সমতল গ্রাফ: সময় জটিলতা 2O(∣F∣2kr3)⋅n2^{O(|\mathcal{F}|^2kr^3)} \cdot n
  2. সীমাবদ্ধ গণ গ্রাফ: সময় জটিলতা 2O(∣F∣2gkr3)⋅nlog⁡n2^{O(|\mathcal{F}|^2gkr^3)} \cdot n \log n
  3. সীমাবদ্ধ স্থানীয় ব্যাসার্ধ ডিস্ক গ্রাফ: সময় জটিলতা 2O(∣F∣2kr3ρ9)⋅n2^{O(|\mathcal{F}|^2kr^3\rho^9)} \cdot n

কঠোরতা প্রমাণ

প্রস্তাব 1.10: P4P_4-সাবগ্রাফ-মুক্ত প্রান্ত মুছে ফেলা সমস্যা সমতল গ্রাফে NP-কঠিন।

প্রমাণ কৌশল:

  1. সমতল 1-in-3-SAT সমস্যা থেকে হ্রাস
  2. জটিল gadget কাঠামো নির্মাণ (পরিবর্তনশীল gadget, ধারা gadget, বিভাজক gadget)
  3. Erdős-Gallai উপপাদ্য ব্যবহার করে সংযোগ স্থাপন

সম্পর্কিত কাজ

গ্রাফ সংশোধন সমস্যা

  • ক্লাসিক ফলাফল: প্রান্ত দ্বিপক্ষীকরণের O(1.977k)⋅nmO(1.977^k) \cdot nm অ্যালগরিদম
  • পরামিতিযুক্ত জটিলতা: গাছের প্রস্থ পরামিতিযুক্ত অ্যালগরিদম এবং W2-কঠিনতা ফলাফল

পণ্য কাঠামো তত্ত্ব

  • অগ্রগামী কাজ: Dujmović এবং অন্যদের সমতল গ্রাফ পণ্য কাঠামো উপপাদ্য
  • প্রয়োগ: সারি সংখ্যা, অ-পুনরাবৃত্তি রঙ, লেবেলিং স্কিম ইত্যাদি সমস্যার সমাধান
  • সম্প্রসারণ: kk-সমতল গ্রাফ, apex-minor-free গ্রাফ ইত্যাদি গ্রাফ শ্রেণীর পণ্য কাঠামো

Baker স্তরযুক্ত কৌশল

  • ক্লাসিক পদ্ধতি: সমতল গ্রাফে NP-সম্পূর্ণ সমস্যার PTAS এর জন্য ব্যবহৃত
  • এই পত্রের অবদান: প্রথমবারের মতো লক্ষ্য গ্রাফ বিচ্ছিন্ন করার প্রান্ত মুছে ফেলা সমস্যায় স্তরযুক্ত কৌশল প্রয়োগ

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

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

  1. পণ্য কাঠামোর উপর ভিত্তি করে একটি একীভূত অ্যালগরিদম কাঠামো বিকশিত করেছে, যা একাধিক গ্রাফ শ্রেণীতে F\mathcal{F}-সাবগ্রাফ-মুক্ত প্রান্ত মুছে ফেলা সমস্যা সমাধান করে
  2. প্রমাণ করেছে যে সীমাবদ্ধ স্থানীয় ব্যাসার্ধের ডিস্ক গ্রাফ পণ্য কাঠামো রাখে, পণ্য কাঠামো তত্ত্ব সম্প্রসারিত করেছে
  3. পরামিতি নির্ভরতার কঠোর নিম্ন সীমা প্রতিষ্ঠা করেছে

সীমাবদ্ধতা

  1. পরামিতি নির্ভরতা: অ্যালগরিদমের চলার সময় পরামিতির উপর দ্বিগুণ সূচকীয় নির্ভরতা রয়েছে
  2. গ্রাফ শ্রেণী সীমাবদ্ধতা: শুধুমাত্র পণ্য কাঠামো সহ গ্রাফ শ্রেণীতে প্রযোজ্য
  3. এম্বেডিং প্রয়োজনীয়তা: পণ্য কাঠামোতে গ্রাফের এম্বেডিং জানা প্রয়োজন

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

পত্রটি দুটি খোলা প্রশ্ন উপস্থাপন করে:

  1. প্রশ্ন 1: পণ্য কাঠামো খুঁজে পাওয়ার জন্য কি FPT আনুমানিক অ্যালগরিদম বিদ্যমান?
  2. প্রশ্ন 2: এম্বেডিং না দিয়ে, কি FPT অ্যালগরিদম বিদ্যমান?

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

সুবিধা

  1. তাত্ত্বিক উদ্ভাবন:
    • প্রথমবারের মতো সিস্টেমেটিকভাবে পণ্য কাঠামো তত্ত্ব গ্রাফ সংশোধন সমস্যায় প্রয়োগ করেছে
    • বিচ্ছিন্ন লক্ষ্য গ্রাফ পরিচালনার কৌশল অনন্য
  2. প্রযুক্তিগত অবদান:
    • ডিস্ক গ্রাফের নতুন পণ্য কাঠামো ফলাফল প্রমাণ করেছে
    • একীভূত অ্যালগরিদম কাঠামো প্রদান করেছে
  3. সম্পূর্ণতা:
    • অ্যালগরিদমের সঠিকতা প্রমাণ এবং জটিলতা বিশ্লেষণ প্রদান করেছে
    • কঠোর নিম্ন সীমা ফলাফল প্রতিষ্ঠা করেছে

অসুবিধা

  1. ব্যবহারিক সীমাবদ্ধতা:
    • দ্বিগুণ সূচকীয় পরামিতি নির্ভরতা ব্যবহারিক প্রয়োগ সীমিত করে
    • পণ্য কাঠামো এম্বেডিং পূর্ব-গণনা প্রয়োজন
  2. পরীক্ষামূলক যাচাইকরণ:
    • প্রকৃত ডেটায় পরীক্ষামূলক যাচাইকরণের অভাব
    • বিদ্যমান পদ্ধতির সাথে প্রকৃত কর্মক্ষমতা তুলনা নেই
  3. প্রযোজ্য পরিসীমা:
    • শুধুমাত্র পণ্য কাঠামো সহ নির্দিষ্ট গ্রাফ শ্রেণীতে প্রযোজ্য
    • সাধারণ গ্রাফ শ্রেণীর জন্য কোনো সমাধান প্রদান করে না

প্রভাব

  1. তাত্ত্বিক মূল্য: পরামিতিযুক্ত অ্যালগরিদম এবং গ্রাফ কাঠামো তত্ত্বে গুরুত্বপূর্ণ অবদান রেখেছে
  2. পদ্ধতিগত তাৎপর্য: অ্যালগরিদম ডিজাইনে পণ্য কাঠামোর শক্তিশালী প্রয়োগ সম্ভাবনা প্রদর্শন করেছে
  3. পরবর্তী গবেষণা: সম্পর্কিত সমস্যা গবেষণার জন্য নতুন প্রযুক্তিগত পথ প্রদান করেছে

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

  1. তাত্ত্বিক গবেষণা: পরামিতিযুক্ত অ্যালগরিদম এবং গ্রাফ তত্ত্বের গবেষণা ভিত্তি হিসাবে উপযুক্ত
  2. নির্দিষ্ট প্রয়োগ: নেটওয়ার্ক বিশ্লেষণে সমতল গ্রাফ বা ডিস্ক গ্রাফ জড়িত পরিস্থিতিতে প্রযোজ্য
  3. অ্যালগরিদম ডিজাইন: অন্যান্য গ্রাফ সংশোধন সমস্যার জন্য ডিজাইন টেমপ্লেট প্রদান করে

তথ্যসূত্র

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