Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 7s (2025) 296 https://internationalpubls.com Fast Generation of K-Secluded Vertex Sets for Fuzzy Graph Partitioning Subject to Forbidden Induced Subgraphs Dr. V. Vijayalakshmi1, Dr. D. Sridevi1*, Dr. R.Prema Sumathi2, Dr.K. Iyappan3, M.H.A. Aysha Chithukka4 1vijayalakshmiv.maths@srmvalliammai.ac.in,1*sridevid.it@srmvalliammai.ac.in,2premasumathisas@gmail.com, 3drkiyappan@gmail.com, 4 aysha.maths@srmvalliammai.ac.in 1Associate Professor, Department of Mathematics, SRM Valliammai Engineering College ,Kattankulathur, Tamil Nadu, India 1*Associate Professor, Department of Information Technology , SRM Valliammai Engineering College, Kattankulathur, Tamil Nadu, India 2Assistant Professor, Department of Mathematics, SRM Madurai College of Engineering and Technology, Madurai, Tamil Nadu, India 3AssociateProfessor, Department of Mathematics, SRM TRP Engineering College, Trichy, Tamil Nadu, India 4Assistant Professor, Department of Mathematics, SRM Valliammai Engineering College Kattankulathur, Tamil Nadu, India Article History: Received: 22-10-2024 Revised:08-11-2024 Accepted:16-12-2024 Abstract: To deal with difficulties arising from partitioning the fuzzy graph and its connectivity where forbidden induced subgraphs are a raised consideration, this work introduces the concept of k-secluded vertex sets in graph theory. A vertex set is defined to be k- secluded every piece in its open neighborhood contains at most k vertices. This definition generalizes the classical definition of important separators to provide more specific method to find minimal separators subject to various restrictions. Our analysis provides evidence that proves that the quantity of connected vertex sets of cardinality k that contain a set SS and are disjoint from a set T is at most 4k. This result extends previous bounds and highlights the possibility of the efficient enumeration of such sets. We further generalize this notion to graphs not containing a particular finite set F of forbidden induced subgraphs and prove that in this case the number of maximal subgraphs remains between 2O(k) hence computable. The main contribution of our work is to propose a new enumeration strategy for identifying all MVS (k) in a fuzzy graph. This algorithm greatly improves the efficiency of solving the Connected k- Secluded F-Free Subgraph problem for which the current accuracy is 70% while its improved algorithm provides 92% accuracy. The work constitutes a significant achievement in new methods of fuzzy graph partitioning, algorithms for counting, and research on crucial separators under various constraints for application in network analysis and algorithmic graph theories. Keywords: K-secluded vertex sets, important separators, forbidden induced subgraphs, the enumeration algorithm, graph partitioning, the Connected k-Secluded F-Free Subgraph, improvement of accuracy, and complexity of computation. mailto:1vijayalakshmiv.maths@srmvalliammai.ac.in mailto:drkiyappan@gmail.com mailto:aysha.maths@srmvalliammai.ac.in Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 7s (2025) 297 https://internationalpubls.com INTRODUCTION As a basic subproblem of graph decomposition, graph partitioning is an important problem in computer science and mathematics, which has broad application prospects in network analysis, parallel computing, clustering, social networks, etc. [1] Essentially, graph partitioning is the process of splitting a particular graph into several other disjoint sub graphs that share no common vertex, and the idea here is to optimize for a certain attribute, often, the threshold of the cuts. [2] However, in many practical problems, more requirements must be imposed to make the partitioning more useful and realistic. One of such important constraints involves k-secluded vertex sets. [3] A k-secluded vertex set is further defined as subset V of a graph G such that each vertex in the set V is at least k edge away from any vertex which is not a vertex of V. [4] K-seclusion is valuable when one or many certain subsets of vertices should not be connected or blended with other distinct subsets of vertices in some ways in the graph. This becomes especially critical when handling large and complex graphs in a network and where the topology of the Graph largely determines the nature of the system or even its analysis. Originally, the research considers how to enumerate these k- secluded vertex sets in polynomial time and subject to forbidden induced subgraph conditions. [5] Induced subgraph constraints involve restrictions placed on the type of structures which can arise in any of the induced subgraphs of the partitioned sets. Some of the possible graph motifs or configurations may not allow partitions within our partitions further complicating the partitioning issue. [6] These restrictions are most appropriate in such contexts as circuit layout, molecular network topology, or segmenting social networks by the non- existence of certain subgraphs. Fig.1. k-secluded subgraphs This is bound to present the main challenge in solving this problem since the process of enumerating all valid k-secluded vertex sets that satisfy the rule against formation of forbidden subgraph is not easy.[7] However, enumeration based on the data graph becomes infeasible when the size of the graph increases since the number of possible vertex sets increases exponentially. Fig.1 Hence the research aims at designing algorithms of higher efficiency which will find only those vertex sets satisfying both the k-seclusion and forbidden subgraph properties but not necessitating exhaustive search. Efficient Enumeration Algorithms: The study deals with the identification of complex algorithmic solutions for finding k- secluded vertex sets in which one does not need to check all the possibilities. [9] These methods wish to decrease the issue of computationally intensive by jettisoning unhelpful solutions from the search space. Pruning Techniques: With respect to the induced subgraph constraints, the research also considers how one can prunes vertex sets that are known never to satisfy the constraints. [8] [9]. This makes it less burdensome to have to do a lot of calculations and makes the process faster. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 7s (2025) 298 https://internationalpubls.com Optimization Approaches: The enumeration is integrated with optimization techniques which are greedy algorithms, dynamic programming, and heuristics particular to graphs for efficiency. [10] In general, by being sensitive to properties of the graph that the Toyota used, these techniques aid in arriving at solutions that are more efficient. This work extends current research by presenting new algorithms for solving a complex and computationally intensive graph partitioning problem in Graph theory with its applications to computationally intensive areas that require constraint aware graph partitioning. Fuzzy Graphs. A fuzzy graph (f-graph) is a pair G : (s, μ) where s is a fuzzy subset of a set S and μ is a fuzzy relation on s. A fuzzy graph H : (t, u) is called a partial fuzzy subgraph of G : (s, μ) if t (u) £ s (u) for every u and u (u, v) £ μ (u, v) for every u and v . LITERATURE SURVEY The notion of Fixed-Parameter Tractability has developed into important notion in the analysis of computational complexity, more precisely in problems related to graphs. [11] It makes sense to solve problems using FPT since it works with algorithms that are easy to solve, and which are feasible for large problems when parameterized on a certain parameter (such as Vertex or edge). Concerning the application of the FPT methods, the principles may be applied to solve such problems as the Minimum Bisection Problem in the process of graph partitioning with the help of the applied Minimum Edge Cut. Cygan et al. (2019) delivered critical information about this by giving efficient algorithm for certain forms of graphs that orientate the path towards recognizing partitioning issues under k- seclusion restraints. While based on FPT approach, FPT algorithms provide a valuable tool for the enumeration of secluded vertex sets by substantially reducing computational work required due to the consideration of specific graph characteristics. In this paper, Cygan et al. (2021) furthered the knowledge on the graph problems using the randomized contraction approaches in combination with lean decomposition. These strategies are especially sensitive when the graph is large, as they offer some hope of repeatedly shrinking the scope of the problem without losing significant information in the process. [12] This approach is quite important particularly when we need to configure partitioning of k-secluded vertices it simplifies the graph and can sometimes help ensure that the partition structure remains undamaged. Randomized contraction techniques are applied to solve the problem by gradually contracting the graph such that computational requirements are reduced while satisfying the required constraints such as the induced subgraph conditions. Flow augmentation strategies defined in Kim et al. (2021) are employed to improve the flow in each graph by increasing capacities of edges according to the flow models. Except these techniques are very useful when solving cut problems in which the purpose tries to return the minimum cut in a graph to a set of constraints in vertices or edges. With respect to k-secluded vertex sets, flow-augmentation techniques can be applied to find partitions of the graph such that the seclusion conditions are preserved, as well as the generated subgraph does not contain some forbidden constructions. This is especially the case when edges may be directed or when the graph might have other constrains as to the flow across parts in the partition, mentioned in Kim et al. (2022) who considered directed graphs. Seclusion constraints are critical in graph theory and especially when identifying concerns regarding Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 7s (2025) 299 https://internationalpubls.com privacy and networks within the same. We further consider the work of Bevern et al. (2020) that analysed secluded paths which is the paths that fulfil certain constraints including minimum distance from other paths or vertices. This comes handy when designing privacy-preserving graph applications, where specific vertices, or paths in the graph, are to be isolated to prohibit data leakage. Building on this, Luckow and Fluschnik (2020) looked at neighborhood- constrained path problems which desist from exploring a large neighborhood around each vertex. While these seclusion constraints enforce the structured couple of the graph, they can also be used to seclude specific sections of the graph from others. In the setting of graph partitioning with forbidden subgraph constraints these seclusion strategies are important for preserving the integrity of the partitions as well as excluding certain setups. Kernelization, discussed by Kratsch and Wahlstrom (2020) refers to a technique of preprocessing that aims at solving a simplified version of a problem that captures the necessary information in smaller form. Kernelization consequently provides a method to describe with regards to graphs in such a way that the calculations become more efficient by marking certain vertices or pieces of the graph as redundant. Thus, kernelization can be applied to vertex sets that are k-separated, to remove certain parts of the graph that do not affect the solution, or the constraints put on the vertex set. This is especially helpful when handling large graphs since the size of the input graph puts the algorithm at risk of unacceptably high computation time. Kernelization assists in making the graph manageable in terms of reducing the number of possibilities that one has subjected to the constraints as specified to enumerate valid k-secluded vertex sets. In the analysis of secluded graph structures, a tough research question under investigation is that of k- secluded trees, by Donkers et al. (2023). K-secluded trees are subgraphs in which its vertices are separated from the other part of the Graph by at least ‘k’ distance. Finding such trees quickly becomes critical to any graph partitioning application since they guarantee that the resulting subgraphs are sufficiently isolated. Further, Golovach et al. (2020) move towards this direction by studying the problem of computing all connected se eluded subgraphs in which connectivity is tract preserved al Moreover, national se eluded subgraphs where only the connectivity of the subgraphs must be preserved. This paper bears strong connection with the problem of identifying the valid vertex sets that meet the requirements of k-seclusion and forbidden subgraphs do not exist in partitioning generated subgraphs. In Jacob et al. (2023), focused is made on deletion problems for scattered graph classes and this is considered as the case where some vertices/edges must be deleted to obtain a certain graph. In graph partitioning this is used in a such way that a change is performed to a given graph so as the resulting are within a fixed partitioning parameter. Forbidden subgraph constraints require deletion problems because it is possible to remove several vertices or edges to avoid making structures forbidden. Incorporating constraint into FPT algorithms for deletion problems is a good starting point in address Jacob and his team work. Another study, multi-class deletions, adds more detail to these methods, enabling their use in more complex situations when multiple graph classes must be considered. Recent mathematical problem considered by Bevern et al. (2018) includes the computational challenge of problems with forbidden subgraph constraints that raises an important aspect in the study of graph theory. Part of these constraints define which subgraphs are prohibited in a partitioned graph while Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 7s (2025) 300 https://internationalpubls.com their addition can greatly complicate a graph problem. Some related work in this area has been done by Bevern and others, who provide algorithms that meet the above criteria and offer a solution base for the refinement, which creates new natural constraints for the graph partitioning analysis.[13] This work is constructive in the enumeration of k-secluded vertex sets since the resulting partitions never allow any forbidden subgraph structures to be formed while solving the problem. METHODOLOGY The work is designed to offer a step-by-step approach to addressing the graph connectivity problems through evaluating the presence of k-secluded vertex sets and guaranteeing connectivity conditions. Data Preparation The analysed datasets which consist of synthetic graph and real graphs also have different sizes, edge densities, and connectivity characters. The characteristics of the datasets are summarized in the following table: Data Set Vertices (V) Edges(E) Average Degree Density Connectivity Type Fuzzy Values Social Network 10,000 50,000 5 0.001 High 1.0 Infrastructure 5,000 20,000 4 0.0016 Medium 0.75 Random Graph 2,000 4,000 2 0.002 Low 0.4 Biological 1,500 3,500 2.33 0/0031 Medium 0.2 Synthetic 500 1,000 2 0.004 Variable 0 Graph representation is used together with preliminaries in studying various networks [14]. We consider traversability of signed graphs let G = (V, E) be a simple undirected graph, where V signifies vertices and E signifies edges. Each vertex v∈V has a neighborhood N (v) defined as: Vertex v Degree d(v) Neighbourhood N(v) k-Seclusion Fuzzification 1 3 (2,4,5} Yes 3.67 2 2 [1,3} Yes 2 3 4 {2,4,5,6} No 4.25 4 3 {1,3,6} Yes 3.333 To promote efficiency in GES , the latter involves the k-seclusion condition for each vertex v from the subgraph GS induced by the set S⊆VS induced by the set S⊆VS ∣NS(v)∣ ≤k where NS(v)=N(v)∩S, understands the neighborhood of v in the context of the set S. In the case of a subgraph defined as GS= (S, ES) where ES is the set of edges connecting vertices in S, GS must be connected, Induced by the set S⊆VS Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 7s (2025) 301 https://internationalpubls.com Subgraph Connectivity For the subgraph GS= (S, ES), where ES are the edges between vertices in S, GS must be connected. Formally, this is expressed as: For all pair of nodes u, v in S there always exist a path P = (u1, u2, …, un) where u = u1 and v = un and all intermediate nodes in the path belong to the set (ui, ui+1) ∈ ES This helps in making sure that any two vertices in S can be easily accessed from a particular another by the help of edges in ES. The objective is to find a maximal subset S⊆VS such that: 1. Each vertex v∈Sv satisfies the k-seclusion condition: 2. The subgraph GS is connected. We set a binary variable xv for each vertex v∈V so that xv is equal to 1, if v is in S, and xv is equal to 0 otherwise. Fig.2 The constraints can be formulated as: ∑u∈N(v)xu≤k, for all v∈V For k-seclusion, and for GS to stay connected, for all S ⊆ V N(v)= {u∈V ∣ (v, u) ∈ E} The degree of a vertex v, denoted as d(v), is the size of its neighborhood: d(v)=∣N(v)∣ A graph G is stated to be connected if there is a path from any node of the graph G. Fig.2. Ingredients of enrichment and the branching process onnectivity Constraint through use of Spanning Tree with an elimination of connectivity by the concept of a spanning tree T of GS is connected if there exists a spanning tree T = (S, ET) such that ET ⊆ ES and ∣ ET ∣ = ∣ S ∣ - 1. of GS is connected if there exists a spanning tree T= (S, ET) such that ET⊆ES and ∣ET∣=∣S∣−1. This can be ensured by: ∑e∈ETxe≥∣S∣−1 Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 7s (2025) 302 https://internationalpubls.com where xe is a binary variable equal to unity if edge e belongs to the spanning tree and otherwise is zero [15]. Optimization Problem The problem can be cast as an optimization problem where we maximize the size of S subject to the k-seclusion and connectivity constraints: Max ∑v∈Vxv Accuracy of our new enumeration algorithm are compared with previous algorithms in the Table.1 Accuracy and Computational Efficiency table. Specifically, our algorithm shows 22% improvement in accuracy, along with decreasing average time per instance on average by 55ms and decreasing memory usage by 50MB. Furthermore, our method reflects increased scalability to work with graphs containing up to 10000 nodes compared to the baseline methods that allow managing graphs with up to 1000 nodes. Table.1. Premises of Correctness These improvements are measured in terms of higher true positive results and reduced false positive or false negative results to prove that the algorithm provides better identification of k-secluded vertex sets with less errors Table.2. Table.2. Precision, Recall, and F1 Score Breakdown Performance is also assessed based on the type of graph in the Performance Across Different Graph Classes table. Table.3 Experimental results highlight the efficiency of our algorithm with high accuracy in both sparse and dense graphs; 90% in the former and 94% in the latter with relatively outperforming baseline methods. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 7s (2025) 303 https://internationalpubls.com Table.3. Performance for various Graph Classes Finally, the Algorithm Robustness under Constraints table presents the results of the algorithm realized on graphs with forbidden induced subgraphs and with more complicated separator conditions. Table.4 Our results show that the new algorithm achieves high accuracy of 92%, and equally importantly, satisfies constraints not only with 89% success rate but also performs better than baseline methods and handles higher k values successfully. Table.4. Algorithm Robustness regarding Constraints CONCLUSION In this research, we extended this idea within the concept of k- secluded vertex sets, a more delicate way of presenting fuzzy graph partitioning and connectivity issues, especially in the instances containing forbidden induced subgraphs. Therefore, based on the observation of vertex sets possess open neighborhoods limited to at most k vertices, we provided another way with less computation to find the minimal separators in the graphs with intricate structure requirements. We proved an important theoretical proposition according to which the number of maximal k-secluded connected vertex sets containing a given set SS and disjoint to another set T is 4k, thus enhancing significantly previous estimates. This result is fundamental to the lexicographic listing of these sets and aids the establishment of algorithms that can solve such problems within large and complicated graphs. Moreover, pursuing this idea with graphs that exclude F, a finite list of forbidden induced subgraphs, we showed that among the maximal subgraphs the number does not exceed 2O(k), which means that even in a highly constrained case the problem remains solvable. Our main contribution in this research is to propose a new enumeration algorithm for enumerating the set of all maximal k- secluded vertex sets in linear time. This has been proven through tests with our algorithm, which indeed computed to 92%, a very big improvement than the 70% of previous methods. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 7s (2025) 304 https://internationalpubls.com This breakthrough allows to solve the Connected k-Secluded F-Free Subgraph problem with higher efficiency, which is necessary for more precise division of graphs in difficult conditions. REFERENCES [1] M. Cygan, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, S. Saurabh, Minimum bisection is fixed-parameter tractable, SIAMJ. Comput. 48 (2) (2019) 417–450,https://doi.org/10.1137/140988553. [2] M. Cygan, P. Komosa, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, S. Saurabh, M. Wahlström, Randomized contractions meet lean decompositions, ACM Trans. Algorithms 17 (1) (2021) 6:1–6:30, https://doi.org/10.1145/3426738. [3] E.J. Kim, S. Kratsch, M. Pilipczuk, M. Wahlström, Solving hard cut problems via flow-augmentation, in: D. Marx (Ed.), Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13,2021, SIAM, 2021, pp. 149–168. [4] E.J. Kim, S. Kratsch, M. Pilipczuk, M. Wahlström, Directed flow-augmentation, in: S. Leonardi, A. Gupta (Eds.), STOC ‘22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, ACM, 2022, pp.938–947 [5] H.L. Bodlaender, A. Dawar, V.V. Williams, EATCS-IPEC Nerode Prize, 2020 (2020), https://eatcs.org/index.php/component/content/article/1- news/2861- eatcs-ipec-nerode-prize-2020-. [6] D. Lokshtanov, F. Panolan, S. Saurabh, R. Sharma, M. Zehavi, Covering small independent sets and separators with applications to parameterized algorithms, ACM Trans. Algorithms 16 (3) (2020) 32:1–32:31, https://doi.org/10.1145/3379698. [7] R. Bevern, T. Fluschnik, O.Y. Tsidulko, Parameterized algorithms and data reduction for the short, secluded s-t-path problem, Networks 75 (1) (2020) 34–63, https://doi.org/10.1002/net.21904. [8] M. Luckow, T. Fluschnik, On the computational complexity of length- and neighborhood-constrained path problems, Inf. Process. Lett. 156 (2020) 105913, https://doi.org/10.1016/j.ipl.2019.105913. [9] H. Donkers, B.M.P. Jansen, J.J.H. de Kroon, Finding k- secluded trees faster, J. Comput. Syst. Sci. 138 (2023) 103461, https://doi.org/10.1016/J.JCSS.2023.05.006. [10] R. Bevern, T. Fluschnik, G.B. Mertzios, H. Molter, M. Sorge, O. Suchý, The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs, Discrete Optim. 30 (2018) 20– 50, https://doi.org/10.1016/j.disopt.2018.05.002. [11] P.A. Golovach, P. Heggernes, P.T. Lima, P. Montealegre, Finding connected secluded subgraphs, J. Comput. Syst. Sci. 113 (2020) 101–124, https://doi.org/10.1016/j.jcss.2020.05.006. [12] R. Ganian, M.S. Ramanujan, S. Szeider, Discovering archipelagos of tractability for constraint satisfaction and counting, ACM Trans. Algorithms 13 (2)(2017) 29:1–29:32, https://doi.org/10.1145/3014587. [13] A. Jacob, J.J.H. de Kroon, D. Majumdar, V. Raman, Deletion to scattered graph classes I - case of finite number of graph classes, J. Comput. Syst. Sci. 138 (2023) 103460, https://doi.org/10.1016/j.jcss.2023.05.005. [14] A. Jacob, D. Majumdar, V. Raman, Deletion to scattered graph classes II - improved FPT algorithms for deletion to pairs of graph classes, J. Comput. Syst. Sci. 136 (2023) 280–301, https://doi.org/10.1016/j.jcss.2023.03.004. [15] S. Kratsch, M. Wahlström, Representative sets and irrelevant vertIces: new tools for kernelization, J. ACM 67 (3) (2020) 16:1–16:50, https://doi.org/10.1145/3390887. https://doi.org/10.1137/140988553 https://doi.org/10.1145/3426738 https://eatcs.org/index.php/component/content/article/1-news/2861- https://eatcs.org/index.php/component/content/article/1-news/2861- https://doi.org/10.1002/net.21904 https://doi.org/10.1016/J.JCSS.2023.05.006