Researcher profile

Shasha Li

Shasha Li contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
24works
0followers
11topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

24 published item(s)

preprint2026arXiv

EMP: Enhance Memory in Data Pruning

Recently, large language and vision models have shown strong performance, but due to high pre-training and fine-tuning costs, research has shifted towards faster training via dataset pruning. Previous methods used sample loss as an evaluation criterion, aiming to select the most "difficult" samples for training. However, when the pruning rate increases, the number of times each sample is trained becomes more evenly distributed, which causes many critical or general samples to not be effectively fitted. We refer to this as Low-Frequency Learning (LFL). In other words, LFL prevents the model from remembering most samples. In our work, we decompose the scoring function of LFL, provide a theoretical explanation for the inefficiency of LFL, and propose adding a memory term to the scoring function to enhance the model's memory capability, along with an approximation of this memory term. Similarly, we explore memory in Self-Supervised Learning (SSL), marking the first discussion on SSL memory. Using contrastive learning, we derive the memory term both theoretically and experimentally. Finally, we propose Enhance Memory Pruning (EMP), which addresses the issue of insufficient memory under high pruning rates by enhancing the model's memory of data, thereby improving its performance. We evaluated the performance of EMP in tasks such as image classification, natural language understanding, and model pre-training. The results show that EMP can improve model performance under extreme pruning rates. For example, in the CIFAR100-ResNet50 pre-training task, with 70\% pruning, EMP outperforms current methods by 2.2\%.

preprint2026arXiv

JPU: Bridging Jailbreak Defense and Unlearning via On-Policy Path Rectification

Despite extensive safety alignment, Large Language Models (LLMs) often fail against jailbreak attacks. While machine unlearning has emerged as a promising defense by erasing specific harmful parameters, current methods remain vulnerable to diverse jailbreaks. We first conduct an empirical study and discover that this failure mechanism is caused by jailbreaks primarily activating non-erased parameters in the intermediate layers. Further, by probing the underlying mechanism through which these circumvented parameters reassemble into the prohibited output, we verify the persistent existence of dynamic $\textbf{jailbreak paths}$ and show that the inability to rectify them constitutes the fundamental gap in existing unlearning defenses. To bridge this gap, we propose $\textbf{J}$ailbreak $\textbf{P}$ath $\textbf{U}$nlearning (JPU), which is the first to rectify dynamic jailbreak paths towards safety anchors by dynamically mining on-policy adversarial samples to expose vulnerabilities and identify jailbreak paths. Extensive experiments demonstrate that JPU significantly enhances jailbreak resistance against dynamic attacks while preserving the model's utility.

preprint2026arXiv

Rethinking Residual Distribution in Locate-then-Edit Model Editing

Model editing enables targeted updates to the knowledge of large language models (LLMs) with minimal retraining. Among existing approaches, locate-then-edit methods constitute a prominent paradigm: they first identify critical layers, then compute residuals at the final critical layer based on the target edit, and finally apply least-squares-based multi-layer updates via $\textbf{residual distribution}$. While empirically effective, we identify a counterintuitive failure mode: residual distribution, a core mechanism in these methods, introduces weight shift errors that undermine editing precision. Through theoretical and empirical analysis, we show that such errors increase with the distribution distance, batch size, and edit sequence length, ultimately leading to inaccurate or suboptimal edits. To address this, we propose the $\textbf{B}$oundary $\textbf{L}$ayer $\textbf{U}$pdat$\textbf{E (BLUE)}$ strategy to enhance locate-then-edit methods. Sequential batch editing experiments on three LLMs and two datasets demonstrate that BLUE not only delivers an average performance improvement of 35.59\%, significantly advancing the state of the art in model editing, but also enhances the preservation of LLMs' general capabilities. Our code is available at https://github.com/xpq-tech/BLUE.

preprint2026arXiv

Seeing Right but Saying Wrong: Inter- and Intra-Layer Refinement in MLLMs without Training

