Search

In this paper, we discuss the problems of finding minimum stopping sets and trapping sets in Tanner graphs, using integer linear programming. These problems are important for establishing reliable communication across noisy channels. Indeed, stopping sets and trapping sets correspond to combinatorial structures in information-theoretic codes, which lead to errors in decoding once a message is received. In particular, these sets correspond to variables that are not eventually corrected by the decoder, thus causing failures in decoding when using iterative algorithms. We present integer linear programs (ILPs) for finding stopping sets and several trapping set variants. Furthermore, we prove that two of these trapping set problem variants are NP-hard for the first time. Additionally, we analyze these variants from the parameterized perspective. Finally, we model stopping set and trapping set problems as Integer Linear Programs (ILPs). The effectiveness of our approach is demonstrated by finding stopping sets of size up to 48 in the (4896 , 2474) Margulis code. This compares favorably to the current state-of-the-art, which finds stopping sets of size up to 26. For the trapping set problems, we show for which cases an ILP produces solutions efficiently and for which cases it performs poorly. The proposed approach is applicable to codes represented by regular and irregular graphs alike.1 [ABSTRACT FROM AUTHOR]

In this paper, we study two closely related problems on bipartite graphs, viz., the partial vertex cover problem and the budgeted maximum coverage problem. Both these problems arise in a number of different application domains, including, but not limited to, computer security and transportation logistics. It is well known that the vertex cover problem is solvable in polynomial time on bipartite graphs. However, the computational complexity of the partial vertex cover problem on bipartite graphs was open, thus far. In this paper, we establish that the partial vertex cover problem is NP-hard, even on bipartite graphs. Our result also establishes that the closely related budgeted maximum coverage problem is NP-hard on bipartite graphs. For the latter problem, we present an 8/9 -approximation algorithm. Our approximation guarantee matches and resolves the integrality gap of the natural linear programming relaxation for this problem and improves upon a recent 4/5-approximation algorithm for the same problem. [ABSTRACT FROM AUTHOR]

A Quantified Linear Implication (QLI) is an inclusion query over two polyhedral sets, with a quantifier string that specifies which variables are existentially quantified and which are universally quantified. Equivalently, it can be viewed as a quantified implication of two systems of linear inequalities. In this paper, we provide a 2-person game semantics for the QLI problem, which allows us to explore the computational complexities of several of its classes. More specifically, we prove that the decision problem for QLIs with an arbitrary number of quantifier alternations is PSPACE-hard. Furthermore, we explore the computational complexities of several classes of 0, 1, and 2-quantifier alternation QLIs. We observed that some classes are decidable in polynomial time, some are NP-complete, some are coNP-hard and some are $\boldsymbol{\Pi}_{\textbf 2}^{\textbf P}$ -hard. We also establish the hardness of QLIs with 2 or more quantifier alternations with respect to the first quantifier in the quantifier string and the number of quantifier alternations. All the proofs that we provide for polynomially solvable problems are constructive, i.e., polynomial-time decision algorithms are devised that utilize well-known procedures. QLIs can be utilized as powerful modelling tools for real-life applications. Such applications include reactive systems, real-time schedulers, and static program analyzers. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we design and analyze a simple, greedy algorithm for checking the linear and integer feasibility of a class of linear programs called Horn programs. This algorithm, which we term the “Lifting Algorithm”, runs in time on a Horn system (Horn program) with constraints and variables. The Lifting Algorithm is a variant of the Stressing Algorithm which was proposed for checking the feasibility of Difference Constraint systems. Inasmuch as Horn constraints subsume difference constraints, and all known algorithms for the problem of checking feasibility of Difference Constraint Systems run in time , the running time of our algorithm is only a factor worse than the best known running time for checking the feasibility of Difference Constraint Systems. Horn programs arise in a number of application areas including econometrics and program verification; consequently, their study is well-motivated. An important feature of our algorithm is that it uses only one operator, viz., addition. We also show that our algorithm can identify the linear and lattice point feasibility of Extended Horn Systems in time. [Copyright &y& Elsevier]

The article presents a study on chain programming over difference constraints. Chain programming is a restricted form of linear programming, and a chain program is characterized by a total ordering on the program variables. The study has shown that for difference constraint systems, the total ordering of the program variables results in an elegant divide and conquer algorithm for the problem of feasibility testing.

Abstract: In this paper, we explore the computational complexity of the conjunctive fragment of the first-order theory of linear arithmetic. Quantified propositional formulas of linear inequalities with quantifier alternations are log-space complete in or depending on the initial quantifier. We show that when we restrict ourselves to quantified conjunctions of linear inequalities, i.e., quantified linear systems, the complexity classes collapse to polynomial time. In other words, the presence of universal quantifiers does not alter the complexity of the linear programming problem, which is known to be in . Our result reinforces the importance of sentence formats from the perspective of computational complexity. [Copyright &y& Elsevier]