Let G = (V, E) be an unweighted simple graph. A distance-d independent set is a subset I subset of V such that dist(u, v) >= d for any two vertices u, v in I, where dist(u, v) is the distance between u and v. Then,...
详细信息
Let G = (V, E) be an unweighted simple graph. A distance-d independent set is a subset I subset of V such that dist(u, v) >= d for any two vertices u, v in I, where dist(u, v) is the distance between u and v. Then, Maximum Distance-d Independent Set problem requires to compute the size of a distance-d independent set with the maximum number of vertices. Even for a fixed integer d >= 3, this problem is NP-hard. In this paper, we design an exact exponential algorithm that calculates the size of a maximum distance-3 independent set in O(1.4143(n)) time.
We introduce a variant of the graph coloring problem, which we denote as BUDGETED COLORING PROBLEM (BCP). Given a graph G, an integer c and an ordered list of integers (b1, b2, ... , bc), BCP asks whether there exists...
详细信息
We introduce a variant of the graph coloring problem, which we denote as BUDGETED COLORING PROBLEM (BCP). Given a graph G, an integer c and an ordered list of integers (b1, b2, ... , bc), BCP asks whether there exists a proper coloring of G where the i-th color is used to color at most bi many vertices. This problem generalizes two well-studied graph coloring problems, BOUNDED COLORING PROBLEM (BOCP) and EQUITABLE COLORING PROBLEM (ECP) and as in the case of other coloring problems, the BCP is NP-hard even for constant values of c. So we study BCP under the paradigm of parameterized complexity, particularly with respect to (structural) parameters that specify how far (the deletion distance) the input graph is from a tractable graph *** dot We show that BCP is FPT (fixed-parameter tractable) parameterized by the vertex cover size. This generalizes a similar result for ECP and immediately extends to the BoCP, which was earlier not *** dot We show that BCP is polynomial time solvable for cluster graphs generalizing a similar result for ECP. However, we show that BCP is FPT, but unlikely to have polynomial kernel, when parameterized by the deletion distance to clique, contrasting the linear kernel for ECP for the same *** dot While the BoCP is known to be polynomial time solvable on split graphs, we show that BCP is NP-hard on split graphs. As BoCP is hard on bipartite graphs when c > 3, the result follows for BCP as well. We provide a dichotomy result by showing that BCP is polynomial time solvable on bipartite graphs when c = 2. We also show that BCP is NP-hard on co-cluster graphs, contrasting the polynomial time algorithm for ECP and *** we present an O*(2|V(G)|) algorithm for the BCP, generalizing the known algorithm with a similar bound for the standard chromatic number.(c) 2022 Elsevier B.V. All rights reserved.
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...
详细信息
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) (c) 2022 Elsevier B.V. All rights reserved.
This paper proposes an exact exponential algorithm for the single machine total tardiness problem. It exploits the structure of a basic branch-and-reduce framework based on the well known Lawler's decomposition pr...
详细信息
This paper proposes an exact exponential algorithm for the single machine total tardiness problem. It exploits the structure of a basic branch-and-reduce framework based on the well known Lawler's decomposition property that solves the problem with worst-case complexity in time O*(3(n)) and polynomial space. The proposed algorithm, called branch and-merge, is an improvement of the branch-and-reduce technique with the embedding of a node merging operation. Its time complexity converges to O*(2(n)) keeping the space complexity polynomial. This improves upon the best-known complexity result for this problem provided by dynamic programming across the subsets with O*(2(n)) worst-case time and space complexity. The branch-and-merge technique is likely to be generalized to other sequencing problems with similar decomposition properties. (C) 2018 Elsevier B.V. All rights reserved.
We introduce a variant of the graph coloring problem, which we denote as Budgeted Coloring Problem (BCP). Given a graph G, an integer c and an ordered list of integers {b(1), b(2),..., b(c)}, BCP asks whether there ex...
详细信息
ISBN:
(纸本)9783030967307;9783030967314
We introduce a variant of the graph coloring problem, which we denote as Budgeted Coloring Problem (BCP). Given a graph G, an integer c and an ordered list of integers {b(1), b(2),..., b(c)}, BCP asks whether there exists a proper coloring of G where the i-th color is used to color at most b(i) many vertices. This problem generalizes two well-studied graph coloring problems, BOUNDED COLORING PROBLEM (BoCP) and EQUITABLE COLORING PROBLEM (ECP), and as in the case of other coloring problems, BCP is NP-hard even for constant values of c. So we study BCP under the paradigm of parameterized complexity, particularly with respect to (structural) parameters that specify how far (the deletion distance) the input graph is from a tractable graph class. - We show that BCP is FPT (fixed-parameter tractable) parameterized by the vertex cover size. This generalizes a similar result for ECP and immediately extends to the BoCP, which was earlier not known. - We show that BCP is polynomial time solvable for cluster graphs generalizing a similar result for ECP. However, we show that BCP is FPT, but unlikely to have polynomial kernel, when parameterized by the deletion distance to clique, contrasting the linear kernel for ECP for the same parameter. - While the BoCP is known to be polynomial time solvable on split graphs, we show that BCP is NP-hard on split graphs. We also show that BCP is NP-hard on co-cluster graphs, contrasting the polynomial time algorithm for ECP and BoCP. Finally we present an O*(2(|V(G)|)) algorithm for the BCP, generalizing the known algorithm with a similar bound for the standard chromatic number.
The circuit satisfiability problem has been intensively studied since Ryan Williams showed a connection between the problem and lower bounds for circuit complexity. In this letter, we present a #SAT algorithm for sync...
详细信息
The circuit satisfiability problem has been intensively studied since Ryan Williams showed a connection between the problem and lower bounds for circuit complexity. In this letter, we present a #SAT algorithm for synchronous Boolean circuits of n inputs and s gates in time 2(n(1 - 1/2O(s/n))) if s = o(n log n).
For every connected graph G, a subgraph H of G is isometric if the distance between any two vertices in H is the same in H as in G. A distance-preserving elimination ordering of G is a total ordering of its vertex-set...
详细信息
For every connected graph G, a subgraph H of G is isometric if the distance between any two vertices in H is the same in H as in G. A distance-preserving elimination ordering of G is a total ordering of its vertex-set V (G), denoted (v(1), v(2),....v(n)), such that any subgraph G(i)= G \ (v(1), v(2),, v(i)) with 1 <= i < n is isometric. This kind of ordering has been introduced by Chepoi in his study on weakly modular graphs (Chepoi, 1998). We prove that it is NP complete to decide whether such ordering exists for a given graph even if it has diameter at most 2. Then, we prove on the positive side that the problem of computing a distance preserving ordering when there exists one is fixed-parameter-tractable in the treewidth. Lastly, we describe a heuristic in order to compute a distance-preserving ordering when there exists one that we compare to an exactexponential time algorithm and to an ILP formulation for the problem. (C) 2018 Elsevier B.V. All rights reserved.
The family of stable matching problems have been well-studied across a wide field of research areas, including economics, mathematics and computer science. In general, an instance of a stable matching problem is given...
详细信息
The family of stable matching problems have been well-studied across a wide field of research areas, including economics, mathematics and computer science. In general, an instance of a stable matching problem is given by a set of participants who have expressed their preferences of each other, and asks to find a "stable" matching, that is, a pairing of the participants such that no unpaired participants prefer each other to their assigned partners. In the case of the Stable Roommates Problem (SR), it is known that given an even number n of participants, there might not exist a stable matching that pairs all of the participants, but there exist efficient algorithms to determine if this is possible or not, and if it is possible, produce such a matching. Common extensions of SR allow for the participants' preference lists to be incomplete, or include indifference. Allowing indifference in turn, gives rise to different possible definitions of stability, super, strong, and weak stability. While instances asking for super and strongly stable matching can be efficiently solved even if preference lists are incomplete, the case of weak stability is NP-complete. We examine a restricted case of indifference, introducing the concept of unranked entries. For this type of instances, we show that the problem of finding a weakly stable matching remains NP-complete even if each participant has a complete preference list with at most two unranked entries, or is herself unranked for up to three other participants. On the other hand, for instances where there are m acceptable pairs and there are in total k unranked entries in all of the participants' preference lists, we propose an O(2(k)n(2))-time and polynomial space algorithm that finds a stable matching, or determines that none exists in the given instance.
We give a new general approach for designing exactexponential-time algorithms for subset problems. In a subset problem the input implicitly describes a family of sets over a universe of size n and the task is to dete...
详细信息
We give a new general approach for designing exactexponential-time algorithms for subset problems. In a subset problem the input implicitly describes a family of sets over a universe of size n and the task is to determine whether the family contains at least one set. A typical example of a subset problem is Weighted d-SAT. Here, the input is a CNF-formula with clauses of size at most d, and an integer W. The universe is the set of variables and the variables have integer weights. The family contains all the subsets S of variables such that the total weight of the variables in S does not exceed W and setting the variables in S to 1 and the remaining variables to 0 satisfies the formula. Our approach is based on "monotone local search," where the goal is to extend a partial solution to a solution by adding as few elements as possible. More formally, in the extension problem, we are also given as input a subset X of the universe and an integer k. The task is to determine whether one can add at most k elements to X to obtain a set in the (implicitly defined) family. Our main result is that a c(k)n(O(1)) time algorithm for the extension problem immediately yields a randomized algorithm for finding a solution of any size with running time O((2 - 1/c)(n)). In many cases, the extension problem can be reduced to simply finding a solution of size at most k. Furthermore, efficient algorithms for finding small solutions have been extensively studied in the field of parameterized algorithms. Directly applying these algorithms, our theorem yields in one stroke significant improvements over the best known exponential-time algorithms for several well-studied problems, including d-HITTING SET, FEEDBACK VERTEX SET, NODE UNIQE LABEL COVER, and WEIGHTED d-SAT. Our results demonstrate an interesting and very concrete connection between parameterized algorithms and exactexponential-time algorithms. We also show how to derandomize our algorithms at the cost of a subexponential multiplic
The paper presents a 1.692(n)n(O(1))-time polynomial-space algorithm for the traveling salesman problem in an n-vertex edge-weighted graph with maximum degree 4, which improves the previous results of the 1.890(n)n(O(...
详细信息
The paper presents a 1.692(n)n(O(1))-time polynomial-space algorithm for the traveling salesman problem in an n-vertex edge-weighted graph with maximum degree 4, which improves the previous results of the 1.890(n)n(O(1))-time polynomial-space algorithm by Eppstein and the 1.733(n)n(O(1))-time exponential-space algorithm by Gebauer.
暂无评论