Multimodal Large Language Models (MLLMs) have demonstrated strong capabilities across a variety of vision-language tasks. However, their internal reasoning often exhibits a critical inconsistency: although deeper layers may attend to the correct visual regions, final predictions are frequently misled by noisy attention from earlier layers. This results in a disconnect between what the model internally understands and what it ultimately expresses, a phenomenon we describe as seeing it right but saying it wrong. To address this issue, we propose DualPD, a dual-perspective decoding refinement strategy that enhances the visual understanding without any additional training. DualPD consists of two components. (1) The layer-wise attention-guided contrastive logits module captures how the belief in the correct answer evolves by comparing output logits between layers that exhibit the largest attention shift. (2) The head-wise information filtering module suppresses low-contribution attention heads that focus on irrelevant regions, thereby improving attention quality within each layer. Experiments conducted on both the LLaVA and Qwen-VL model families across multiple multimodal benchmarks demonstrate that DualPD consistently improves accuracy without training, confirming its effectiveness and generalizability. The code will be released upon publication.

preprint2026arXiv

Where Does Vision Meet Language? Understanding and Refining Visual Fusion in MLLMs via Contrastive Attention

Multimodal Large Language Models (MLLMs) have achieved remarkable progress in vision-language understanding, yet how they internally integrate visual and textual information remains poorly understood. To bridge this gap, we perform a systematic layer-wise masking analysis across multiple architectures, revealing how visual-text fusion evolves within MLLMs. The results show that fusion emerges at several specific layers rather than being uniformly distributed across the network, and certain models exhibit a late-stage "review" phenomenon where visual signals are reactivated before output generation. Besides, we further analyze layer-wise attention evolution and observe persistent high-attention noise on irrelevant regions, along with gradually increasing attention on text-aligned areas. Guided by these insights, we introduce a training-free contrastive attention framework that models the transformation between early fusion and final layers to highlight meaningful attention shifts. Extensive experiments across various MLLMs and benchmarks validate our analysis and demonstrate that the proposed approach improves multimodal reasoning performance. Code will be released.

preprint2022arXiv

A Context-Aware Approach for Textual Adversarial Attack through Probability Difference Guided Beam Search

Textual adversarial attacks expose the vulnerabilities of text classifiers and can be used to improve their robustness. Existing context-aware methods solely consider the gold label probability and use the greedy search when searching an attack path, often limiting the attack efficiency. To tackle these issues, we propose PDBS, a context-aware textual adversarial attack model using Probability Difference guided Beam Search. The probability difference is an overall consideration of all class label probabilities, and PDBS uses it to guide the selection of attack paths. In addition, PDBS uses the beam search to find a successful attack path, thus avoiding suffering from limited search space. Extensive experiments and human evaluation demonstrate that PDBS outperforms previous best models in a series of evaluation metrics, especially bringing up to a +19.5% attack success rate. Ablation studies and qualitative analyses further confirm the efficiency of PDBS.

preprint2022arXiv

A Two-Phase Paradigm for Joint Entity-Relation Extraction

An exhaustive study has been conducted to investigate span-based models for the joint entity and relation extraction task. However, these models sample a large number of negative entities and negative relations during the model training, which are essential but result in grossly imbalanced data distributions and in turn cause suboptimal model performance. In order to address the above issues, we propose a two-phase paradigm for the span-based joint entity and relation extraction, which involves classifying the entities and relations in the first phase, and predicting the types of these entities and relations in the second phase. The two-phase paradigm enables our model to significantly reduce the data distribution gap, including the gap between negative entities and other entities, as well as the gap between negative relations and other relations. In addition, we make the first attempt at combining entity type and entity distance as global features, which has proven effective, especially for the relation extraction. Experimental results on several datasets demonstrate that the spanbased joint extraction model augmented with the two-phase paradigm and the global features consistently outperforms previous state-of-the-art span-based models for the joint extraction task, establishing a new standard benchmark. Qualitative and quantitative analyses further validate the effectiveness the proposed paradigm and the global features.

preprint2022arXiv

Anomalous transverse optic phonons in SnTe and PbTe -- revisited

