ترغب بنشر مسار تعليمي؟ اضغط هنا

Parameterized Complexity of Two-Interval Pattern Problem

60   0   0.0 ( 0 )
 نشر من قبل Saeed Mehrabi
 تاريخ النشر 2020
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

A emph{2-interval} is the union of two disjoint intervals on the real line. Two 2-intervals $D_1$ and $D_2$ are emph{disjoint} if their intersection is empty (i.e., no interval of $D_1$ intersects any interval of $D_2$). There can be three different relations between two disjoint 2-intervals; namely, preceding ($<$), nested ($sqsubset$) and crossing ($between$). Two 2-intervals $D_1$ and $D_2$ are called emph{$R$-comparable} for some $Rin{<,sqsubset,between}$, if either $D_1RD_2$ or $D_2RD_1$. A set $mathcal{D}$ of disjoint 2-intervals is $mathcal{R}$-comparable, for some $mathcal{R}subseteq{<,sqsubset,between}$ and $mathcal{R} eqemptyset$, if every pair of 2-intervals in $mathcal{R}$ are $R$-comparable for some $Rinmathcal{R}$. Given a set of 2-intervals and some $mathcal{R}subseteq{<,sqsubset,between}$, the objective of the emph{2-interval pattern problem} is to find a largest subset of 2-intervals that is $mathcal{R}$-comparable. The 2-interval pattern problem is known to be $W[1]$-hard when $|mathcal{R}|=3$ and $NP$-hard when $|mathcal{R}|=2$ (except for $mathcal{R}={<,sqsubset}$, which is solvable in quadratic time). In this paper, we fully settle the parameterized complexity of the problem by showing it to be $W[1]$-hard for both $mathcal{R}={sqsubset,between}$ and $mathcal{R}={<,between}$ (when parameterized by the size of an optimal solution); this answers an open question posed by Vialette [Encyclopedia of Algorithms, 2008].



قيم البحث

اقرأ أيضاً

The problem of publishing personal data without giving up privacy is becoming increasingly important. An interesting formalization that has been recently proposed is the $k$-anonymity. This approach requires that the rows of a table are partitioned i n clusters of size at least $k$ and that all the rows in a cluster become the same tuple, after the suppression of some entries. The natural optimization problem, where the goal is to minimize the number of suppressed entries, is known to be APX-hard even when the records values are over a binary alphabet and $k=3$, and when the records have length at most 8 and $k=4$ . In this paper we study how the complexity of the problem is influenced by different parameters. In this paper we follow this direction of research, first showing that the problem is W[1]-hard when parameterized by the size of the solution (and the value $k$). Then we exhibit a fixed parameter algorithm, when the problem is parameterized by the size of the alphabet and the number of columns. Finally, we investigate the computational (and approximation) complexity of the $k$-anonymity problem, when restricting the instance to records having length bounded by 3 and $k=3$. We show that such a restriction is APX-hard.
142 - Minghui Jiang , Yong Zhang 2011
We show that the problem k-Dominating Set and its several variants including k-Connected Dominating Set, k-Independent Dominating Set, and k-Dominating Clique, when parameterized by the solution size k, are W[1]-hard in either multiple-interval graph s or their complements or both. On the other hand, we show that these problems belong to W[1] when restricted to multiple-interval graphs and their complements. This answers an open question of Fellows et al. In sharp contrast, we show that d-Distance k-Dominating Set for d >= 2 is W[2]-complete in multiple-interval graphs and their complements. We also show that k-Perfect Code and d-Distance k-Perfect Code for d >= 2 are W[1]-complete even in unit 2-track interval graphs. In addition, we present various new results on the parameterized complexities of k-Vertex Clique Partition and k-Separating Vertices in multiple-interval graphs and their complements, and present a very simple alternative proof of the W[1]-hardness of k-Irredundant Set in general graphs.
The classic Ham-Sandwich theorem states that for any $d$ measurable sets in $mathbb{R}^d$, there is a hyperplane that bisects them simultaneously. An extension by Barany, Hubard, and Jeronimo [DCG 2008] states that if the sets are convex and emph{wel l-separated}, then for any given $alpha_1, dots, alpha_d in [0, 1]$, there is a unique oriented hyperplane that cuts off a respective fraction $alpha_1, dots, alpha_d$ from each set. Steiger and Zhao [DCG 2010] proved a discrete analogue of this theorem, which we call the emph{$alpha$-Ham-Sandwich theorem}. They gave an algorithm to find the hyperplane in time $O(n (log n)^{d-3})$, where $n$ is the total number of input points. The computational complexity of this search problem in high dimensions is open, quite unlike the complexity of the Ham-Sandwich problem, which is now known to be PPA-complete (Filos-Ratsikas and Goldberg [STOC 2019]). Recently, Fearley, Gordon, Mehta, and Savani [ICALP 2019] introduced a new sub-class of CLS (Continuous Local Search) called emph{Unique End-of-Potential Line} (UEOPL). This class captures problems in CLS that have unique solutions. We show that for the $alpha$-Ham-Sandwich theorem, the search problem of finding the dividing hyperplane lies in UEOPL. This gives the first non-trivial containment of the problem in a complexity class and places it in the company of classic search problems such as finding the fixed point of a contraction map, the unique sink orientation problem and the $P$-matrix linear complementarity problem.
111 - Sahab Hajebi , Ramin Javadi 2021
A matching is a set of edges in a graph with no common endpoint. A matching $M$ is called acyclic if the induced subgraph on the endpoints of the edges in $M$ is acyclic. Given a graph $G$ and an integer $k$, Acyclic Matching Problem seeks for an acy clic matching of size $k$ in $G$. The problem is known to be NP-complete. In this paper, we investigate the complexity of the problem in different aspects. First, we prove that the problem remains NP-complete for the class of planar bipartite graphs with maximum degree three and girth of arbitrary large. Also, the problem remains NP-complete for the class of planar line graphs with maximum degree four. Moreover, we study the parameterized complexity of the problem. In particular, we prove that the problem is W[1]-hard on bipartite graphs with respect to the parameter $k$. On the other hand, the problem is fixed parameter tractable with respect to $k$, for line graphs, $C_4$-free graphs and every proper minor-closed class of graphs (including bounded tree-width and planar graphs).
We investigate the parameterized complexity of the following edge coloring problem motivated by the problem of channel assignment in wireless networks. For an integer q>1 and a graph G, the goal is to find a coloring of the edges of G with the maximu m number of colors such that every vertex of the graph sees at most q colors. This problem is NP-hard for q>1, and has been well-studied from the point of view of approximation. Our main focus is the case when q=2, which is already theoretically intricate and practically relevant. We show fixed-parameter tractable algorithms for both the standard and the dual parameter, and for the latter problem, the result is based on a linear vertex kernel.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا