Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

everybody knows there exist many decision problems which are NP-hard on general graphs, but I'm interested in problems that are even NP-hard when the underlying graph is a path. So, can you help me to collect such problems?

I've already found a related question about NP-hard problems on trees.

share|improve this question
16  
If you see that question you should also carefully read the accepted answer: "Take any NP-hard problem related to supersequences, superstrings, substrings, etc. Then re-interpret a string as a labelled path graph. " –  Saeed Feb 4 at 10:25
    
Thanks for your advice, I read over this fact. –  Benjamin Feb 4 at 11:13
1  
Just a note: if the paths are not labeled, they are obviously highly compressible and the compact representation is a reasonable choice ($\log n$ bits to represent a path of $n$ nodes) ... so you can also "convert" hard problems that don't use unary encoding; e.g. subset sum: given $n$ unlabeled paths of length $a_1,...,a_n$, does there exist a subset of them that can be joined to form a path of length $b$? –  Marzio De Biasi Feb 5 at 11:30
add comment

6 Answers 6

A rainbow matching in an edge-colored graph is a matching whose edges have distinct colors. The problem is: given an edge-colored graph $G$ and an integer $k$, does $G$ have a rainbow matching with at least $k$ edges? This is known as rainbow matching problem, and its NP-complete even for properly edge-colored paths. The authors even note that prior to this result, no unweighted graph problem is known to be NP-hard for simple paths to the best of their knowledge.

See Le, Van Bang, and Florian Pfender. "Complexity results for rainbow matchings." Theoretical Computer Science (2013), or the arXiv version.

share|improve this answer
add comment

Here are some simple observations.

  • An uncolored path graph basically encodes an integer, so you can take any NP-hard problem involving unary-encoded integers and reinterpret it as a path graph problem. If you allow multiple integers encoded in unary (= a disjoint union of path graphs), then you can use some strongly NP-complete problems like 3-Partition.

  • A colored path graph encodes a word on a fixed alphabet, so again you can take a NP-hard problem on words. An example that I'm aware of is the Disjoint Factors problem introduced in Bodlaender, Thomassé and Yeo.

share|improve this answer
2  
That's basically @Saeed's comment.. –  R B Feb 4 at 15:16
    
Right, then feel free to downvote my reply. As for NP-hard problems on trees, I can mention the well-known Bandwidth problem; it was actually shown to be hard for the W-hierarchy in a research report by Bodlaender, which I couldn't find online. –  Super0 Feb 4 at 15:27
add comment

MinCC Graph Motif is NP-hard when the graph is a path (even APX-hard). Given a graph with colors on the vertices and a set of colors, find a subgraph matching the set of colors and minimizing the number of connected comp. See Complexity issues in vertex-colored graph pattern matching, JDA 2011.

share|improve this answer
add comment

Given a path with $n$ nodes and weighted edges $1 \leq \text{weight}(u,v) < n$, find if the nodes can be labeled using numbers in $[1..n]$ (avoiding duplicate labels) in such a way that the absolute difference of the labels of two adjacent nodes is equal to the weight of the edge:

$$| \text{lab}(u) - \text{lab}(v)| = \text{weight}(u,v)$$

This is equivalent to the Permutation Reconstruction from Differences problem which is NPC (one of my "unofficial" results :-).

share|improve this answer
add comment

A trivial answer which is close to some of what appears above but, I think, distinct.

Fix any polynomial-time computable coding $f\colon\mathbb{N}^3\to\mathbb{N}$ of triples $\langle k,m,w\rangle$ as natural numbers. The set of values $f(k,m,w)$ such that the $m$th nondeterministic Turing machine accepts its $w$th input in at most $n^{\log k}$ steps (where $n$ is the length of that input) is NP-complete. ($\log k$ so that we're effectively coding $k$ in unary.) That set of values can be represented as a set of paths.

share|improve this answer
add comment

The Unsplittable Flow Problem (UFP) remains NP-hard on a path. Indeed, UFP is NP-hard even on a single edge, as it is equivalent to the Knapsack problem.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.