We present a study of the soft transverse optic phonon mode in SnTe in comparison to the corresponding mode in PbTe using inelastic neutron scattering and ab-initio lattice dynamical calculations. In contrast to previous reports our calculations predict that the soft mode in SnTe features a strongly asymmetric spectral weight distribution qualitatively similar to that found in PbTe. Experimentally, we find that the overall width in energy of the phonon peaks is comparable in our neutron scattering spectra for SnTe and PbTe. We observe the well-known double-peak-like signature of the TO mode in PbTe even down to $T$ = 5 K questioning its proposed origin purely based on phonon-phonon scattering. The proximity to the incipient ferroelectric transition in PbTe likely plays an important role not included in current models.

preprint2022arXiv

Boosting Span-based Joint Entity and Relation Extraction via Squence Tagging Mechanism

Span-based joint extraction simultaneously conducts named entity recognition (NER) and relation extraction (RE) in text span form. Recent studies have shown that token labels can convey crucial task-specific information and enrich token semantics. However, as far as we know, due to completely abstain from sequence tagging mechanism, all prior span-based work fails to use token label in-formation. To solve this problem, we pro-pose Sequence Tagging enhanced Span-based Network (STSN), a span-based joint extrac-tion network that is enhanced by token BIO label information derived from sequence tag-ging based NER. By stacking multiple atten-tion layers in depth, we design a deep neu-ral architecture to build STSN, and each atten-tion layer consists of three basic attention units. The deep neural architecture first learns seman-tic representations for token labels and span-based joint extraction, and then constructs in-formation interactions between them, which also realizes bidirectional information interac-tions between span-based NER and RE. Fur-thermore, we extend the BIO tagging scheme to make STSN can extract overlapping en-tity. Experiments on three benchmark datasets show that our model consistently outperforms previous optimal models by a large margin, creating new state-of-the-art results.

preprint2022arXiv

Few-shot Named Entity Recognition with Entity-level Prototypical Network Enhanced by Dispersedly Distributed Prototypes

Few-shot named entity recognition (NER) enables us to build a NER system for a new domain using very few labeled examples. However, existing prototypical networks for this task suffer from roughly estimated label dependency and closely distributed prototypes, thus often causing misclassifications. To address the above issues, we propose EP-Net, an Entity-level Prototypical Network enhanced by dispersedly distributed prototypes. EP-Net builds entity-level prototypes and considers text spans to be candidate entities, so it no longer requires the label dependency. In addition, EP-Net trains the prototypes from scratch to distribute them dispersedly and aligns spans to prototypes in the embedding space using a space projection. Experimental results on two evaluation tasks and the Few-NERD settings demonstrate that EP-Net consistently outperforms the previous strong models in terms of overall performance. Extensive analyses further validate the effectiveness of EP-Net.

preprint2022arXiv

Multi-Document Scientific Summarization from a Knowledge Graph-Centric View

Multi-Document Scientific Summarization (MDSS) aims to produce coherent and concise summaries for clusters of topic-relevant scientific papers. This task requires precise understanding of paper content and accurate modeling of cross-paper relationships. Knowledge graphs convey compact and interpretable structured information for documents, which makes them ideal for content modeling and relationship modeling. In this paper, we present KGSum, an MDSS model centred on knowledge graphs during both the encoding and decoding process. Specifically, in the encoding process, two graph-based modules are proposed to incorporate knowledge graph information into paper encoding, while in the decoding process, we propose a two-stage decoder by first generating knowledge graph information of summary in the form of descriptive sentences, followed by generating the final summary. Empirical results show that the proposed architecture brings substantial improvements over baselines on the Multi-Xscience dataset.

preprint2022arXiv

Multi-Expert Adversarial Attack Detection in Person Re-identification Using Context Inconsistency

