Explore the vast range of titles available.

In this paper, we focus on analyzing the 3-path vertex cover (3PVC) problem in a number of graph classes. Let G = ( V , E ) be a simple graph. A set C ⊆ V is called a k -path vertex cover of G , if each path of order k in G , contains at least one vertex from C . In the k -path vertex cover problem, we are given a graph G , and asked to find a k -path vertex cover of minimum size. For k = 3 , the problem becomes the well-known 3PVC problem. A problem that is closely related to the 3PVC problem is the dissociation set (DS) problem. Given a graph G = ( V , E ) , a dissociation set is any D ⊆ V , such that the vertex-induced subgraph G ′ = ( D , E ′ ) consists of vertices having degree 0 or 1. In the dissociation set problem, we are required to find a dissociation set of maximum cardinality. Both these problems have also been studied extensively as per the literature. In this paper, we focus on pipartite (planar and bipartite) graphs for the most part. We first show that the 3PVC problem is NP-hard , even in pipartite graphs having maximum degree 4. We then show that the 3PVC problem on this class of graphs admits a linear time 8 5 -approximation algorithm. Next, we show that the 3PVC problem is APX-complete in bipartite graphs having maximum degree 4 and cubic graphs. Finally, we discuss an elegant and alternative proof for the APX-completeness of the vertex cover problem in cubic graphs and establish lower bounds for the 3PVC problem in special graph classes. It is important to note that our work is the first of its kind to establish APX-completeness of the 3PVC problem in graphs.

In this paper, we discuss algorithms for the problem of finding read-once resolution refutations of unsatisfiable 2CNF formulas within the resolution refutation system. Broadly, a read-once resolution refutation is one in which each constraint (input or derived) is used at most once. Read-once resolution refutations have been widely studied in the literature for a number of constraint system-refutation system pairs. For instance, read-once resolution has been analyzed for boolean formulas in conjunctive normal form (CNF) and read-once cutting planes have been analyzed for polyhedral systems. By definition, read-once refutations are compact, and hence valuable in applications that place a premium on visualization. The satisfiability problem (SAT) is concerned with finding a satisfying assignment for a boolean formula in CNF. While SAT is NP-complete in general, there exist some interesting subclasses of CNF formulas, for which it is decidable in polynomial time. One such subclass is the class of 2CNF formulas, i.e., CNF formulas in which each clause has at most two literals. The existence of efficient algorithms for satisfiability checking in 2CNF formulas (2SAT), makes this class useful from the perspective of modeling selected logic programs. The work in this paper is concerned with the read-once refutability problem (under resolution) in this subclass. Although 2SAT is decidable in polynomial time, the problem of finding a read-once resolution refutation of an unsatisfiable 2CNF formula is NP-complete . We design non-trivial, parameterized and exact exponential algorithms for this problem. Additionally, we study the computational complexity of finding a shortest read-once resolution refutation of a 2CNF formula.

In this paper, we examine variants of the partial vertex cover problem from the perspective of parameterized algorithms. Recall that in the classical vertex cover problem (VC), we are given a graph G=⟨V,E⟩ and a number k and asked if we can cover all of the edges in E, using at most k vertices from V. The partial vertex cover problem (PVC) is a more general version of the VC problem in which we are given an additional parameter k′. We then ask the question of whether at least k′ of the edges in E can be covered using at most k vertices from V. Note that the VC problem is a special case of the PVC problem when k′=|E|. In this paper, we study the weighted generalizations of the PVC problem. This is called the weighted partial vertex cover problem (WPVC). In the WPVC problem, we are given two parameters R and L, associated respectively with the vertex set V and edge set E of the graph G respectively. Additionally, we are given non-negative integral weight functions for the vertices and the edges. The goal then is to cover edges of total weight at least L, using vertices of total weight at most R. This paper studies several variants of the PVC and WPVC problems and establishes new results from the perspective of fixed-parameter tractability and W[1]-hardness. We also introduce a new problem called the partial vertex cover with matching constraints and show that it is Fixed-Parameter Tractable (FPT) for a certain class of graphs. Finally, we show that the WPVC problem is APX-complete for bipartite graphs.

Database migration is an important problem faced by companies dealing with big data. Not only is migration a costly procedure, but it also involves serious security risks as well. For some institutions, the primary focus is on reducing the cost of the migration operation, which manifests itself in application testing. For other institutions, minimizing security risks is the most important goal, especially if the data involved is of a sensitive nature. In the literature, the database migration problem has been studied from a test cost minimization perspective. In this paper, we focus on an orthogonal measure, i.e., security risk minimization. We associate security with the number of shifts needed to complete the migration task. Ideally, we want to complete the migration in as few shifts as possible, so that the risk of data exposure is minimized. In this paper, we provide a formal framework for studying the database migration problem from the perspective of security risk minimization (shift minimization) and establish the computational complexities of several models in the same. For the NP-hard models, we develop memetic algorithms that produce solutions that are within 10% and 7% of the optimal in 95% of the instances under 8 and 82 seconds, respectively.

