اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدClique in 3-track interval graphs is APX-hard
157
0
0.0
(
0
)
تأليف
Minghui Jiang
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Butman, Hermelin, Lewenstein, and Rawitz proved that Clique in t-interval graphs is NP-hard for t >= 3. We strengthen this result to show that Clique in 3-track interval graphs is APX-hard.
قيم البحث
اقرأ أيضاً
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.
Multiple interval graphs are variants of interval graphs where instead of a single interval, each vertex is assigned a set of intervals on the real line. We study the complexity of the MAXIMUM CLIQUE problem in several classes of multiple interval gr
aphs. The MAXIMUM CLIQUE problem, or the problem of finding the size of the maximum clique, is known to be NP-complete for $t$-interval graphs when $tgeq 3$ and polynomial-time solvable when $t=1$. The problem is also known to be NP-complete in $t$-track graphs when $tgeq 4$ and polynomial-time solvable when $tleq 2$. We show that MAXIMUM CLIQUE is already NP-complete for unit 2-interval graphs and unit 3-track graphs. Further, we show that the problem is APX-complete for 2-interval graphs, 3-track graphs, unit 3-interval graphs and unit 4-track graphs. We also introduce two new classes of graphs called $t$-circular interval graphs and $t$-circular track graphs and study the complexity of the MAXIMUM CLIQUE problem in them. On the positive side, we present a polynomial time $t$-approximation algorithm for WEIGHTED MAXIMUM CLIQUE on $t$-interval graphs, improving earlier work with approximation ratio $4t$.
A clique minor in a graph G can be thought of as a set of connected subgraphs in G that are pairwise disjoint and pairwise adjacent. The Hadwiger number h(G) is the maximum cardinality of a clique minor in G. This paper studies clique minors in the C
artesian product G*H. Our main result is a rough structural characterisation theorem for Cartesian products with bounded Hadwiger number. It implies that if the product of two sufficiently large graphs has bounded Hadwiger number then it is one of the following graphs: - a planar grid with a vortex of bounded width in the outerface, - a cylindrical grid with a vortex of bounded width in each of the two `big faces, or - a toroidal grid. Motivation for studying the Hadwiger number of a graph includes Hadwigers Conjecture, which states that the chromatic number chi(G) <= h(G). It is open whether Hadwigers Conjecture holds for every Cartesian product. We prove that if |V(H)|-1 >= chi(G) >= chi(H) then Hadwigers Conjecture holds for G*H. On the other hand, we prove that Hadwigers Conjecture holds for all Cartesian products if and only if it holds for all G * K_2. We then show that h(G * K_2) is tied to the treewidth of G. We also develop connections with pseudoachromatic colourings and connected dominating sets that imply near-tight bounds on the Hadwiger number of grid graphs (Cartesian products of paths) and Hamming graphs (Cartesian products of cliques).
Given a clique-width $k$-expression of a graph $G$, we provide $2^{O(k)}cdot n$ time algorithms for connectivity constraints on locally checkable properties such as Node-Weighted Steiner Tree, Connected Dominating Set, or Connected Vertex Cover. We a
lso propose a $2^{O(k)}cdot n$ time algorithm for Feedback Vertex Set. The best running times for all the considered cases were either $2^{O(kcdot log(k))}cdot n^{O(1)}$ or worse.
A proper edge-coloring of a graph $G$ with colors $1,ldots,t$ is called an emph{interval cyclic $t$-coloring} if all colors are used, and the edges incident to each vertex $vin V(G)$ are colored by $d_{G}(v)$ consecutive colors modulo $t$, where $d_{
G}(v)$ is the degree of a vertex $v$ in $G$. A graph $G$ is emph{interval cyclically colorable} if it has an interval cyclic $t$-coloring for some positive integer $t$. The set of all interval cyclically colorable graphs is denoted by $mathfrak{N}_{c}$. For a graph $Gin mathfrak{N}_{c}$, the least and the greatest values of $t$ for which it has an interval cyclic $t$-coloring are denoted by $w_{c}(G)$ and $W_{c}(G)$, respectively. In this paper we investigate some properties of interval cyclic colorings. In particular, we prove that if $G$ is a triangle-free graph with at least two vertices and $Gin mathfrak{N}_{c}$, then $W_{c}(G)leq vert V(G)vert +Delta(G)-2$. We also obtain bounds on $w_{c}(G)$ and $W_{c}(G)$ for various classes of graphs. Finally, we give some methods for constructing of interval cyclically non-colorable graphs.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
