We study two related problems motivated by molecular biology. Given a graph G and a constant k, does there exist a supergraph G' of G that is a unit interval graph and has clique size at most k? Given a graph G an...
详细信息
We study two related problems motivated by molecular biology. Given a graph G and a constant k, does there exist a supergraph G' of G that is a unit interval graph and has clique size at most k? Given a graph G and a proper k-coloring c of G, does there exist a supergraph G' of G that is properly colored by c and is a unit interval graph? We show that those problems are polynomial for fixed k. On the other hand, we prove that the first problem is equivalent to deciding if the bandwidth of G is at most k - 1. Hence, it is NP-hard and W[t]-hard for all t. We also show that the second problem is W[1]-hard. This implies that for fixed k, both of the problems are unlikely to have an O(n(alpha)) algorithm, where alpha is a constant independent of k. A central tool in our study is a new graph-theoretic parameter closely related to pathwidth. An unexpected useful consequence is the equivalence of this parameter to the bandwidth of the graph.
It is shown that the Precedence Constrained K-Processor Scheduling problem is hard for the parameterized complexity class W[2]. This means that there does not exist a constant c, such that for all fixed K, the Precede...
详细信息
It is shown that the Precedence Constrained K-Processor Scheduling problem is hard for the parameterized complexity class W[2]. This means that there does not exist a constant c, such that for all fixed K, the Precedence Constrained K-Processor Scheduling problem can be solved in 0(n(C)) time, unless an unlikely collapse occurs in the parameterized complexity hierarchy. That is, if the problem can be solved in polynomial time for each fixed K, then it is likely that the degree of the running time polynomial must increase as the number of processors K increases.
For many fixed-parameter problems that are trivially soluable in polynomial time, such as (k-)DOMINATING SET, essentially no better algorithm is presently known than the one which tries all possible solutions. Other p...
详细信息
For many fixed-parameter problems that are trivially soluable in polynomial time, such as (k-)DOMINATING SET, essentially no better algorithm is presently known than the one which tries all possible solutions. Other problems, such as (k-)FEEDBACK VERTEX SET, exhibit fixed-parameter tractability: for each fixed k the problem is soluable in time bounded by a polynomial of degree c, where c is a constant independent of k. We establish the main results of a completeness program which addresses the apparent fixed-parameter intractability of many parameterized problems. In particular, we define a hierarchy of classes of parameterized problems FPT subset of or equal to W[1] subset of or equal to W[2] subset of or equal to ... subset of or equal to W[SAT] subset of or equal to W[P] and identify natural complete problems for W[t] for t greater than or equal to 2. (In other papers we have shown many problems complete for W[1].) DOMINATING SET is shown to be complete for W[2], and thus is not fixed-parameter tractable unless INDEPENDENT SET, CLIQUE, IRREDUNDANT SET, and many other natural problems in W[2] are also fixed-parameter tractable. We also give a compendium of currently known hardness results as an appendix.
We present new min-max relations in digraphs between the number of paths satisfying certain conditions and the order of the corresponding cuts. We define these objects in order to capture, in the context of solving th...
详细信息
We present new min-max relations in digraphs between the number of paths satisfying certain conditions and the order of the corresponding cuts. We define these objects in order to capture, in the context of solving the half-integral linkage problem, the essential properties needed for reaching a large bramble of constant congestion from the terminal set. This strategy has been used ad-hoc in several articles, usually with lengthy technical proofs, and our objective is to abstract it to make it applicable in a simpler and unified way. We provide two proofs of the min-max relations, one consisting in applying Menger’s Theorem on appropriately defined digraphs, and an alternative simpler one using matroids, however with worse polynomial running *** an application, we manage to simplify and improve several results of Edwards et al. [ESA 2017] and of Giannopoulou et al. [SODA 2022] about finding half-integral linkages in digraphs. Concerning the former, besides being simpler, our proof provides an almost optimal bound on the strong connectivity of a digraph for it to be half-integrally feasible under the presence of a large bramble of congestion two (or equivalently, if the directed tree-width is large). Concerning the latter, our proof uses brambles as rerouting objects instead of cylindrical grids, hence yielding much better bounds and being somehow independent of a particular *** hope that our min-max relations will find further applications as, in our opinion, they are simple, robust, and versatile to be easily applicable to different types of routing problems in digraphs.
Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, suc...
详细信息
Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space that is exponential in the decomposition’s width, and there are good reasons to believe that this is necessary. However, it has been shown that in graphs of low treedepth it is possible to design algorithms that achieve polynomial space complexity without requiring worse time complexity than their counterparts working on tree decompositions of bounded width. Here, treedepth is a graph parameter that, intuitively speaking, takes into account both the depth and the width of a tree decomposition of the graph, rather than the width *** by the above, we consider graphs that admit clique expressions with bounded depth and label count, or equivalently, graphs of low shrubdepth. Here, shrubdepth is a bounded-depth analogue of cliquewidth, in the same way as treedepth is a bounded-depth analogue of treewidth. We show that also in this setting, bounding the depth of the decomposition is a deciding factor for improving the space complexity. More precisely, we prove that on n-vertex graphs equipped with a tree-model (a decomposition notion underlying shrubdepth) of depth d and using k labels,•Independent Set and Dominating Set can be solved in time \(2^{\mathcal {O}(dk)}\cdot n^{\mathcal {O}(1)}\) using \(\mathcal {O}(dk\log n)\) space;•Max Cut can be solved in time \(n^{\mathcal {O}(dk)}\) using \(\mathcal {O}(dk\log n)\) *** also establish a lower bound, conditional on a certain assumption about the complexity of Longest Common Subsequence, which shows that at least in the case of Independent Set the exponent of the parametric factor in the time complexity has to grow with d if one wishes to keep the space complexity polynomial.
Checking whether a system of linear equations is consistent is a basic computational problem with ubiquitous applications. When dealing with inconsistent systems, one may seek an assignment that minimises the number o...
详细信息
Checking whether a system of linear equations is consistent is a basic computational problem with ubiquitous applications. When dealing with inconsistent systems, one may seek an assignment that minimises the number of unsatisfied equations. This problem is NP-hard and UGC-hard to approximate within any constant even for two-variable equations over the two-element field. We study this problem from the point of view of parameterized complexity, with the parameter being the number of unsatisfied equations. We consider equations defined over a family of commutative domains (i.e. rings without zero divisors) with a particular Helly property. This set contains, for instance, finite and infinite fields, the ring of integers, and univariate polynomial rings with coefficients from a field; more generally, it contains the important class of Prüfer domains. We show that if every equation contains at most two variables, the problem is fixed-parameter tractable. This generalises many eminent graph separation problems such as Bipartization, Multiway Cut and Multicut parameterized by the size of the cutset. To complement this, we show that the problem is W[1]-hard when three or more variables are allowed in an equation, as well as for many commutative rings that are not covered by our fpt result. On the technical side, we introduce the notion of important balanced subgraphs, generalising the important separators of Marx [Theoretical Computer Science, 351:3, 2006] to the setting of biased graphs. Furthermore, we use recent results on parameterized MinCSP [Kim et al., SODA-2021] to efficiently solve a generalisation of Multicut with disjunctive cut requests.
暂无评论