2
votes
0answers
109 views

NP-hard proof of optimization version of exact cover [closed]

Exact cover is NPC. http://en.wikipedia.org/wiki/Exact_cover#Equivalent_problems Given a collection $\mathcal{S}$ of subsets of a set $X$, an exact cover is a >>subcollection $\mathcal{S}^*$ ...
2
votes
0answers
158 views

Computing the chromatic polynomial of graph modulo $x-3$

The chromatic polynomial of graph $P(G,x)$ is univariate polynomial which counts the number of colorings of $G$ with $x$ colors for natural $x$. Graph is not $k$ colorable iff $P(G,k)=0$. The ...
3
votes
1answer
208 views

How hard is a variant of graph automorphism problem?

I'm interested in a variant of graph automorphism problem (which is prime candidate for $NP$-Intermediate problem). Restricted GA Input: Given an undirected graph $G(E, V)$, and $\epsilon |V|/2$ ...
0
votes
0answers
40 views

Complexity of graph isomorphism in $(P_4 \cup K_1,\overline{3K_2})$-free graphs

Related to this question where isomorphism preserving transformation maps triangle-free graphs to $(P_4 \cup K_1,\overline{3K_2})$-free graphs. What is the complexity of graph isomorphism in $(P_4 ...
1
vote
0answers
49 views

Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs

Let $C$ be a graph class defined by a finite number of forbidden induced subgraphs, all of which are cyclic (contain at least one cycle). Are there graph problems that can be solved in ...
33
votes
6answers
2k views

Is it easy to produce hard-to-color graphs?

This question arises from my recent visit to my daughter's second-grade class, where I led some discussion and activities on graph coloring (see Math for seven-year-olds). In one such activity, each ...
13
votes
1answer
588 views

Who first dubbed them “expander graphs”?

Expander graphs ("sparse graphs that have strong connectivity properties") burst onto the mathematical scene around the millennium, but I have not been successful in tracing the origin of (a) the ...
1
vote
0answers
120 views

Basis of periodic tiling of Wang tile

Given a set of Wang tile, Given 3 periodic tiling: A, B, C We define 3 vector F[A], F[B], F[C] each vector correspond to the appearing frequency of each type of tiles in the tiling. Now, we ...
2
votes
1answer
88 views

simple cycle analog in 2D (with application in tiling)

We know that any closed cycle of a graph could be decomposed into sum of simple cycles. To translate this theorem into tiling of 1D (Wang tile). We know that any 1D periodic tiling could be ...
2
votes
0answers
101 views

Graph theoretical representation of Wang Tile

We note that for one dimensional tiling problem of Wang Tile could be represented by a graph. Each cycle on the graph represents a periodic solution. However, is there a well established counter-part ...
1
vote
1answer
78 views

Is undirected short-simple-path-through-3-vertices decidable in polynomial time?

Consider the following language: $L=\{\langle G=(V,E),s,v,t,l\rangle\;|\;s,v,t\in V, l\in \mathbb{N} \wedge $ There exists a simple path from $s$ to $t$, going through $v$ of length $\leq l\}$. ($G$ ...
3
votes
1answer
132 views

Is the domination number NP for non-bipartite graphs?

Calculating the domination number is an NP-Hard problem. Does it remain NP-Hard if we restrict it to non-bipartite graphs?
7
votes
1answer
403 views

Seeming contradiction about P vs NP between graphclasses.org and at least two papers about clique in even-hole-free graphs

I believe correctness about clique in even-hole-free graphs of graphclasses.org and the paper Vertex elimination orderings for hereditary graph classes, Pierre Aboulker, Pierre Charbit, Nicolas ...
8
votes
1answer
319 views

A combinatorial problem concerned with logic circuits

Consider a logic circuit with two-bit gates only. The length of each gate is the number of bit lines that the gate crosses. How hard is to compute the maximum length for a given circuit? Notice that ...
3
votes
2answers
195 views

Making a graph claw-free by adding as few edges as possible

Independent set is polynomial in claw-free graphs, so I am wondering if this can approximate independent set. By adding enough edges to $G$ and gets claw-free $G'$. IS in $G'$ is IS in $G$, so this ...
4
votes
2answers
217 views

Cubic graphs decompositions

There are many interesting computational problems related to connected cubic graph decomposition. For instance, decomposition of cubic graph into a perfect matching and a connected 2-factor ...
2
votes
0answers
109 views

Partitioning a cubic graph into two induced cycles of equal order

I am aware that deciding the existence of a partition of the vertices of a connected graph $G(V, E)$ into two induced cycles is $NP$-complete(Theorem 2). Induced cycle is a cycle without any chord ...
1
vote
1answer
144 views

Graph classes where Hamiltonian Cycle and Hamiltonian Path problems have different complexity

While searching The information System on Graph Classes and their Inclusions, I stumbled on several graph classes for which the Hamiltonian Cycle problem is $NP$-complete while the complexity of ...
5
votes
0answers
113 views

Complexity of finding three perfect matchings with no edge in common in a bridgeless cubic graph

According to a conjecture: Conjecture (Fan & Raspaud, 1994) Every bridgeless cubic graph contains three perfect matchings with no edge in common. Equivalent statement here Main question: ...
3
votes
1answer
166 views

Minimum distance between Hamiltonian cycles in cubic Hamiltonian graph

It is $NP$-hard to find constant factor approximation of longest cycle in cubic Hamiltonian graphs. Therefore, finding a Hamiltonian cycle in a cubic Hamiltonian graph is NP-hard. By Smith's theorem, ...
3
votes
1answer
164 views

Hamiltonian circuit

Let us consider a disk with one labelled point on the boundary and $n$ labelled points in the interior. Let T be a triangulation of the whole disk with vertices on the labelled points such that T ...
0
votes
0answers
68 views

maximum weight k-edge problem

Given positive integer $k$ and an undirected graph $(V,E)$, with nonnegative (non-uniform) weights on the nodes. Find $k$ edges whose spanning nodes have the maximum weight. Is this in P or NP? I ...
5
votes
5answers
280 views

Efficient Hamiltonian cycle algorithms for graph classes

Generally speaking finding a Hamiltonian cycle is NP-Hard and so tough. But if $G=L(H)$ is the line graph of $G$ then we can reduce the finding of a Hamiltonian cycle in $G$ to a Eurler your of $H$ ...
4
votes
1answer
154 views

NP-hardness of sparsest cut

Consider bipartitioning the vertices of a graph $(V,E)$ into $V = P \cup Q$ to minimize $$\frac{|E(P,Q)|}{|P| |Q|},$$ where $E(P,Q)$ denotes the set of edges in the cut. The usual citation for ...
2
votes
0answers
53 views

Is the $d$-dimensional Arrangement of Trees still $NP$-hard?

The $d$-dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...
1
vote
0answers
92 views

Schönhage's SMM with only one instruction

It is possible to implement $\lambda$-calculus in Schönhage's storage modification machine using an infinite set of nodes and one single program consisted exclusively of (about hundred) instructions ...
1
vote
1answer
107 views

Separation of Anti-Hole Inequality

Given an undirected graph $G=(V,E)$ with no loops or multiple edges, a stable set is a set of vertices for which no two vertices are adjacent. An induced subgraph $H$ of $G$ is called an odd-antihole ...
1
vote
2answers
111 views

complexity of finding optimal matchings of given fixed size

It is known, that maximal matchings (i.e. matchings with the maximal number of edges) and optimal matchings (i.e. matchings for which the sum of edge weights is optimal) can be calculated in ...
6
votes
1answer
233 views

Do sparse DAGs can have large min-cuts?

For a graph $G$, let $e(G)$ denote the number of its edges, and $c_k(G)$ the smallest number of edges that must be removed in order to destroy all paths of length $\geq k+1$. Note that $c_1(G)\geq ...
1
vote
0answers
128 views

NP problem implications [closed]

Hi, i would like to have some clarification on NP-completeness. In particular I'm reading an article where they show: 1) Partitioning the edges of a graph into connected component of 3 edges (3-path ...
4
votes
1answer
225 views

If a graph invariant is NP-Hard, is its “deck ratio” NP-Hard as well?

This question is inspired by the Graph Reconstruction Conjecture. Suppose that $\psi$ is some graph invariant and that it is NP-Hard. There is a plethora of examples, of course. Now define ...
1
vote
2answers
129 views

Is number of quasi-kernels NP-hard?

A quasi-kernel in a directed graph D is an independent subset of vertices $S$ so that for every $v \in V(D)-S$ either $v->s$ for some $s \in S$ or $v->w->s$ for some $w \in V(D)-S, s \in S$. ...
2
votes
0answers
171 views

A natural problem on “cartesian union” of set families (hypergraphs). Does anybody know NP-complete problems related to the notion of cartesian product?

I'm curious whether the problem below is NP-complete. I provide two simple definitions and one example at first. Definition 1. Let $\langle {\cal{S}}_i\rangle\substack{i\in I}$ and $\langle ...
3
votes
2answers
1k views

Generation of All Path in a Directed Acyclic Graph

I am working on a very large dataset of a single DAG whose vertices have a low branching factor. I need to generate all possible (simple) paths starting from the source and write them to a file. My ...
10
votes
1answer
582 views

A generalization of the triangle counting problem for simple weighted graphs

One nice identity is $$tr(A^3)/6$$ which counts the number of triangles of a graph represented with adjacency matrix $A.$ It also implies that triangle counting can be performed in subcubic time. ...
0
votes
1answer
186 views

graph to tree and graph isomorphism problem

Sorry if the following are stupid questions (i do not know much about the graph theory). 1. Motivation we do not know the graph isomorphism problem in class P or NP complete and it is P in the ...
14
votes
3answers
502 views

Complexity of equitable partitions

We are talking about undirected simple graphs and partitions of their vertex sets into disjoint non-empty cells. Such a partition is equitable if for any two vertices $v,w$ in the same cell, and any ...
3
votes
1answer
234 views

Complexity of Labeled Graph Homomorphism

The following recreational math problem has been floating around work: We're given an $m \times n$ grid ($m,n$ positive integers). We wish to label the elements of the grid with letters so that we ...
3
votes
1answer
123 views

Counting connected fundamental domains of actions on Cayley graphs

The following question arises, for me, from mathematical music theory: Write $({\Bbb Z}^n,E_n)$ for the Cayley graph of ${\Bbb Z}^n$ relative to standard free generators. Given a subgroup $L$ of ...
1
vote
1answer
478 views

k-uniform k-partite hypergraph matching in polynomial time

I have what seems like an elementary question, but google didn't throw up any answers for it. I would appreciate any pointers that MO users may provide. It is well known that for $k\geq 3$ finding ...
3
votes
1answer
125 views

Quick tests for Self complementary vertex transitive graphs

Are there any quick tests to determine if a graph is Self complementary vertex transitive? That is if the graph is self complementary vertex transitive the answer should be yes.
3
votes
0answers
153 views

Best lower bound for proof complexity of graph asymmetry

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 ...
6
votes
1answer
594 views

NP-hardness of a graph partition problem?

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 ...
2
votes
2answers
630 views

Enumerating all Hamiltonian Cycles in a Bipartite Vertex Transitive Graph

Hi everyone! This is my first post, apologies if I made any mistakes anywhere. Here goes the question: Consider all length 7 binary sequences. Let $X$ be the set of sequences with hamming weight 3 ...
13
votes
6answers
1k views

Compressing Graphs (Kolmogorov complexity of graphs)

What is known about compressing graphs? Here, with "compressing", I mean something like "putting a graph into a zip program"; or with a more technical expression, what is know about the Kolmogorov ...
2
votes
0answers
176 views

Complexity of bipartite graphs and their matchings.

My question concerns a hypothetical family of bipartite graphs, $G_i$. Each graph $G_i$ has $2^i$ red nodes and $2^i$ blue nodes - so nodes get labelled by their color and a binary string of ...
4
votes
1answer
803 views

Finding a vertex of least distance to all other vertices in a graph

Some background to my question: if $G$ is a (simple) graph of $N$ vertices, labelled by integers $0,1,...,N-1$, the closeness centrality of a vertex $i$, denoted by $C(i)$, is defined to be the ...
2
votes
0answers
336 views

Hamiltonian paths in subgraphs of rectangular lattice graphs

Is following decision problem NP-hard / NP-complete: Having vertex-induced subgraph of rectangular lattice graph determine if any Hamiltonian path exists Having vertex-induced subgraph of ...
2
votes
2answers
527 views

Could this be a NP complete?

Given a undirected and unweighted graph G(V,E). M is a subset of vertices of V. s is a vertex in V - M. Find an optimal tree T of G defined as: (1) M and s are in V(T) (2) Distance (which is ...
2
votes
0answers
187 views

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

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 ...