The success of deep neural networks (DNNs) has promoted the widespread applications of person re-identification (ReID). However, ReID systems inherit the vulnerability of DNNs to malicious attacks of visually inconspicuous adversarial perturbations. Detection of adversarial attacks is, therefore, a fundamental requirement for robust ReID systems. In this work, we propose a Multi-Expert Adversarial Attack Detection (MEAAD) approach to achieve this goal by checking context inconsistency, which is suitable for any DNN-based ReID systems. Specifically, three kinds of context inconsistencies caused by adversarial attacks are employed to learn a detector for distinguishing the perturbed examples, i.e., a) the embedding distances between a perturbed query person image and its top-K retrievals are generally larger than those between a benign query image and its top-K retrievals, b) the embedding distances among the top-K retrievals of a perturbed query image are larger than those of a benign query image, c) the top-K retrievals of a benign query image obtained with multiple expert ReID models tend to be consistent, which is not preserved when attacks are present. Extensive experiments on the Market1501 and DukeMTMC-ReID datasets show that, as the first adversarial attack detection approach for ReID, MEAAD effectively detects various adversarial attacks and achieves high ROC-AUC (over 97.5%).

preprint2022arXiv

SummScore: A Comprehensive Evaluation Metric for Summary Quality Based on Cross-Encoder

Text summarization models are often trained to produce summaries that meet human quality requirements. However, the existing evaluation metrics for summary text are only rough proxies for summary quality, suffering from low correlation with human scoring and inhibition of summary diversity. To solve these problems, we propose SummScore, a comprehensive metric for summary quality evaluation based on CrossEncoder. Firstly, by adopting the original-summary measurement mode and comparing the semantics of the original text, SummScore gets rid of the inhibition of summary diversity. With the help of the text-matching pre-training Cross-Encoder, SummScore can effectively capture the subtle differences between the semantics of summaries. Secondly, to improve the comprehensiveness and interpretability, SummScore consists of four fine-grained submodels, which measure Coherence, Consistency, Fluency, and Relevance separately. We use semi-supervised multi-rounds of training to improve the performance of our model on extremely limited annotated data. Extensive experiments show that SummScore significantly outperforms existing evaluation metrics in the above four dimensions in correlation with human scoring. We also provide the quality evaluation results of SummScore on 16 mainstream summarization models for later research.

preprint2022arXiv

Topic-Grained Text Representation-based Model for Document Retrieval

Document retrieval enables users to find their required documents accurately and quickly. To satisfy the requirement of retrieval efficiency, prevalent deep neural methods adopt a representation-based matching paradigm, which saves online matching time by pre-storing document representations offline. However, the above paradigm consumes vast local storage space, especially when storing the document as word-grained representations. To tackle this, we present TGTR, a Topic-Grained Text Representation-based Model for document retrieval. Following the representation-based matching paradigm, TGTR stores the document representations offline to ensure retrieval efficiency, whereas it significantly reduces the storage requirements by using novel topicgrained representations rather than traditional word-grained. Experimental results demonstrate that compared to word-grained baselines, TGTR is consistently competitive with them on TREC CAR and MS MARCO in terms of retrieval accuracy, but it requires less than 1/10 of the storage space required by them. Moreover, TGTR overwhelmingly surpasses global-grained baselines in terms of retrieval accuracy.

preprint2022arXiv

Win-Win Cooperation: Bundling Sequence and Span Models for Named Entity Recognition

For Named Entity Recognition (NER), sequence labeling-based and span-based paradigms are quite different. Previous research has demonstrated that the two paradigms have clear complementary advantages, but few models have attempted to leverage these advantages in a single NER model as far as we know. In our previous work, we proposed a paradigm known as Bundling Learning (BL) to address the above problem. The BL paradigm bundles the two NER paradigms, enabling NER models to jointly tune their parameters by weighted summing each paradigm's training loss. However, three critical issues remain unresolved: When does BL work? Why does BL work? Can BL enhance the existing state-of-the-art (SOTA) NER models? To address the first two issues, we implement three NER models, involving a sequence labeling-based model--SeqNER, a span-based NER model--SpanNER, and BL-NER that bundles SeqNER and SpanNER together. We draw two conclusions regarding the two issues based on the experimental results on eleven NER datasets from five domains. We then apply BL to five existing SOTA NER models to investigate the third issue, consisting of three sequence labeling-based models and two span-based models. Experimental results indicate that BL consistently enhances their performance, suggesting that it is possible to construct a new SOTA NER system by incorporating BL into the current SOTA system. Moreover, we find that BL reduces both entity boundary and type prediction errors. In addition, we compare two commonly used labeling tagging methods as well as three types of span semantic representations.

preprint2020arXiv

$k$-tree connectivity of line graphs

For a graph $G=(V,E)$ and a set $S\subseteq V(G)$ of size at least $2$, an $S$-Steiner tree $T$ is a subgraph of $G$ that is a tree with $S\subseteq V(T)$. Two $S$-Steiner trees $T$ and $T'$ are internally disjoint (resp. edge-disjoint) if $E(T)\cap E(T')=\emptyset$ and $V(T)\cap V(T')=S$ (resp. if $E(T)\cap E(T')=\emptyset$). Let $κ_G (S)$ (resp. $λ_G (S)$) denote the maximum number of internally disjoint (resp. edge-disjoint) $S$-Steiner trees in $G$. The $k$-tree connectivity $κ_k(G)$ (resp. $k$-tree edge-connectivity $λ_k(G)$) of $G$ is then defined as the minimum $κ_G (S)$ (resp. $λ_G (S)$), where $S$ ranges over all $k$-subsets of $V(G)$. In [H. Li, B. Wu, J. Meng, Y. Ma, Steiner tree packing number and tree connectivity, Discrete Math. 341(2018), 1945--1951], the authors conjectured that if a connected graph $G$ has at least $k$ vertices and at least $k$ edges, then $κ_k(L(G))\geq λ_k(G)$ for any $k\geq 2$, where $L(G)$ is the line graph of $G$. In this paper, we confirm this conjecture and prove that the bound is sharp.

preprint2020arXiv

A4 : Evading Learning-based Adblockers

Efforts by online ad publishers to circumvent traditional ad blockers towards regaining fiduciary benefits, have been demonstrably successful. As a result, there have recently emerged a set of adblockers that apply machine learning instead of manually curated rules and have been shown to be more robust in blocking ads on websites including social media sites such as Facebook. Among these, AdGraph is arguably the state-of-the-art learning-based adblocker. In this paper, we develop A4, a tool that intelligently crafts adversarial samples of ads to evade AdGraph. Unlike the popular research on adversarial samples against images or videos that are considered less- to un-restricted, the samples that A4 generates preserve application semantics of the web page, or are actionable. Through several experiments we show that A4 can bypass AdGraph about 60% of the time, which surpasses the state-of-the-art attack by a significant margin of 84.3%; in addition, changes to the visual layout of the web page due to these perturbations are imperceptible. We envision the algorithmic framework proposed in A4 is also promising in improving adversarial attacks against other learning-based web applications with similar requirements.

preprint2020arXiv

Connecting the Dots: Detecting Adversarial Perturbations Using Context Inconsistency

There has been a recent surge in research on adversarial perturbations that defeat Deep Neural Networks (DNNs) in machine vision; most of these perturbation-based attacks target object classifiers. Inspired by the observation that humans are able to recognize objects that appear out of place in a scene or along with other unlikely objects, we augment the DNN with a system that learns context consistency rules during training and checks for the violations of the same during testing. Our approach builds a set of auto-encoders, one for each object class, appropriately trained so as to output a discrepancy between the input and output if an added adversarial perturbation violates context consistency rules. Experiments on PASCAL VOC and MS COCO show that our method effectively detects various adversarial attacks and achieves high ROC-AUC (over 0.95 in most cases); this corresponds to over 20% improvement over a state-of-the-art context-agnostic method.

preprint2020arXiv

Measurement-driven Security Analysis of Imperceptible Impersonation Attacks

