Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Maximum Clique Problem in Multiple Interval Graphs
191
0
0.0
(
0
)
Added by
Mathew Francis
Publication date
2011
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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 graphs. 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$.
rate research
Read More
We study the complexity of Maximum Clique in intersection graphs of convex objects in the plane. On the algorithmic side, we extend the polynomial-time algorithm for unit disks [Clark 90, Raghavan and Spinrad 03] to translates of any fixed convex set. We also generalize the efficient polynomial-time approximation scheme (EPTAS) and subexponential algorithm for disks [Bonnet et al. 18, Bonamy et al. 18] to homothets of a fixed centrally symmetric convex set. The main open question on that topic is the complexity of Maximum Clique in disk graphs. It is not known whether this problem is NP-hard. We observe that, so far, all the hardness proofs for Maximum Clique in intersection graph classes $mathcal I$ follow the same road. They show that, for every graph $G$ of a large-enough class $mathcal C$, the complement of an even subdivision of $G$ belongs to the intersection class $mathcal I$. Then they conclude invoking the hardness of Maximum Independent Set on the class $mathcal C$, and the fact that the even subdivision preserves that hardness. However there is a strong evidence that this approach cannot work for disk graphs [Bonnet et al. 18]. We suggest a new approach, based on a problem that we dub Max Interval Permutation Avoidance, which we prove unlikely to have a subexponential-time approximation scheme. We transfer that hardness to Maximum Clique in intersection graphs of objects which can be either half-planes (or unit disks) or axis-parallel rectangles. That problem is not amenable to the previous approach. We hope that a scaled down (merely NP-hard) variant of Max Interval Permutation Avoidance could help making progress on the disk case, for instance by showing the NP-hardness for (convex) pseudo-disks.
We give an $O(n^4)$ algorithm to find a minimum clique cover of a (bull, $C_4$)-free graph, or equivalently, a minimum colouring of a (bull, $2K_2$)-free graph, where $n$ is the number of vertices of the graphs.
The Double Travelling Salesman Problem with Multiple Stacks, DTSPMS, deals with the collect and delivery of n commodities in two distinct cities, where the pickup and the delivery tours are related by LIFO constraints. During the pickup tour, commodities are loaded into a container of k rows, or stacks, with capacity c. This paper focuses on computational aspects of the DTSPMS, which is NP-hard. We first review the complexity of two critical subproblems: deciding whether a given pair of pickup and delivery tours is feasible and, given a loading plan, finding an optimal pair of pickup and delivery tours, are both polynomial under some conditions on k and c. We then prove a (3k)/2 standard approximation for the MinMetrickDTSPMS, where k is a universal constant, and other approximation results for vario
In this short note, we show two NP-completeness results regarding the emph{simultaneous representation problem}, introduced by Lubiw and Jampani. The simultaneous representation problem for a given class of intersection graphs asks if some $k$ graphs can be represented so that every vertex is represented by the same interval in each representation. We prove that it is NP-complete to decide this for the class of interval and circular-arc graphs in the case when $k$ is a part of the input and graphs are not in a sunflower position.
A matching $M$ in a graph $G$ is said to be uniquely restricted if there is no other matching in $G$ that matches the same set of vertices as $M$. We describe a polynomial-time algorithm to compute a maximum cardinality uniquely restricted matching in an interval graph, thereby answering a question of Golumbic et al. (Uniquely restricted matchings, M. C. Golumbic, T. Hirst and M. Lewenstein, Algorithmica, 31:139--154, 2001). Our algorithm actually solves the more general problem of computing a maximum cardinality strong independent set in an interval nest digraph, which may be of independent interest. Further, we give linear-time algorithms for computing maximum cardinality uniquely restricted matchings in proper interval graphs and bipartite permutation graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
