In knockout tournaments, players compete in successive rounds, with losers eliminated and winners advancing until a single champion remains. Given a tournament digraph D, which encodes the outcomes of all possible matches, and a designated player v* in V(D), the Tournament Fixing problem (TFP) asks whether the tournament can be scheduled in a way that guarantees v* emerges as the winner. TFP is known to be NP-hard, but is fixed-parameter tractable (FPT) when parameterized by structural measures such as the feedback arc set (fas) or feedback vertex set (fvs) number of the tournament digraph. In this paper, we introduce and study two new structural parameters: the number of players who can defeat v* (i.e., the in-degree of v*, denoted by k) and the number of players that v* can defeat (i.e., the out-degree of v*, denoted by l). A natural question is that: can TFP be efficiently solved when k or l is small? We answer this question affirmatively by showing that TFP is FPT when parameterized by either the in-degree or out-degree of v*. Our algorithm for the in-degree parameterization is particularly involved and technically intricate. Notably, the in-degree k can remain small even when other structural parameters, such as fas or fvs, are large. Hence, our results offer a new perspective and significantly broaden the parameterized algorithmic understanding of the Tournament Fixing problem.

Parity-SAT is the problem of determining whether a given CNF formula has an odd number of satisfying assignments. As a canonical ⊕P-complete problem, it represents a fundamental variant of the exact model counting problem (#SAT). Under the Strong Exponential Time Hypothesis (SETH), Parity-SAT admits no O^*((2-ε)ⁿ)-time or O^*((2-ε)^m)-time algorithm for any constant ε > 0, where n and m denote the numbers of variables and clauses, respectively. Thus, breaking the 2ⁿ or 2^m barrier appears impossible in full generality. In this work, we revisit this barrier through structural restrictions and a refined exploitation of parity. We study Parity-d-occ-SAT, where each variable appears in at most d clauses, and obtain three main results. First, we design {a randomized} O^*(2^{m(1-1/O(d))})-time algorithm, thereby breaking the 2^m barrier for every fixed d. Second, for the special case d = 2, we develop a significantly sharper branching algorithm running in O^*(1.1193ⁿ) time or O^*(1.3248^m) time. Third, leveraging the structural insights underlying the d = 2 case, we obtain an O^*(1.1052^L)-time algorithm for general Parity-SAT, where L denotes the formula length. All algorithms use only polynomial space. Notably, our running-time bounds are better than the best known bounds for the corresponding exact counting counterparts, highlighting a genuine algorithmic advantage of parity over counting. Conceptually, our results demonstrate that parity admits finer structural reductions and more efficient branching than exact model counting, and that bounded occurrence can be systematically leveraged to circumvent classical exponential barriers.

We consider a novel vertex cover problem on temporal graphs, where the edges in the graph may change over time, and a vertex selected into the solution has a lifespan d. Specifically, a vertex selected at time t can cover all incident edges in graphs from time slot t to t+d-1. This model effectively captures the scenario of monitoring communication links via secure nodes (monitors) with limited lifespan in a dynamic network. We provide a systematic study of this problem from both theoretical and practical perspectives. We analyze its computational complexity, develop approximation and online algorithms with tight ratios, and present a parameterized algorithm and a tight quadratic kernel under fixed d. Experimental results on random and real-world temporal networks demonstrate the effectiveness of our algorithms. We believe that our systematic study not only reveals the nature of the problem itself, but also paves the way for investigating the ''sustained'' version of other problems on temporal graphs.

With the frequent occurrences of natural disasters and the rising risk of malicious attacks, improving network survivability and guaranteeing connectivity in the presence of large-scale failures have emerged as a critical research challenge. Traditional studies on improving edge/node connectivity assume that failures occur at random and fail to capture the locality of large-scale failures. Although studies on region-based connectivity can address this limitation, they fail to consider how local failures affect the communication between certain key source-destination (SD) pairs. In this paper, we first extend the definition of region-based connectivity to include SD pairs. Given ℓ failure regions andkSD pairs, we study the problem of shielding edges with minimum cost to improve region-based connectivity between thekSD pairs. Second, we systematically analyze the computational complexity of the problem under different settings of ℓ,kand topologies of failure regions. Third, we design an ILP-based formulation to solve the general problem and propose two polynomial-time algorithms for two special cases based on the matroid technique and the biconnected component decomposition, respectively. Experimental results show that our algorithms are much faster than previously known algorithms.

In the Clustered TSP (CTSP), we are given an edge-weighted graph satisfying the triangle inequality property, and a family of pairwise disjoint vertex groups. The goal is to find a minimum weight tour that includes all vertices, ensuring that the vertices within each group appear consecutively on the tour. The subgroup planning problem (SGPP) is an extension of CTSP by relaxing some triangle inequality requirements on edge weights. CTSP and SGPP have plentiful applications in AI and robotics. In this paper, we design three improved approximation algorithms for SGPP and CTSP. First, we propose a polynomial-time 2.167-approximation algorithm for SGPP, improving the previous ratio of 3 (IJCAI 2017). Second, we give an FPT 2.072-approximation algorithm for SGPP parameterized by the maximum group size, improving the previous ratio of 2.5 (IJCAI 2017). Third, we prove an FPT (β

The #2-SAT and #3-SAT problems involve counting the number of satisfying assignments (also called models) for instances of 2-SAT and 3-SAT, respectively. In 2010, Zhou et al. (https://doi.org/10.1609/aaai.v24i1.7537) proposed an O*(1.1892^m)-time algorithm for #2-SAT and an efficient approach for #3-SAT, where m denotes the number of clauses. In this paper, we show that the weighted versions of #2-SAT and #3-SAT can be solved in O*(1.1082^m) and O*(1.4423^m) time, respectively. These results directly apply to the unweighted cases and achieve substantial improvements over the previous results. These advancements are enabled by the introduction of novel reduction rules, a refined analysis of branching operations, and the application of path decompositions on the primal and dual graphs of the formula.

We present fast algorithms for the general CNF satisfiability problem (SAT) with running-time bound O*({c_d}^n), where c_d is a function of the maximum occurrence d of variables (d can also be the average occurrence when each variable appears at least twice), and n is the number of variables in the input formula. Similar to SAT with bounded clause lengths, SAT with bounded occurrences of variables has also been extensively studied in the literature. Especially, the running-time bounds for small values of d, such as d=3 and d=4, have become bottlenecks for algorithms evaluated by the formula length L and other algorithms. In this paper, we show that SAT can be solved in time O*(1.1238^n) for d=3 and O*(1.2628^n) for d=4, improving the previous results O*(1.1279^n) and O*(1.2721^n) obtained by Wahlström (SAT 2005) nearly 20 years ago. For d>=5, we obtain a running time bound of O*(1.0641^{dn}), implying a bound of O*(1.0641^L) with respect to the formula length L, which is also a slight improvement over the previous bound.

As networks and their inter-connectivity grow and become complex, failures in the networks impact society and industries more than ever. In these networks the notion of connectedness is the key to understanding and reasoning about these failures. Traditional studies in improving edge/node connectivity assume that failures occur at random. However, in many scenarios (such as earthquakes, hurricanes, and human-designed attacks on networks) failures are not random, and most traditional methods do not always work. To address this limitation, we consider region-based connectivity to capture the local nature of failures under the geographical failure model, where failures may happen only on edges in a sub-network (region) and we want to shield some edges in regions to protect the connectivity. There may be several regions and in different regions the failures occur independently. Firstly, we establish the NP-hardness of the problem for regions, answering a question proposed in previous papers. Secondly, we propose a polynomial-time algorithm for the special case of two regions based on the matroid techniques. Furthermore, we design an ILP-based algorithm to solve the problem for regions. Experimental results on random and real networks show that our algorithms are much faster than previously known algorithms.