The emergence of Internet of Things (IoT) brings about new security challenges at the intersection of cyber and physical spaces. One prime example is the vulnerability of Face Recognition (FR) based access control in IoT systems. While previous research has shown that Deep Neural Network(DNN)-based FR systems (FRS) are potentially susceptible to imperceptible impersonation attacks, the potency of such attacks in a wide set of scenarios has not been thoroughly investigated. In this paper, we present the first systematic, wide-ranging measurement study of the exploitability of DNN-based FR systems using a large scale dataset. We find that arbitrary impersonation attacks, wherein an arbitrary attacker impersonates an arbitrary target, are hard if imperceptibility is an auxiliary goal. Specifically, we show that factors such as skin color, gender, and age, impact the ability to carry out an attack on a specific target victim, to different extents. We also study the feasibility of constructing universal attacks that are robust to different poses or views of the attacker's face. Our results show that finding a universal perturbation is a much harder problem from the attacker's perspective. Finally, we find that the perturbed images do not generalize well across different DNN models. This suggests security countermeasures that can dramatically reduce the exploitability of DNN-based FR systems.

preprint2020arXiv

Note on Path-Connectivity of Complete Bipartite Graphs

For a graph $G=(V,E)$ and a set $S\subseteq V(G)$ of size at least $2$, a path in $G$ is said to be an $S$-path if it connects all vertices of $S$. Two $S$-paths $P_1$ and $P_2$ are said to be internally disjoint if $E(P_1)\cap E(P_2)=\emptyset$ and $V(P_1)\cap V(P_2)=S$. Let $π_G (S)$ denote the maximum number of internally disjoint $S$-paths in $G$. The $k$-path-connectivity $π_k(G)$ of $G$ is then defined as the minimum $π_G (S)$, where $S$ ranges over all $k$-subsets of $V(G)$. In [M. Hager, Path-connectivity in graphs, Discrete Math. 59(1986), 53--59], the $k$-path-connectivity of the complete bipartite graph $K_{a,b}$ was calculated, where $k\geq 2$. But, from his proof, only the case that $2\leq k\leq min\{a,b\}$ was considered. In this paper, we calculate the the situation that $min\{a,b\}+1\leq k\leq a+b$ and complete the result.

preprint2011arXiv

Note on the complexity of deciding the rainbow connectedness for bipartite graphs

A path in an edge-colored graph is said to be a rainbow path if no two edges on the path have the same color. An edge-colored graph is (strongly) rainbow connected if there exists a rainbow (geodesic) path between every pair of vertices. The (strong) rainbow connection number of $G$, denoted by ($scr(G)$, respectively) $rc(G)$, is the smallest number of colors that are needed in order to make $G$ (strongly) rainbow connected. Though for a general graph $G$ it is NP-Complete to decide whether $rc(G)=2$, in this paper, we show that the problem becomes easy when $G$ is a bipartite graph. Moreover, it is known that deciding whether a given edge-colored (with an unbound number of colors) graph is rainbow connected is NP-Complete. We will prove that it is still NP-Complete even when the edge-colored graph is bipartite. We also show that a few NP-hard problems on rainbow connection are indeed NP-Complete.

preprint2011arXiv

Note on the minimal size of a graph with generalized connectivity kappa_3= 2

The concept of generalized $k$-connectivity $κ_{k}(G)$ of a graph $G$ was introduced by Chartrand et al. in recent years. In our early paper, extremal theory for this graph parameter was started. We determined the minimal number of edges of a graph of order $n$ with $κ_{3}= 2$, i.e., for a graph $G$ of order $n$ and size $e(G)$ with $κ_{3}(G)= 2$, we proved that $e(G)\geq (6/5)n$, and the lower bound is sharp by constructing a class of graphs, only for $n\equiv 0 \ (mod \ 5)$ and $n\neq 10$. In this paper, we improve the lower bound to $\lceil(6/5)n\rceil$. Moreover, we show that for all $n\geq 4$ but $n= 9, 10$, there always exists a graph of order $n$ with $κ_{3}= 2$ whose size attains the lower bound $\lceil(6/5)n\rceil$. Whereas for $n= 9, 10$ we give examples to show that $\lceil(6/5)n\rceil+1$ is the best possible lower bound. This gives a clear picture on the minimal size of a graph of order $n$ with generalized connectivity $κ_{3}= 2$.

preprint2010arXiv

Hardness results on generalized connectivity

Let $G$ be a nontrivial connected graph of order $n$ and let $k$ be an integer with $2\leq k\leq n$. For a set $S$ of $k$ vertices of $G$, let $κ(S)$ denote the maximum number $\ell$ of edge-disjoint trees $T_1,T_2,...,T_\ell$ in $G$ such that $V(T_i)\cap V(T_j)=S$ for every pair $i,j$ of distinct integers with $1\leq i,j\leq \ell$. A collection $\{T_1,T_2,...,T_\ell\}$ of trees in $G$ with this property is called an internally disjoint set of trees connecting $S$. Chartrand et al. generalized the concept of connectivity as follows: The $k$-$connectivity$, denoted by $κ_k(G)$, of $G$ is defined by $κ_k(G)=$min$\{κ(S)\}$, where the minimum is taken over all $k$-subsets $S$ of $V(G)$. Thus $κ_2(G)=κ(G)$, where $κ(G)$ is the connectivity of $G$, for which there are polynomial-time algorithms to solve it. This paper mainly focus on the complexity of the generalized connectivity. At first, we obtain that for two fixed positive integers $k_1$ and $k_2$, given a graph $G$ and a $k_1$-subset $S$ of $V(G)$, the problem of deciding whether $G$ contains $k_2$ internally disjoint trees connecting $S$ can be solved by a polynomial-time algorithm. Then, we show that when $k_1$ is a fixed integer of at least 4, but $k_2$ is not a fixed integer, the problem turns out to be NP-complete. On the other hand, when $k_2$ is a fixed integer of at least 2, but $k_1$ is not a fixed integer, we show that the problem also becomes NP-complete. Finally we give some open problems.

preprint2010arXiv

The generalized connectivity of complete bipartite graphs

Let $G$ be a nontrivial connected graph of order $n$, and $k$ an integer with $2\leq k\leq n$. For a set $S$ of $k$ vertices of $G$, let $κ(S)$ denote the maximum number $\ell$ of edge-disjoint trees $T_1,T_2,...,T_\ell$ in $G$ such that $V(T_i)\cap V(T_j)=S$ for every pair $i,j$ of distinct integers with $1\leq i,j\leq \ell$. Chartrand et al. generalized the concept of connectivity as follows: The $k$-$connectivity$, denoted by $κ_k(G)$, of $G$ is defined by $κ_k(G)=$min$\{κ(S)\}$, where the minimum is taken over all $k$-subsets $S$ of $V(G)$. Thus $κ_2(G)=κ(G)$, where $κ(G)$ is the connectivity of $G$. Moreover, $κ_{n}(G)$ is the maximum number of edge-disjoint spanning trees of $G$. This paper mainly focus on the $k$-connectivity of complete bipartite graphs $K_{a,b}$. First, we obtain the number of edge-disjoint spanning trees of $K_{a,b}$, which is $\lfloor\frac{ab}{a+b-1}\rfloor$, and specifically give the $\lfloor\frac{ab}{a+b-1}\rfloor$ edge-disjoint spanning trees. Then based on this result, we get the $k$-connectivity of $K_{a,b}$ for all $2\leq k \leq a+b$. Namely, if $k>b-a+2$ and $a-b+k$ is odd then $κ_{k}(K_{a,b})=\frac{a+b-k+1}{2}+\lfloor\frac{(a-b+k-1)(b-a+k-1)}{4(k-1)}\rfloor,$ if $k>b-a+2$ and $a-b+k$ is even then $κ_{k}(K_{a,b})=\frac{a+b-k}{2}+\lfloor\frac{(a-b+k)(b-a+k)}{4(k-1)}\rfloor,$ and if $k\leq b-a+2$ then $κ_{k}(K_{a,b})=a. $