The Restricted Subset Feedback Vertex Set problem (R-SFVS) takes a graph G = (V, E), a terminal set T subset of V, and an integer k as the input. The task is to determine whether there exists a subset S subset of V \ ...
详细信息
ISBN:
(纸本)9783031203497;9783031203503
The Restricted Subset Feedback Vertex Set problem (R-SFVS) takes a graph G = (V, E), a terminal set T subset of V, and an integer k as the input. The task is to determine whether there exists a subset S subset of V \ T of at most k vertices, after deleting which no terminal in T is contained in a cycle in the remaining graph. R-SFVS is NP-complete even when the input graph is restricted to chordal graphs. In this paper, we show that R-SFVS in chordal graphs can be solved in time O(1.1550 vertical bar V vertical bar), significantly improving all the previous results. As a by-product, we prove that the Maximum Independent Set problem parameterized by the edge clique cover number is fixed-parameter tractable. Furthermore, by using a simple reduction from R-SFVS to Vertex Cover, we obtain a 1.2738(k)vertical bar V vertical bar(O(1))-time parameterized algorithm and an O(k(2))-kernel for R-SFVS in chordal graphs.
In this paper, we address three related problems. One is the enumeration of all the maximal edge induced chain subgraphs of a bipartite graph, for which we provide a polynomial delay algorithm. We give bounds on the n...
详细信息
ISBN:
(纸本)9783319445434;9783319445427
In this paper, we address three related problems. One is the enumeration of all the maximal edge induced chain subgraphs of a bipartite graph, for which we provide a polynomial delay algorithm. We give bounds on the number of maximal chain subgraphs for a bipartite graph and use them to establish the input-sensitive complexity of the enumeration problem. The second problem we treat is the one of finding the minimum number of chain subgraphs needed to cover all the edges a bipartite graph. For this we provide an exactexponential algorithm with a non trivial complexity. Finally, we approach the problem of enumerating all minimal chain subgraph covers of a bipartite graph and show that it can be solved in quasi-polynomial time.
This thesis summarizes the author's PhD research works on the design of exact al- gorithms that provide a worst-case (time or space) guarantee for N P-hard scheduling problems. Both theoretical and practical aspec...
详细信息
This thesis summarizes the author's PhD research works on the design of exact al- gorithms that provide a worst-case (time or space) guarantee for N P-hard scheduling problems. Both theoretical and practical aspects are considered with three main results reported. The first one is about a Dynamic Programming algorithm which solves the F 3||C max problem in O ∗ (3 n ) time and space. The algorithm is easily generalized to other flowshop problems including F 2||f and F 3||f, and single machine scheduling problems like 1|r i |f, with f ∈ {f max, f i }. The second contribution is about a search tree method called Branch & Merge which solves the 1|| P T i problem with the time complexity converging to O ∗ (2 n ) and in polyno- mial space. The work is based on the observation that many identical subproblems appear during the solution of the input problem. An operation called merge is then derived, which merges all identical nodes to one whenever possible and hence yields a better complexity. Our third contributionaims to improve the practical efficiency of exact search tree algo- rithms solving scheduling problems. First we realized that a better way to implement the idea of Branch & Merge is to use a technique called Memorization. By the finding of a new algorithmic paradox and the implementation of a memory cleaning strategy, the method succeeded to solve instances with 300 more jobs with respect to the state-of-the-art algo- rithm for the 1|| P T i problem. Then the treatment is extended to another three problems 1|r i | P C i, 1| ˜ d i | P w i C i and F 2|| P C i previously addressed by T'kindt et al. (2004). The results of the four problems all together show the power of the Memorization paradigm when applied on sequencing problems. We name it Branch & Memorize to promote a systematic consideration of Memorization as an essential building block in branching algo- rithms like Branch & Bound. The method can surely also be used to solve other problems, which are not nec
We present singly-exponential quantum algorithms for the One-Sided Crossing Minimization (OSCM) problem. We show that OSCM can be viewed as a set problem amenable for exactalgorithms with a quantum speedup with respe...
详细信息
In the 1970s, Lovasz built a bridge between graphs and alternating matrix spaces, in the context of perfect matchings [Proceedings of FCT, 1979, pp. 565-574]. A similar connection between bipartite graphs and matrix s...
详细信息
In the 1970s, Lovasz built a bridge between graphs and alternating matrix spaces, in the context of perfect matchings [Proceedings of FCT, 1979, pp. 565-574]. A similar connection between bipartite graphs and matrix spaces plays a key role in the recent resolutions of the noncommutative rank problem [A. Garg et al., Proceedings of FOCS, 2016, pp. 109-117;G. Ivanyos, Y. Qiao, and K. V. Subrahmanyam, Comput. Complexity, 26 (2017), pp. 717-763]. In this paper, we lay the foundation for another bridge between graphs and alternating matrix spaces, in the context of independent sets and vertex colorings. The corresponding structures in alternating matrix spaces are isotropic spaces and isotropic decompositions, both useful structures in group theory and manifold theory. We first show that the maximum independent set problem and the vertex c-coloring problem reduce to the maximum isotropic space problem and the isotropic c-decomposition problem, respectively. Next, we show that several topics and results about independent sets and vertex colorings have natural correspondences for isotropic spaces and decompositions. These include algorithmic problems, such as the maximum independent set problem for bipartite graphs, and exactexponential-time algorithms for the chromatic number, as well as mathematical questions, such as the number of maximal independent sets, and the relation between the maximum degree and the chromatic number. These connections lead to new interactions between graph theory and algebra. Some results have concrete applications to group theory and manifold theory, and we initiate a variant of these structures in the context of quantum information theory. Finally, we propose several open questions for further exploration.
The RESTRICTED SUBSET FEEDBACK VERTEX SET problem (R-SFVS) takes a graph G = (V, E), a terminal set T C V, an integer k as the input. The task is to determine whether there exists a subset S C V ⧵ T of at most k verti...
详细信息
The RESTRICTED SUBSET FEEDBACK VERTEX SET problem (R-SFVS) takes a graph G = (V, E), a terminal set T C V, an integer k as the input. The task is to determine whether there exists a subset S C V ⧵ T of at most k vertices, after deleting which no terminal in T is contained in a cycle in the remaining graph. R-SFVS is NP-complete even when the input graph is restricted to split graphs. In this paper, we mainly show that R-SFVS in chordal , split graphs can be solved in 0(1.1550|V|) time and exponential space or in 0(1.1605|V|) time and polynomial space, significantly improving all previous results. As a by-product, we show that the MAXIMUM INDEPENDENT SET problem parameterized by the edge clique cover number is fixed-parameter tractable. Furthermore, by using a simple reduction from R-SFVS to VERTEX COVER, we obtain an 0*(1.2738k)-time parameterized algorithm and a tight 0(k2)-kernel for R-SFVS in chordal and split graphs.
Cytoplasmic incompatibility (CI) relates to the manipulation by the parasiteWolbachiaof its host reproduction. Despite its widespread occurrence, the molecular basis of CI remains unclear and theoretical models have b...
详细信息
Cytoplasmic incompatibility (CI) relates to the manipulation by the parasiteWolbachiaof its host reproduction. Despite its widespread occurrence, the molecular basis of CI remains unclear and theoretical models have been proposed to understand the phenomenon. We consider in this paper the quantitative Lock-Key model which currently represents a good hypothesis that is consistent with the data available. CI is in this case modelled as the problem of covering the edges of a bipartite graph with the minimum number of chain subgraphs. This problem is already known to be NP-hard, and we provide an exponential algorithm with a non trivial complexity. It is frequent that depending on the dataset, there may be many optimal solutions which can be biologically quite different among them. To rely on a single optimal solution may therefore be problematic. To this purpose, we address the problem of enumerating (listing) all minimal chain subgraph covers of a bipartite graph and show that it can be solved in quasi-polynomial time. Interestingly, in order to solve the above problems, we considered also the problem of enumerating all the maximal chain subgraphs of a bipartite graph and improved on the current results in the literature for the latter. Finally, to demonstrate the usefulness of our methods we show an application on a real dataset.
暂无评论