User mohammad al-turkistany - MathOverflow

How dense is the set of asymmetric graphs?

2013-04-21T10:40:25Z

On $n$ nodes, we have $2^{n(n-1)/2}$ graphs. Asymmetric graph is a graph that has only trivial automorphism. We known that asymptotically almost all finite graphs are asymmetric. Therefore, in the limit, the ratio of asymmetric graphs approaches 1.

However, I did not find any reference that provides lower bound on the number of asymmetric graphs on $n$ nodes. What is known about the density of asymmetric graphs as a function of the number of nodes $n$?

Redundancy and Structure of computational problems

2012-10-08T09:22:40Z

It is widely believed that some computational problems such as graph isomorphism can not be NP-complete because it does not possess enough structure or redundancy to be computationally hard (NP-hard). I'm interested in the different formal notions for structure of computational problems and redundancy measures.

What are the major results known about such formal notions for computational problems? A recent survey of such notions would be very nice.

It was posted on TCS stackexchange without any answer.

Best lower bound for proof complexity of graph asymmetry

2012-03-17T18:26:30Z

Graph automorphism problem ( GA) of determining whether a graph has a nontrivial automorphism is a good candidate for a problem in $NP$-intermediate. I'm looking for references that study the certificate complexity of graph non-automorphism (GNA= {G| G is rigid or asymmetric graph}).

What is the best known lower bound on the length of certificates that prove a graph is rigid ($G \in GNA$)? Also, Is there a plausible conjecture that prohibits sub-exponential certificates for $CoNP$-complete problems (analogues to ETH)?

NP-hardness of a graph partition problem?

2012-03-03T16:00:05Z

I'm interested in this problem: Given an undirected graph $G(E, V)$, Is there a partition of $G$ into graphs $G_1(E_1, V_1)$ and $G_2(E_2, V_2)$ such that $G_1$ and $G_2$ are isomorphic? Here $E$ is partitioned into two disjoint sets $E_1$ and $E_2$. Sets $V_1$ and $V_2$ are not necessarily disjoint. $E1∪E2=E$ and $V1∪V2=V$.

This problem is at least as hard as Graph Isomorphism Problem. I guess it is harder than Graph Isomorphism but not NP-hard.

Is this partition problem $NP$-hard?

I posted it on CS theory without any answer.

Partition a square into sub-rectangles with restrictions

2011-05-13T21:55:29Z

Is there an algorithm to generate all partitions of given square by using $n$ vertical and $n$ horizontal lines into sub-rectangles under the following restrictions:

1- No vertical line crosses any horizontal line and vice versa.

2- Each vertical line touches exactly three horizontal lines and each horizontal line touches exactly three vertical lines.

Here is an example when $n=4$

NP-complete variants of NPI problems

2011-06-23T15:41:29Z

Motivated by these posts, An NP-complete variant of factoring and Relationship between symmetry and computational intractability, It seems to be worthwhile to investigate the different factors that increase the hardness of problems in NPI. I'm interested in other NP-complete variants of problems of intermediate complexity.

Is there a recent survey paper of $NP$-complete variants of problems of intermediate complexity (problems between P and NP-complete)?

Cross posted on TCS StackExchange

UPDATE: Bounty may be awarded to an answer that gives other interesting NPI problems that have an $NP$-complete variant.

Complexity of a problem related to 3D matching?

2011-04-24T16:07:26Z

Given a set of triples of a base set $S$, find a subset of triples such that each element in $S$ appears exactly in one triple. This problem is NP-complete by reduction from NP-complete problem 3D Matching.

I'm interested in the complexity of related problem. What is the complexity of finding a subset of triples such that each element in $S$ appears exactly in two triples?

Has this problem been studied in the literature? I'd greatly appreciate pointing me to references.

Complexity of Max Bisection on cubic planar graphs?

2011-01-20T05:30:33Z

Max Bisection problem is to partition the set of nodes into two equal size sets such that the number of crossing edges is maximized. Max Bisection is $NP$-complete on cubic graphs and also on planar graphs.