In this paper, we study the efficacy of several mathematical programming formulations for the single-source shortest path problem, the negative cost cycle detection problem, and the shortest negative cost cycle problem in arc-dependent networks. In an arc-dependent network, the cost of an arc a depends upon the arc preceding a. These networks differ from traditional networks in which the cost associated with an arc is a fixed constant and part of the input. Arc-dependent networks are useful for modeling a number of real-world problems, such as the turn-penalty shortest path problem, which cannot be captured in the traditional network setting. We present new integer and non-linear programming formulations for each problem. We also perform the first known empirical study for arc-dependent networks to contrast the execution times of the two formulations on a set of graphs with varying families and sizes. Our experiments indicate that although non-linear programming formulations are more compact, integer programming formulations are more efficient for the problems studied in this paper. Additionally, we introduce a number of cuts for each integer programming formulation and examine their effectiveness.

In this paper, we investigate the properties of cutting plane based refutations for a class of integer programs called Horn constraint systems (HCSs). Briefly, a system of linear inequalities A ⋅ x ≥ b is called a Horn constraint system, if each entry in A belongs to the set {0,1,− 1} and furthermore, there is at most one positive entry per row. Our focus is on deriving refutations, i.e. proofs of unsatisfiability, of such programs using cutting planes as a proof system. We also look at several properties of these refutations. HCSs can be considered a more general form of Horn formulas, i.e., CNF formulas with at most one positive literal per clause. Cutting plane calculus (CP) is a well-known calculus for deciding the unsatisfiability of propositional CNF formulas and integer programs. Usually, CP consists of a pair of inference rules. These are called the addition rule (ADD) and the division rule (DIV). In this paper, we show that cutting plane calculus is still complete for HCSs when every intermediate constraint is required to be Horn. We also investigate the lengths of cutting plane proofs for Horn constraint systems.

In this paper, we investigate refutability in Difference Constraint Systems (DCS) under the Unit Read-Once Refutation (UROR) system. A difference constraint is a linear relationship of the form: xi-xj≤bij and a DCS is a conjunction of such constraints. In the UROR refutation system, each constraint can be used by at most one inference. Additionally, each inference has to use at least one one-variable (absolute) constraint. Note that an unsatisfiable difference constraint system may not have a UROR. Thus, the UROR refutation system is incomplete for DCSs. The UROR refutation system is useful for proving that the infeasibility of a DCS is caused by the current variable domains. These domains are determined by the absolute constraints in the system. Thus, the UROR refutations of a DCS depend on these variable domains. This is in contrast to unrestricted refutations which do not need to depend on these domain constraints. Investigating weak (incomplete) refutation systems leads to a better understanding of the inference rules required for establishing contradictions in the given constraint system. Thus, this study is well-motivated. Likewise, difference constraint systems arise in a number of application domains such as program verification and scheduling. It follows that efficient refutation systems are of paramount interest. In this paper, we show that problem of checking if a DCS has a unit read-once refutation is NP-complete. Additionally, we provide parameterized and exact exponential algorithms for solving this problem. Finally, we show that the problem of finding the length of the shortest unit read-once refutation is NPO PB-complete.

Kidney transplantation is vital for treating end-stage renal disease, impacting roughly one in a thousand Europeans. The search for a suitable deceased donor often leads to prolonged and uncertain wait times, making living donor transplants a viable alternative. However, approximately 40% of living donors are incompatible with their intended recipients. Therefore, many countries have established kidney exchange programs, allowing patients with incompatible donors to participate in “swap” arrangements, exchanging donors with other patients in similar situations. Several variants of the vertex-disjoint cycle cover problem model the above problem, which deals with different aspects of kidney exchange as required. This paper discusses several specific vertex-disjoint cycle cover variants and deals with finding the exact solution. We employ the dataless neural networks framework to establish single differentiable functions for each variant. Recent research highlights the framework’s effectiveness in representing several combinatorial optimization problems. Inspired by these findings, we propose customized dataless neural networks for vertex-disjoint cycle cover variants. We derive a differentiable function for each variant and prove that the function will attain its minimum value if an exact solution is found for the corresponding problem variant. We also provide proof of the correctness of our approach.

Magnesium (Mg) has become a focus in the transportation industry due to its potential in reducing fuel consumption and gas emissions while improving recyclability. Mg alloys are also known for their low neutron absorption, good resistant of carbon dioxide as well as thermal conductivity which makes them suitable for use in industrial equipment for nuclear energy. there has been an increasing interest in the research and development of Mg alloys. These are the lightest of all metallic structural materials and are approximately 33% lighter than aluminium (Al) and 75% lighter than ferrous (Fe) alloys and have excellent specific mechanical properties. In this work, FSW of AZ31B Alloy was examined at the various rotational speeds of 900 -1440 rpm, with fixed welding speed of 40mm/min and 2° tool tilt angle using an HSS tool. The mechanical properties were compared for the different rotational speeds. The quality of FSW joints is dependent on input value of heat and material flow rate, which are prejudiced by process parameters., higher rotation speeds may cause abnormal stirring, resulting in a tunnel defect at the weld nugget due to increased strain rate and turbulence.