Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [co.combinatorics]

Questions related to combinatorics and discrete mathematical structures

19
votes
0answers
617 views

Weighted Hamming distance

Basically my question is, what kind of geometry do we get if we use a "weighted" Hamming distance. This is not necessarily Theoretical Computer Science but I think similar things come up sometimes, ...
6
votes
1answer
659 views

Lower bound on independence number in terms of clique number and order of graph

In the paper "On Multi-dimensional Packing Problems" by Chekuri and Khanna there is the following lemma: Lemma 4.3.(p. 191 of the paper) Let $G$ be a graph on $n$ vertices with $\omega(G) ≤ k$. Then $...
16
votes
1answer
650 views

Reference for (odd-hole,antihole)-free graphs?

X-free graphs are those that contain no graph from X as an induced subgraph. A hole is a cycle with at least 4 vertices. An odd-hole is a hole with an odd number of vertices. An antihole is the ...
27
votes
4answers
1k views

Maximal classes for which largest independent set can be found in polynomial time?

The ISGCI lists over 1100 classes of graphs. For many of these we know whether INDEPENDENT SET can be decided in polynomial time; these are sometimes called IS-easy classes. I would like to compile ...
5
votes
2answers
591 views

Non-hamiltonian Graphs with unique hamiltonian path between exactly 4 pair of vertices

Need some example graphs which are not Hamiltonian, i.e, does not admit any Hamiltonian cycle, but which have Hamiltonian path. It has Hamiltonian paths between exactly 4 pair of vertices. I have ...
22
votes
2answers
663 views

Are there local maxima in the number of moves required to solve a Rubik's Cube?

Peter Shor brought up an interesting point in relation to an attempt to answer an earlier question on the complexity of solving the $n \times n \times n$ Rubiks cube. I had posted a rather naive ...
25
votes
1answer
1k views

An edge partitioning problem on cubic graphs

Has the complexity of the following problem been studied? Input: a cubic (or $3$-regular) graph $G=(V,E)$, a natural upper bound $t$ Question: is there a partition of $E$ into $|E|/3$ parts of size $...
3
votes
2answers
828 views

Diameter of a graph with O(|V|) edges

What's the minimum diameter of a connected undirected graph with |V| vertices and O(|V|) edges?
10
votes
4answers
474 views

Interesting functions on graphs that can be efficiently maximized.

Say that I have a weighted graph $G = (V,E,w)$ such that $w:E\rightarrow [-1,1]$ is the weighting function -- note that negative weights are allowed. Say that $f:2^V\rightarrow \mathbb{R}$ defines a ...
52
votes
1answer
1k views

A combinatorial version for the polynomial Hirsch conjecture

Consider $t$ disjoint families of subsets of {1,2,…,n}, ${\cal F}_1,{\cal F_2},\dots {\cal F_t}$ . Suppose that (*) For every $i \lt j \lt k$ and every $R \in {\cal F}_i$, and $T \in {\cal F}_k$, ...
4
votes
3answers
413 views

Enumeration given a product of primes

Given a list of (small) primes $ (p_0, p_1, \dots, p_{n-1})$, is there an (efficient) algorithm to enumerate, in order, all numbers that can be expressed as $ \prod_{k=0}^{n-1} p_k^{e_k} $, where $e_k ...
5
votes
1answer
215 views

How can one construct a densest graph with no k-clique?

Given integers $k$ and $n$ with $2 \le k < n$, how does one construct a graph on $n$ vertices that contains no $k$-clique and has the maximal number of edges? This sounds like basic ...
17
votes
3answers
1k views

Properties of Random Directed Graphs with Fixed Out-Degree

I am interested in properties of random directed graphs with fixed out-degree $d$. I am imagining a random graph model where each vertex chooses d neighbors (say, with replacement) u.a.r. ...
7
votes
1answer
936 views

Graph Theory Fun Problem

Show that in any graph $G$ with min-degree $k$ ($k \geq 1$ duh!) you can find as its subgraph any tree on $k+1$ vertices. I have not been able to solve the question so far. However, I would like if ...
3
votes
2answers
497 views

Counting complexity of a scheduling problem. [closed]