What is the complexity of Max Bisection on cubic planar graphs? Is it $NP$-complete?

Cross posted on SE tcs

Complexity of finding disjoint 2-factors with equal cardinality in cubic graphs?

2011-04-13T10:41:01Z

Finding a connected 2-factor that contains every node in cubic graphs is $NP$-complete since it is equivalent to the Hamiltonian cycle problem. I'm interested in the complexity of finding vertex disjoint 2-factors with equal cardinality in cubic graphs.

I suspect that it is $NP$-complete but I'm not able to find a reference. Also, What is the complexity of finding vertex disjoint 2-factors with equal cardinality in planar cubic bipartite graphs? Is it $NP$-complete?

Providing references is highly appreciated.

Abstract notion for energy complexity of computational problems?

2011-01-20T07:31:53Z

Energy is very valuable computational resource especially in mobile computing. Optimizing the energy consumed during the execution of algorithms has significant practical implications. Intuitively, It seems that such abstract energy measure has to be correlated to the time complexity, the space complexity, and the frequency of space (memory) access operations. Communications costs should be accounted for if we consider distributed computing model.

Are there abstract notions of energy (possibly analogous to the action quantity in physics) which could be useful for establishing energy-complexity classes for computational problems?

This is a follow-up to this question on SE TCS

Complexity of edge coloring in planar graphs?

2011-02-22T19:21:37Z

I asked this on StackExchange TCS but did not get a satisfactory answer:

Four Color Theorem is equivalent to "Every cubic planar bridgeless graphs is 3-edge colorable". However, 3-edge coloring of cubic graphs is $NP$-complete. I'm wondering if the problem is still hard for cubic planar graphs.

What is the complexity of 3-edge coloring for cubic planar graphs?

Also, It is conjectured that $\Delta$-edge coloring is $NP$-hard for planar graphs with maximum degree $\Delta \in${4,5}.

Has any progress been made towards resolving this conjecture?

Marek Chrobak and Takao Nishizeki. Improved edge-coloring algorithms for planar graphs. Journal of Algorithms, 11:102-116, 1990

Hardness of discrete geometric area minimization problem?

2010-11-14T15:43:25Z

This question was originally posted on: cstheory.stackexchange

Given $xyz=C$ where $x, y,$ and $z$ are integer variables and $C$ is integer constant. Assume all integers are encoded in binary.

What is the complexity of finding $x, y, z$ such that $xy+xz+yz$ has minimum value? Is there any subexponential algorithm that solves this problem? Does the problem become easier when integers are encoded in unary?

Motivation: I'm interested in the following generalized problem:

Input: integers $C$ and $K$

Problem: Find integers $x$, $y$, and $z$ such that $xyz\ge C$ and $xy+xz+yz\le K$

Human checkable proof of the Four Color Theorem?

2010-11-03T13:20:15Z

Four Color Theorem is equivalent to the statement: "Every cubic planar bridgeless graphs is 3-edge colorable". There is computer assisted proof given by Appel and Haken. Dick Lipton in of his beautiful blogs posed the following open problem:

Are there non-computer based proofs of the Four Color Theorem?

Surprisingly, While I was reading this paper, Anshelevich and Karagiozova, Terminal backup, 3D matching, and covering cubic graphs , the authors state that Cahit proved that "every 2-connected cubic planar graph is edge-3-colorable" which is equivalent to the Four Color Theorem (I. Cahit, Spiral Chains: The Proofs of Tait's and Tutte's Three-Edge-Coloring Conjectures. arXiv preprint, math CO/0507127 v1, July 6, 2005).

Does Cahit's proof resolve the open problem in Lipton's blog by providing non-computer based proof for the Four Color Theorem?

Cross posted on cstheory.stackexchange.com as Human checkable proof of the Four Color Theorem?

Complexity of a variant of the Mandelbrot set decision problem?

2010-09-27T15:54:12Z

This is a modified version of a question posted on StackExchange TCS.

