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-उपग्राफ-मुक्त किनारा विलोपन के लिए एक कुशल एल्गोरिदम
  • लेखक: Shinwoo An (Bar-Ilan University), Seonghyuk Im (KAIST & IBS), Seokbeom Kim (KAIST & IBS), Myounghwan Lee (Hanyang University)
  • वर्गीकरण: cs.DM (असतत गणित), cs.DS (डेटा संरचना और एल्गोरिदम), math.CO (संयोजन गणित)
  • प्रकाशन समय: 17 अक्टूबर 2025 (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 प्रमेय का उपयोग करके संबंध स्थापित करें

संबंधित कार्य

ग्राफ़ संशोधन समस्याएँ

  • शास्त्रीय परिणाम: Edge Bipartization के लिए 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 संबंधित संदर्भों का हवाला देता है, जो पैरामीटरीकृत एल्गोरिदम, ग्राफ़ सिद्धांत, संयोजन अनुकूलन और अन्य कई क्षेत्रों के महत्वपूर्ण कार्यों को शामिल करते हैं, जो अनुसंधान के लिए एक ठोस सैद्धांतिक आधार प्रदान करते हैं।