Let $T={1,…,n}$ be a set of tasks. Each task $i$ has associated a non negative processing time $p_i$ and a deadline $d_i$. A feasible schedule of the tasks consists of a permutation of $n$ elements $\...
4
votes
1answer
216 views

Optimizing multiplication in a partly commutative semigroup

Let us say I have a semigroup M and its basis B. I know which elements of B commute. What is the most efficient way to do multiplication in such a semigroup? Essentially, this is a question of how ...
12
votes
1answer
360 views

Efficient algorithm for near-optimal edge-colourings of hypergraphs

Graph colouring problems are, already, hard enough for most people. Even so, I'm going to have to be difficult and ask a problem about hypergraph colouring. Question. What efficient algorithms are ...
11
votes
1answer
381 views

Computation of max H-free sets

In a graph, an independent set is a vertex subset which doesn't contain an edge as an induced subgraph. The problem of finding largest independent sets in a graph is a fundamental algorithmic question,...
13
votes
2answers
347 views

H-free partition

This is a question inspired by the H-free cut problem. Given a graph, a partition of its vertex set $V$ into $r$ parts $V_1, V_2, \ldots, V_r$ is $H$-free if $G[V_i]$ does not induce a copy of $H$ for ...
21
votes
1answer
340 views

Consensus clustering using set union

I've already posted this question a while ago on MathOverflow, but to the best of my knowledge it is still open, so I'm reposting it here in the hope that someone might have heard of it. Problem ...
37
votes
6answers
2k views

Grid $k$-coloring without monochromatic rectangles

Update: The obstruction set (i.e. the NxM "barrier" between colorable and uncolorable grid sizes) for all monochromatic-rectangle-free 4-colorings is now known. Anyone feel up to trying 5-colorings? ;...
38
votes
3answers
7k views

Is optimally solving the n×n×n Rubik's Cube NP-hard?

Consider the obvious $n\times n\times n$ generalization of the Rubik's Cube. Is it NP-hard to compute the shortest sequence of moves that solves a given scrambled cube, or is there a polynomial-time ...
19
votes
1answer
884 views

Construction of graphs where every pair of vertices have an unique common neighbor

Let $G$ be a simple graph on $n$ vertices $(n > 3)$ with no vertex of degree $n − 1$. Suppose that for any two vertices of $G$, there is a unique vertex adjacent to both of them. It is an exercise ...
4
votes
1answer
196 views

Choosing subsets of a set such that the subsets satisfy a global constraint

We have a set of items $I = \{i_1, i_2, ..., i_n\}$. Each of these items has what we call a p value, which is some real number. We want to choose a subset of $I$, call it $I'$, of size $m$ (for some ...
23
votes
6answers
2k views

Graph families which have polynomial time algorithms for computing the chromatic number

Post updated on 31st of August: I added a summary of the current answers below the original question. Thanks for all the interesting answers! Of course, everyone can continue posting any new findings. ...
41
votes
10answers
3k views

Kolmogorov complexity applications in computational complexity

Informally speaking, Kolmogorov complexity of a string $x$ is a length of a shortest program that outputs $x$. We can define a notion of 'random string' using it ($x$ is random if $K(x) \geq 0.99 |x|$)...
16
votes
2answers
339 views

Finding small sets of integers in which every element is a sum of two others

This is a follow-up to this question on math.stackexchange. Let us say that a non-empty set S ⊆ ℤ is self-supporting if for every a ∈ S, there exist distinct ...
23
votes
1answer
340 views

Cliquewidth of Almost Cographs

(I posted this question to MathOverflow two weeks ago, but so far without a rigorous answer) I have a question about graph width measures of undirected simple graphs. It is well-known that cographs (...
39
votes
13answers
2k views

Using error-correcting codes in theory

What are applications of error-correcting codes in theory besides error correction itself? I am aware of three applications: Goldreich-Levin theorem about hard core bit, Trevisan's construction of ...
23
votes
3answers
1k views

What is known about solutions to sparse integer linear programming problems?

If I have a set of linear constraints in which each constraint has at most (say) 4 variables (all nonnegative and with {0,1} coefficients except for one variable that can have a -1 coefficient), what ...