Mandelbrot set is defined using the complex equation $P_c (z)=z^2 +c$ where $c$ is a complex number. Let us define

$M=${$(c,k,r) |$ In the sequence $P_c (0),P_c (P_c (0)), P_c (P_c (P_c (0)))...$ of first $k$ complex numbers, there is a subset $T$ of complex numbers such that the sum of the real parts $\gt$ $r.k$ and the sum of imaginary parts $\gt$ $r.k$}

where $r$ is real number and $k$ is an integer in unary.

Here is a geometric interpretation, since each $P_c^i(0)$ is a vector in 2D, we want to find the maximum size square obtainable by the summation of a subset of two dimensional vectors.

Is there an efficient algorithm in the real computing model (i.e the Blum-Shub-Smale model) for deciding set $M$ or is it $NP$-complete ?

EDIT: Is there any NP-complete problem related to Mandelbrot set?

Self-improvement property of optimazation problems?

2010-09-16T16:33:08Z

Maximum CLIQUE problem is very hard to approximate. It has a self-improvement property defined using graph product which is utilized to prove hardness of approximation results. One such example is ruling out any constant factor polynomial time approximation scheme unless $P = NP$. Furthermore, using booster products, we can show that its NP-hard to approximate Max CLIQUE within a factor of $n^{\epsilon}$ for some value $\epsilon >0$. Also, Maximum independent set problem has a self-improvement property which is used to rule out constant factor approximation (assuming $P \ne NP$).

I would like to gain insights into the failure of many optimization problems to have self-improvement property. What are the common features of hard to approximate problems that poses self-improvement property?

Under what conditions an optimization problem can not poses self-improvement property?

Comment by Mohammad Al-Turkistany

2012-03-04T14:27:50Z

Thanks Hebert. GT12 is different since the required isomorphism is fixed by graph $H$.

Comment by Mohammad Al-Turkistany

2011-05-14T22:17:51Z

Here is the paper: de Fraysseix, de Mendez, and Pach: Representation of planar graphs by segments, in: Intuitive Geometry.

Comment by Mohammad Al-Turkistany

2011-05-14T18:06:57Z

Thanks Mark. There is a theorem which states that every planar bipartite graph is representable by a contact graph of horizontal and vertical line segments. I'm looking for explicit algorithm to construct contact graphs that correspond to cubic planar bipartite graphs.

Comment by Mohammad Al-Turkistany

2011-04-24T18:25:24Z

Which reduction do you have in mind for NP-hardness?

Comment by Mohammad Al-Turkistany

2011-04-13T10:49:34Z

$NP$-completeness refers to the decision version of the problem.

Comment by Mohammad Al-Turkistany

2011-04-03T05:57:14Z

@Phil, Nice answer. You should convert your comment to an answer.

Comment by Mohammad Al-Turkistany

2010-11-16T12:23:05Z

Thanks Aaron, Does your answer suggest that exhaustive search ($2^{\Omega (n)}$−time) is unavoidable?

Comment by Mohammad Al-Turkistany

2010-11-14T20:38:16Z

Indeed, x,y,z are positive integers.

Comment by Mohammad Al-Turkistany

2010-11-14T20:37:07Z

@Qiaochu, Is exhaustive search avoidable in either case? Are you aware of any subexponential-time algorithms?

Comment by Mohammad Al-Turkistany

2010-11-14T16:18:21Z

It think the first problem is a special case of the second problem. Am I right?

Comment by Mohammad Al-Turkistany

2010-09-17T18:08:18Z

I agree, there is no rigorous systematic study of Self-improvement properties of optimization problems. All examples I have seen are Ad-hoc in nature. For instance, Karger used it to prove that the Longest Path cannot be approximated within $O(\log n)$ unless P=NP. Karger, Motwani, Ramkumar, [On approximating the longest path in a graph](springerlink.com/content/861m67dd2euu4qlj) <a href="springerlink.com/content/861m67dd2euu4qlj/…;